vertex_cover.py

from ortools.linear_solver import pywraplp

# A simple program that uses a SCIP solver to solve a Vertex Cover instance
def main():
    # Create the mip solver with the SCIP backend.
    solver = pywraplp.Solver.CreateSolver('SCIP')

    # Variables (Nodes)
    x1 = solver.IntVar(0, 1, 'x1')
    x2 = solver.IntVar(0, 1, 'x2')
    x3 = solver.IntVar(0, 1, 'x3')
    x4 = solver.IntVar(0, 1, 'x4')
    x5 = solver.IntVar(0, 1, 'x5')
    x6 = solver.IntVar(0, 1, 'x6')

    print('Number of variables/nodes =', solver.NumVariables())

    # Constraints (Edges)
    solver.Add(x1 + x2 >= 1.0)
    solver.Add(x1 + x3 >= 1.0)
    solver.Add(x2 + x3 >= 1.0)

    solver.Add(x2 + x4 >= 1.0)
    solver.Add(x2 + x5 >= 1.0)
    solver.Add(x2 + x6 >= 1.0)

    print('Number of constraints/edges =', solver.NumConstraints())

    # Maximize -x1-x2-x3-x4-x5-x6
    solver.Maximize(-x1-x2-x3-x4-x5-x6)

    status = solver.Solve()

    if status == pywraplp.Solver.OPTIMAL:
        print('Solution:')
        print('Objective value =', solver.Objective().Value())
        print('x1 =', x1.solution_value())
        print('x2 =', x2.solution_value())
        print('x3 =', x3.solution_value())
        print('x4 =', x4.solution_value())
        print('x5 =', x5.solution_value())
        print('x6 =', x6.solution_value())
    else:
        print('The problem does not have an optimal solution.')

    print('\nStatistics:')
    print('Problem solved in %f milliseconds' % solver.wall_time())
    print('Problem solved in %d iterations' % solver.iterations())
    print('Problem solved in %d branch-and-bound nodes' % solver.nodes())


if __name__ == '__main__':
    main()