2021-05-03 12:11:39 +02:00
|
|
|
#!/usr/bin/env python3
|
2025-01-10 11:33:35 +01:00
|
|
|
# Copyright 2010-2025 Google LLC
|
2011-11-03 10:27:53 +00:00
|
|
|
# Licensed under the Apache License, Version 2.0 (the "License");
|
|
|
|
|
# you may not use this file except in compliance with the License.
|
|
|
|
|
# You may obtain a copy of the License at
|
|
|
|
|
#
|
|
|
|
|
# http://www.apache.org/licenses/LICENSE-2.0
|
|
|
|
|
#
|
|
|
|
|
# Unless required by applicable law or agreed to in writing, software
|
|
|
|
|
# distributed under the License is distributed on an "AS IS" BASIS,
|
|
|
|
|
# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
|
|
|
|
|
# See the License for the specific language governing permissions and
|
|
|
|
|
# limitations under the License.
|
2023-07-01 06:06:53 +02:00
|
|
|
|
2011-11-03 10:27:53 +00:00
|
|
|
"""Integer programming examples that show how to use the APIs."""
|
|
|
|
|
|
2013-12-24 11:35:01 +00:00
|
|
|
from ortools.linear_solver import pywraplp
|
2011-11-03 10:27:53 +00:00
|
|
|
|
|
|
|
|
|
2020-06-24 18:11:12 +02:00
|
|
|
def Announce(solver, api_type):
|
2023-07-01 06:06:53 +02:00
|
|
|
print(
|
|
|
|
|
"---- Integer programming example with " + solver + " (" + api_type + ") -----"
|
|
|
|
|
)
|
2020-06-24 18:11:12 +02:00
|
|
|
|
|
|
|
|
|
2011-12-05 14:15:20 +00:00
|
|
|
def RunIntegerExampleNaturalLanguageAPI(optimization_problem_type):
|
2018-11-11 09:39:59 +01:00
|
|
|
"""Example of simple integer program with natural language API."""
|
2020-06-24 18:11:12 +02:00
|
|
|
|
2020-08-18 17:16:10 +02:00
|
|
|
solver = pywraplp.Solver.CreateSolver(optimization_problem_type)
|
2020-06-24 18:11:12 +02:00
|
|
|
if not solver:
|
|
|
|
|
return
|
|
|
|
|
|
2023-07-01 06:06:53 +02:00
|
|
|
Announce(optimization_problem_type, "natural language API")
|
2020-06-24 18:11:12 +02:00
|
|
|
|
2018-11-11 09:39:59 +01:00
|
|
|
infinity = solver.infinity()
|
|
|
|
|
# x1 and x2 are integer non-negative variables.
|
2023-07-01 06:06:53 +02:00
|
|
|
x1 = solver.IntVar(0.0, infinity, "x1")
|
|
|
|
|
x2 = solver.IntVar(0.0, infinity, "x2")
|
2011-11-03 10:27:53 +00:00
|
|
|
|
2018-11-11 09:39:59 +01:00
|
|
|
solver.Minimize(x1 + 2 * x2)
|
|
|
|
|
solver.Add(3 * x1 + 2 * x2 >= 17)
|
2011-11-03 10:27:53 +00:00
|
|
|
|
2018-11-11 09:39:59 +01:00
|
|
|
SolveAndPrint(solver, [x1, x2])
|
2011-11-03 10:27:53 +00:00
|
|
|
|
|
|
|
|
|
|
|
|
|
def RunIntegerExampleCppStyleAPI(optimization_problem_type):
|
2018-11-11 09:39:59 +01:00
|
|
|
"""Example of simple integer program with the C++ style API."""
|
2020-08-18 17:16:10 +02:00
|
|
|
solver = pywraplp.Solver.CreateSolver(optimization_problem_type)
|
2020-06-24 18:11:12 +02:00
|
|
|
if not solver:
|
|
|
|
|
return
|
|
|
|
|
|
2023-07-01 06:06:53 +02:00
|
|
|
Announce(optimization_problem_type, "C++ style API")
|
2020-06-24 18:11:12 +02:00
|
|
|
|
2018-11-11 09:39:59 +01:00
|
|
|
infinity = solver.infinity()
|
|
|
|
|
# x1 and x2 are integer non-negative variables.
|
2023-07-01 06:06:53 +02:00
|
|
|
x1 = solver.IntVar(0.0, infinity, "x1")
|
|
|
|
|
x2 = solver.IntVar(0.0, infinity, "x2")
|
2011-11-03 10:27:53 +00:00
|
|
|
|
2018-11-11 09:39:59 +01:00
|
|
|
# Minimize x1 + 2 * x2.
|
|
|
|
|
objective = solver.Objective()
|
|
|
|
|
objective.SetCoefficient(x1, 1)
|
|
|
|
|
objective.SetCoefficient(x2, 2)
|
2011-11-03 10:27:53 +00:00
|
|
|
|
2018-11-11 09:39:59 +01:00
|
|
|
# 2 * x2 + 3 * x1 >= 17.
|
|
|
|
|
ct = solver.Constraint(17, infinity)
|
|
|
|
|
ct.SetCoefficient(x1, 3)
|
|
|
|
|
ct.SetCoefficient(x2, 2)
|
2011-11-03 10:27:53 +00:00
|
|
|
|
2018-11-11 09:39:59 +01:00
|
|
|
SolveAndPrint(solver, [x1, x2])
|
2011-11-03 10:27:53 +00:00
|
|
|
|
|
|
|
|
|
|
|
|
|
def SolveAndPrint(solver, variable_list):
|
2018-11-11 09:39:59 +01:00
|
|
|
"""Solve the problem and print the solution."""
|
2023-07-01 06:06:53 +02:00
|
|
|
print("Number of variables = %d" % solver.NumVariables())
|
|
|
|
|
print("Number of constraints = %d" % solver.NumConstraints())
|
2011-11-03 10:27:53 +00:00
|
|
|
|
2018-11-11 09:39:59 +01:00
|
|
|
result_status = solver.Solve()
|
2011-11-03 10:27:53 +00:00
|
|
|
|
2018-11-11 09:39:59 +01:00
|
|
|
# The problem has an optimal solution.
|
|
|
|
|
assert result_status == pywraplp.Solver.OPTIMAL
|
2011-11-03 10:27:53 +00:00
|
|
|
|
2018-11-11 09:39:59 +01:00
|
|
|
# The solution looks legit (when using solvers others than
|
|
|
|
|
# GLOP_LINEAR_PROGRAMMING, verifying the solution is highly recommended!).
|
|
|
|
|
assert solver.VerifySolution(1e-7, True)
|
2014-07-09 11:17:29 +00:00
|
|
|
|
2023-07-01 06:06:53 +02:00
|
|
|
print("Problem solved in %f milliseconds" % solver.wall_time())
|
2011-11-03 10:27:53 +00:00
|
|
|
|
2018-11-11 09:39:59 +01:00
|
|
|
# The objective value of the solution.
|
2023-07-01 06:06:53 +02:00
|
|
|
print("Optimal objective value = %f" % solver.Objective().Value())
|
2011-11-03 10:27:53 +00:00
|
|
|
|
2018-11-11 09:39:59 +01:00
|
|
|
# The value of each variable in the solution.
|
|
|
|
|
for variable in variable_list:
|
2023-07-01 06:06:53 +02:00
|
|
|
print("%s = %f" % (variable.name(), variable.solution_value()))
|
2011-11-03 10:27:53 +00:00
|
|
|
|
2023-07-01 06:06:53 +02:00
|
|
|
print("Advanced usage:")
|
|
|
|
|
print("Problem solved in %d branch-and-bound nodes" % solver.nodes())
|
2011-11-03 10:27:53 +00:00
|
|
|
|
|
|
|
|
|
2011-12-05 14:15:20 +00:00
|
|
|
def RunAllIntegerExampleNaturalLanguageAPI():
|
2023-07-01 06:06:53 +02:00
|
|
|
RunIntegerExampleNaturalLanguageAPI("GLPK")
|
|
|
|
|
# Disabling due to ASAN errors with CBC.
|
|
|
|
|
# RunIntegerExampleNaturalLanguageAPI('CBC')
|
|
|
|
|
RunIntegerExampleNaturalLanguageAPI("SCIP")
|
|
|
|
|
RunIntegerExampleNaturalLanguageAPI("SAT")
|
2023-11-13 15:29:08 +01:00
|
|
|
RunIntegerExampleNaturalLanguageAPI("XPRESS")
|
2011-11-03 10:27:53 +00:00
|
|
|
|
|
|
|
|
|
|
|
|
|
def RunAllIntegerExampleCppStyleAPI():
|
2023-07-01 06:06:53 +02:00
|
|
|
RunIntegerExampleCppStyleAPI("GLPK")
|
|
|
|
|
# Disabling due to ASAN errors with CBC.
|
|
|
|
|
# RunIntegerExampleCppStyleAPI('CBC')
|
|
|
|
|
RunIntegerExampleCppStyleAPI("SCIP")
|
|
|
|
|
RunIntegerExampleCppStyleAPI("SAT")
|
2023-11-13 15:29:08 +01:00
|
|
|
RunIntegerExampleCppStyleAPI("XPRESS")
|
2011-11-03 10:27:53 +00:00
|
|
|
|
|
|
|
|
|
2015-12-09 14:56:52 +01:00
|
|
|
def main():
|
2018-11-11 09:39:59 +01:00
|
|
|
RunAllIntegerExampleNaturalLanguageAPI()
|
|
|
|
|
RunAllIntegerExampleCppStyleAPI()
|
2011-11-03 10:27:53 +00:00
|
|
|
|
|
|
|
|
|
2023-07-01 06:06:53 +02:00
|
|
|
if __name__ == "__main__":
|
2018-11-11 09:39:59 +01:00
|
|
|
main()
|
