Skip to content

Commit 4ececbe

Browse files
lperronlperron
committed
update python code, remove __future__ imports, remove six, use absl-py for flags, update examples
1 parent c1b23ff commit 4ececbe

99 files changed

Lines changed: 245 additions & 339 deletions

File tree

Some content is hidden

Large Commits have some content hidden by default. Use the searchbox below for content that may be hidden.

‎examples/python/appointments.py‎

Lines changed: 0 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -12,8 +12,6 @@
1212
# limitations under the License.
1313
"""Generates possible daily schedules for workers."""
1414

15-
from __future__ import print_function
16-
from __future__ import division
1715

1816
import argparse
1917
from ortools.sat.python import cp_model

‎examples/python/arc_flow_cutting_stock_sat.py‎

Lines changed: 0 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -12,7 +12,6 @@
1212
# limitations under the License.
1313
"""Cutting stock problem with the objective to minimize wasted space."""
1414

15-
from __future__ import print_function
1615

1716
import argparse
1817
import collections

‎examples/python/assignment2_sat.py‎

Lines changed: 0 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -11,7 +11,6 @@
1111
# See the License for the specific language governing permissions and
1212
# limitations under the License.
1313

14-
from __future__ import print_function
1514
from ortools.sat.python import cp_model
1615

1716

‎examples/python/assignment_with_constraints_sat.py‎

Lines changed: 0 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -12,7 +12,6 @@
1212
# limitations under the License.
1313
"""Solve an assignment problem with combination constraints on workers."""
1414

15-
from __future__ import print_function
1615

1716
from ortools.sat.python import cp_model
1817

‎examples/python/balance_group_sat.py‎

Lines changed: 0 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -18,8 +18,6 @@
1818
be in that group.
1919
"""
2020

21-
from __future__ import print_function
22-
from __future__ import division
2321

2422
from ortools.sat.python import cp_model
2523

‎examples/python/bus_driver_scheduling_flow_sat.py‎

Lines changed: 0 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -21,7 +21,6 @@
2121
- 15 min cleaning time after the last shift
2222
- 2 min waiting time after each shift for passenger boarding and alighting
2323
"""
24-
from __future__ import print_function
2524

2625
import argparse
2726
import collections

‎examples/python/bus_driver_scheduling_sat.py‎

Lines changed: 75 additions & 39 deletions
Original file line numberDiff line numberDiff line change
@@ -21,13 +21,23 @@
2121
- 15 min cleaning time after the last shift
2222
- 2 min waiting time after each shift for passenger boarding and alighting
2323
"""
24-
from __future__ import print_function
2524

2625
import collections
2726
import math
2827

28+
from google.protobuf import text_format
29+
from absl import app
30+
from absl import flags
2931
from ortools.sat.python import cp_model
3032

33+
FLAGS = flags.FLAGS
34+
35+
flags.DEFINE_string('output_proto', '',
36+
'Output file to write the cp_model proto to.')
37+
flags.DEFINE_string('params', 'num_search_workers:8,log_search_progress:true',
38+
'Sat solver parameters.')
39+
flags.DEFINE_integer('instance', 1, 'Instance to select (1, 2, 3).', 1, 3)
40+
3141
SAMPLE_SHIFTS_SMALL = [
3242
#
3343
# column description:
@@ -1652,22 +1662,39 @@
16521662
[1355, '00:57', '01:07', 1497, 1507, 10]
16531663
] # yapf:disable
16541664

1655-
1656-
SAMPLE_SHIFTS = SAMPLE_SHIFTS_MEDIUM
1665+
# pytype: disable=wrong-arg-types
16571666

16581667

16591668
def bus_driver_scheduling(minimize_drivers, max_num_drivers):
16601669
"""Optimize the bus driver scheduling problem.
16611670
1662-
This model has two modes.
1671+
This model has two modes.
1672+
1673+
If minimize_drivers == True, the objective will be to find the minimal
1674+
number of drivers, independently of the working times of each drivers.
16631675
1664-
If minimize_drivers == True, the objective will be to find the minimal
1665-
number of drivers, independently of the working times of each drivers.
1676+
Otherwise, will will create max_num_drivers non optional drivers, and
1677+
minimize the sum of working times of these drivers.
16661678
1667-
Otherwise, will will create max_num_drivers non optional drivers, and
1668-
minimize the sum of working times of these drivers.
1669-
"""
1670-
num_shifts = len(SAMPLE_SHIFTS)
1679+
Args:
1680+
minimize_drivers: A Boolean parameter specifying the objective of the
1681+
problem. If True, it tries to minimize the number of used drivers. If
1682+
false, it minimizes the sum of working times per workers.
1683+
max_num_drivers: This number specifies the exact number of non optional
1684+
drivers to use. This is only used if 'minimize_drivers' is False.
1685+
1686+
Returns:
1687+
The objective value of the model.
1688+
"""
1689+
shifts = None
1690+
if FLAGS.instance == 1:
1691+
shifts = SAMPLE_SHIFTS_SMALL
1692+
elif FLAGS.instance == 2:
1693+
shifts = SAMPLE_SHIFTS_MEDIUM
1694+
elif FLAGS.instance == 3:
1695+
shifts = SAMPLE_SHIFTS_LARGE
1696+
1697+
num_shifts = len(shifts)
16711698

