|
import cplex |
|
|
|
|
|
def _main(): |
|
r""" |
|
Flow network to be solved. |
|
|
|
/---> a -2-> e- |
|
1 5 \ |
|
/ | 3 |
|
s --9---> b --4----> t |
|
\ ^ / |
|
9.5 2 / |
|
\----> c -3.5- |
|
""" |
|
prob = cplex.Cplex() |
|
prob.set_problem_name("Max Flow/Min Cut") |
|
|
|
# PROBLEM TYPE OPTIONS |
|
# ============================= |
|
# Cplex.problem_type.LP |
|
# Cplex.problem_type.MILP |
|
# Cplex.problem_type.fixed_MILP |
|
# Cplex.problem_type.QP |
|
# Cplex.problem_type.MIQP |
|
# Cplex.problem_type.fixed_MIQP |
|
# Cplex.problem_type.QCP |
|
# Cplex.problem_type.MIQCP |
|
# ============================= |
|
prob.set_problem_type(cplex.Cplex.problem_type.LP) |
|
|
|
# We want to find a maximum of our objective function |
|
prob.objective.set_sense(prob.objective.sense.maximize) |
|
|
|
# Variable Names |
|
names = ["sa", "sb", "sc", "ae", "be", "bt", "cb", "ct", "et"] |
|
# Objective (linear) weights |
|
w_obj = [1.0, 1.0, 1.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0] |
|
# Lower bounds. Since these are all zero, we could simply not pass them in as |
|
# all zeroes is the default. |
|
low_bnd = [0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0] |
|
# Upper bounds. The default here would be cplex.infinity, or 1e+20. |
|
upr_bnd = [1.0, 9.0, 9.5, 2.0, 5.0, 4.0, 2.0, 3.5, 3.0] |
|
prob.variables.add(names=names, obj=w_obj, lb=low_bnd, ub=upr_bnd) |
|
|
|
constraints = [] |
|
# 1.0 * sa - 1.0 * ae |
|
constraints.append([["sa", "ae"], [1.0, -1.0]]) |
|
constraints.append([["sb", "cb", "bt", "be"], [1.0, 1.0, -1.0, -1.0]]) |
|
constraints.append([["sc", "cb", "ct"], [1.0, -1.0, -1.0]]) |
|
constraints.append([["ae", "be", "et"], [1.0, 1.0, -1.0]]) |
|
|
|
# Name the constraints |
|
constraint_names = ["c" + str(i) for i, _ in enumerate(constraints)] |
|
|
|
# So far we haven't added a right hand side, so we do that now. Note that the |
|
# first entry in this list corresponds to the first constraint, and so-on. |
|
rhs = [0] * len(constraints) |
|
|
|
# We need to enter the senses of the constraints. That is, we need to tell Cplex |
|
# whether each constrains should be treated as an upper-limit (≤, denoted "L" |
|
# for less-than), a lower limit (≥, denoted "G" for greater than) or an equality |
|
# (=, denoted "E" for equality) |
|
constraint_senses = ["E"] * len(constraints) |
|
|
|
# And add the constraints |
|
prob.linear_constraints.add(names=constraint_names, |
|
lin_expr=constraints, |
|
senses=constraint_senses, |
|
rhs=rhs) |
|
# Solve the problem |
|
print("Problem Type: %s" % prob.problem_type[prob.get_problem_type()]) |
|
prob.solve() |
|
print("Solution result is: %s" % prob.solution.get_status_string()) |
|
print(prob.solution.get_values()) |
|
|
|
|
|
if __name__ == "__main__": |
|
_main() |