Python CPLEX: Minimum Vertex Cover

README_CPLEX_Vertex_Cover.md

Vertex Cover Using CPLEX in Python

This program uses the Python cplex library to solve a vertex cover problem. More information on Vertex Cover is available in the Wikipedia article. The basic idea of the problem is to select the smallest set of vertices such that each edge in the graph is incident on at least one selected vertex. Solving vertex cover is NP-Hard.

For this example, I used the toy graph below.

      g
    /   \
  /       \
a --- b --- e
| \   |   / |
|   \ |  /  |
c --- d --- f

Main items to take note of include:

• Variables: Set of vertices. I used integer values and constrained them to {0,1}, but binary variables would have worked here.
• Constraints: Each edge is a constraint and is the sum of the variables for the verticies on that edge.
• Objective: Minimum the sum of the vertex values.

Note: Tested with Python 3.6.5 & cplex version 12.8.0.0

cplex_min_vertex_cover.py

import cplex


def _main():
    r"""
    Example Undirected Graph:

          g
        /   \
      /       \
    a --- b --- e
    | \   |   / |
    |   \ |  /  |
    c --- d --- f
    """
    prob = cplex.Cplex()
    prob.set_problem_name("Minimum Vertex Cover")

    # 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.minimize)

    # Variable Names
    names = ["a", "b", "c", "d", "e", "f", "g"]

    # Objective (linear) weights
    w_obj = [1, 1, 1, 1, 1, 1, 1]
    # 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]
    # Upper bounds. The default here would be cplex.infinity, or 1e+20.
    upr_bnd = [1, 1, 1, 1, 1, 1, 1]
    prob.variables.add(names=names, obj=w_obj, lb=low_bnd, ub=upr_bnd)

    # How to set the variable types
    # Must be AFTER adding the variablers
    #
    # Option #1: Single variable name (or number) with type
    # prob.variables.set_types("0", prob.variables.type.continuous)
    # Option #2: List of tuples in the form (var_name, type)
    # prob.variables.set_types([("1", prob.variables.type.integer), \
    #                           ("2", prob.variables.type.binary), \
    #                           ("3", prob.variables.type.semi_continuous), \
    #                           ("4", prob.variables.type.semi_integer)])
    #
    # Vertex cover requires only integers
    all_int = [(var, prob.variables.type.integer) for var in names]
    prob.variables.set_types(all_int)

    constraints = []
    # Edge ab
    constraints.append([["a", "b"], [1, 1]])
    # Edge ac
    constraints.append([["a", "c"], [1, 1]])
    # Edge ad
    constraints.append([["a", "d"], [1, 1]])
    constraints.append([["a", "g"], [1, 1]])
    constraints.append([["b", "d"], [1, 1]])
    constraints.append([["b", "e"], [1, 1]])
    constraints.append([["c", "d"], [1, 1]])
    constraints.append([["d", "e"], [1, 1]])
    constraints.append([["d", "f"], [1, 1]])
    constraints.append([["e", "g"], [1, 1]])
    constraints.append([["f", "e"], [1, 1]])

    # Constraint names
    constraint_names = ["".join(x[0]) for x in constraints]

    # Each edge must have at least one vertex
    rhs = [1] * 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 = ["G"] * 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()