16721699
# All durations are in minutes.
16731700
max_driving_time = 540 # 8 hours.
@@ -1680,12 +1707,12 @@ def bus_driver_scheduling(minimize_drivers, max_num_drivers):
16801707
cleanup_time = 15
16811708

16821709
# Computed data.
1683-
total_driving_time = sum(shift[5] for shift in SAMPLE_SHIFTS)
1684-
min_num_drivers = int(
1685-
math.ceil(total_driving_time * 1.0 / max_driving_time))
1710+
total_driving_time = sum(shift[5] for shift in shifts)
1711+
min_num_drivers = int(math.ceil(total_driving_time * 1.0 /
1712+
max_driving_time))
16861713
num_drivers = 2 * min_num_drivers if minimize_drivers else max_num_drivers
1687-
min_start_time = min(shift[3] for shift in SAMPLE_SHIFTS)
1688-
max_end_time = max(shift[4] for shift in SAMPLE_SHIFTS)
1714+
min_start_time = min(shift[3] for shift in shifts)
1715+
max_end_time = max(shift[4] for shift in shifts)
16891716

16901717
print('Bus driver scheduling')
16911718
print(' num shifts =', num_shifts)
@@ -1760,7 +1787,7 @@ def bus_driver_scheduling(minimize_drivers, max_num_drivers):
17601787
performed[d, s] = model.NewBoolVar('performed_%i_%i' % (d, s))
17611788

17621789
for s in range(num_shifts):
1763-
shift = SAMPLE_SHIFTS[s]
1790+
shift = shifts[s]
17641791
duration = shift[5]
17651792

17661793
# Arc from source to shift.
@@ -1772,10 +1799,9 @@ def bus_driver_scheduling(minimize_drivers, max_num_drivers):
17721799
shared_incoming_literals[s].append(source_lit)
17731800
model.Add(start_times[d] == shift[3] -
17741801
setup_time).OnlyEnforceIf(source_lit)
1775-
model.Add(
1776-
total_driving[d, s] == duration).OnlyEnforceIf(source_lit)
1777-
model.Add(
1778-
no_break_driving[d, s] == duration).OnlyEnforceIf(source_lit)
1802+
model.Add(total_driving[d, s] == duration).OnlyEnforceIf(source_lit)
1803+
model.Add(no_break_driving[d,
1804+
s] == duration).OnlyEnforceIf(source_lit)
17791805
starting_shifts[d, s] = source_lit
17801806

17811807
# Arc from shift to sink
@@ -1787,14 +1813,15 @@ def bus_driver_scheduling(minimize_drivers, max_num_drivers):
17871813
incoming_sink_literals.append(sink_lit)
17881814
model.Add(end_times[d] == shift[4] +
17891815
cleanup_time).OnlyEnforceIf(sink_lit)
1790-
model.Add(driving_times[d] == total_driving[d, s]).OnlyEnforceIf(
1791-
sink_lit)
1816+
model.Add(
1817+
driving_times[d] == total_driving[d, s]).OnlyEnforceIf(sink_lit)
17921818

17931819
# Node not performed
17941820
# - set both driving times to 0
17951821
# - add a looping arc on the node
1796-
model.Add(total_driving[d, s] == 0).OnlyEnforceIf(
1797-
performed[d, s].Not())
1822+
model.Add(total_driving[d,
1823+
s] == 0).OnlyEnforceIf(performed[d,
1824+
s].Not())
17981825
model.Add(no_break_driving[d, s] == 0).OnlyEnforceIf(
17991826
performed[d, s].Not())
18001827
incoming_literals[s].append(performed[d, s].Not())
@@ -1811,7 +1838,7 @@ def bus_driver_scheduling(minimize_drivers, max_num_drivers):
18111838
performed[d, s])
18121839

18131840
for o in range(num_shifts):
1814-
other = SAMPLE_SHIFTS[o]
1841+
other = shifts[o]
18151842
delay = other[3] - shift[4]
18161843
if delay < min_delay_between_shifts:
18171844
continue
@@ -1826,9 +1853,8 @@ def bus_driver_scheduling(minimize_drivers, max_num_drivers):
18261853
model.Add(
18271854
no_break_driving[d, o] == other[5]).OnlyEnforceIf(lit)
18281855
else:
1829-
model.Add(
1830-
no_break_driving[d, o] == no_break_driving[d, s] +
1831-
other[5]).OnlyEnforceIf(lit)
1856+
model.Add(no_break_driving[d, o] == no_break_driving[d, s] +
1857+
other[5]).OnlyEnforceIf(lit)
18321858

