Python CPLEX: Max Flow/Min Cut

README_CPLEX_Max-Flow_Min-Cut.md.md

Max Flow/Min Cut Using CPLEX in Python

This program uses the Python cplex library to solve a max flow/min cut problem. More information on max flow/min cut is available in the Wikipedia article.
The basic idea is to assign flow to each edge such that no edge's flow exceeds that edge's capacity.

Be aware that a linear program may not always be the most efficient technique for solving max flow/min cut. This gist is intended more as a demonstration of how to use CPLEX in Python.

The graph I used is:

    /---> a -2->e-
   /      ^       \
  1       5        3
 /        |         \
s --9---> b --4----> t
 \        ^        /
 9.5      2       /
   \----> c -3.5-

Main items to take note of include:

• Edges: These are float variables constrained between 0 and that edge's capacity inclusive.
• Constraints: Conservation of flow into/out of each vertex.
• Objective: Maximize flow out of s or into t. This example uses the former.

Note: Tested with Python 3.6.5 & cplex version 12.8.0.0

cplex_max_flow_min_cut.py

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()