18331859
# Add arc
18341860
outgoing_literals[s].append(lit)
@@ -1890,26 +1916,32 @@ def bus_driver_scheduling(minimize_drivers, max_num_drivers):
18901916
working_drivers[d + 1].Not())
18911917

18921918
# Redundant constraints: sum of driving times = sum of shift driving times
1893-
model.Add(sum(driving_times) == total_driving_time)
1919+
model.Add(cp_model.LinearExpr.Sum(driving_times) == total_driving_time)
18941920
if not minimize_drivers:
18951921
model.Add(
1896-
sum(working_times) == total_driving_time +
1922+
cp_model.LinearExpr.Sum(working_times) == total_driving_time +
18971923
num_drivers * (setup_time + cleanup_time) +
18981924
cp_model.LinearExpr.ScalProd(delay_literals, delay_weights))
18991925

19001926
if minimize_drivers:
19011927
# Minimize the number of working drivers
1902-
model.Minimize(sum(working_drivers))
1928+
model.Minimize(cp_model.LinearExpr.Sum(working_drivers))
19031929
else:
19041930
# Minimize the sum of delays between tasks, which in turns minimize the
19051931
# sum of working times as the total driving time is fixed
19061932
model.Minimize(
19071933
cp_model.LinearExpr.ScalProd(delay_literals, delay_weights))
19081934

1935+
if not minimize_drivers and FLAGS.output_proto:
1936+
print('Writing proto to %s' % FLAGS.output_proto)
1937+
with open(FLAGS.output_proto, 'w') as text_file:
1938+
text_file.write(str(model))
1939+
19091940
# Solve model.
19101941
solver = cp_model.CpSolver()
1911-
solver.parameters.log_search_progress = True # not minimize_drivers
1912-
solver.parameters.num_search_workers = 8
1942+
if FLAGS.params:
1943+
text_format.Parse(FLAGS.params, solver.parameters)
1944+
19131945
status = solver.Solve(model)
19141946

19151947
if status != cp_model.OPTIMAL and status != cp_model.FEASIBLE:
@@ -1929,7 +1961,7 @@ def bus_driver_scheduling(minimize_drivers, max_num_drivers):
19291961

19301962
first = True
19311963
for s in range(num_shifts):
1932-
shift = SAMPLE_SHIFTS[s]
1964+
shift = shifts[s]
19331965

19341966
if not solver.BooleanValue(performed[d, s]):
19351967
continue
@@ -1939,18 +1971,22 @@ def bus_driver_scheduling(minimize_drivers, max_num_drivers):
19391971
# no_break_driving which was reinitialized in that case.
19401972
if solver.Value(no_break_driving[d, s]) == shift[5] and not first:
19411973
print(' **break**')
1942-
print(' shift ', shift[0], ':', shift[1], "-", shift[2])
1974+
print(' shift ', shift[0], ':', shift[1], '-', shift[2])
19431975
first = False
19441976

19451977
return int(solver.ObjectiveValue())
19461978

19471979

1948-
def optimize_bus_driver_allocation():
1980+
def main(_):
19491981
"""Optimize the bus driver allocation in two passes."""
19501982
print('----------- first pass: minimize the number of drivers')
19511983
num_drivers = bus_driver_scheduling(True, -1)
1952-
print('----------- second pass: minimize the sum of working times')
1953-
bus_driver_scheduling(False, num_drivers)
1984+
if num_drivers == -1:
1985+
print('no solution found, skipping the final step')
1986+
else:
1987+
print('----------- second pass: minimize the sum of working times')
1988+
bus_driver_scheduling(False, num_drivers)
19541989

19551990

1956-
optimize_bus_driver_allocation()
1991+
if __name__ == '__main__':
1992+
app.run(main)

‎examples/python/chemical_balance_lp.py‎

Lines changed: 0 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -17,8 +17,6 @@
1717
# Furthermore, if one color is an a group, at least k items with this color must
1818
# be in that group.
1919

20-
from __future__ import print_function
21-
from __future__ import division
2220

2321
from ortools.linear_solver import pywraplp
2422

‎examples/python/chemical_balance_sat.py‎

Lines changed: 0 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -17,8 +17,6 @@
1717
# Furthermore, if one color is an a group, at least k items with this color must
1818
# be in that group.
1919

20-
from __future__ import print_function
21-
from __future__ import division
2220

2321
from ortools.sat.python import cp_model
2422
import math

‎examples/python/clustering_sat.py‎

Lines changed: 0 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -12,8 +12,6 @@
1212
# limitations under the License.
1313
"""Cluster 40 cities in 4 equal groups to minimize sum of crossed distances."""
1414

15-
from __future__ import print_function
16-
from __future__ import division
1715

1816
from ortools.sat.python import cp_model
1917

0 commit comments

Comments
 (0)