Gurobi demo_ Vertex Cover
In [1]:
import networkx as nx
import gurobipy as gb
In [2]:
gb.setParam(‘Method’, 1)
Restricted license – for non-production use only – expires 2022-01-13
Changed value of parameter Method to 1
Prev: -1 Min: -1 Max: 5 Default: -1
Modeling function¶
In [6]:
def vertex_cover(G, relax=False):
“Solve IP or LP relaxation for vertex cover problem defined by G.”
model = gb.Model(“vertex cover”)
# 1. Create LP variables: x[u] for each vertex u
x = model.addVars(
G.nodes(),
lb=0.0,
ub=1.0,
vtype=gb.GRB.CONTINUOUS if relax else gb.GRB.BINARY,
name=’x’
)
# 2. Create LP constraints: x[u] + x[v] >=1 for each edge (u,v)
for (u, v) in G.edges():
model.addConstr(
x[u] + x[v] >= 1
)
# 3. Create LP objective: sum_u x_u
model.setObjective(
gb.quicksum(x),
gb.GRB.MINIMIZE
)
# 4. Optimize
model.optimize()
return model
Evaluation¶
Cycle of size 3¶
In [7]:
G = nx.Graph()
G.add_edges_from([(1, 2), (2, 3), (3, 1)])
In [8]:
m = vertex_cover(G, relax=True)
Gurobi Optimizer version 9.1.2 build v9.1.2rc0 (mac64)
Thread count: 4 physical cores, 8 logical processors, using up to 8 threads
Optimize a model with 3 rows, 3 columns and 6 nonzeros
Model fingerprint: 0x7616b8b6
Coefficient statistics:
Matrix range [1e+00, 1e+00]
Objective range [1e+00, 1e+00]
Bounds range [1e+00, 1e+00]
RHS range [1e+00, 1e+00]
Presolve time: 0.02s
Presolved: 3 rows, 3 columns, 6 nonzeros
Iteration Objective Primal Inf. Dual Inf. Time
0 0.0000000e+00 3.000000e+00 0.000000e+00 0s
3 1.5000000e+00 0.000000e+00 0.000000e+00 0s
Solved in 3 iterations and 0.03 seconds
Optimal objective 1.500000000e+00
In [9]:
# print out solution
for x in m.getVars():
print(“{} = {}”.format(x.VarName, x.X))
x[1] = 0.5
x[2] = 0.5
x[3] = 0.5
In [10]:
m.printAttr(‘X’)
Variable X
————————-
x[1] 0.5
x[2] 0.5
x[3] 0.5
In [11]:
m = vertex_cover(G, relax=False)
Gurobi Optimizer version 9.1.2 build v9.1.2rc0 (mac64)
Thread count: 4 physical cores, 8 logical processors, using up to 8 threads
Optimize a model with 3 rows, 3 columns and 6 nonzeros
Model fingerprint: 0x41300915
Variable types: 0 continuous, 3 integer (3 binary)
Coefficient statistics:
Matrix range [1e+00, 1e+00]
Objective range [1e+00, 1e+00]
Bounds range [1e+00, 1e+00]
RHS range [1e+00, 1e+00]
Found heuristic solution: objective 2.0000000
Presolve removed 3 rows and 3 columns
Presolve time: 0.00s
Presolve: All rows and columns removed
Explored 0 nodes (0 simplex iterations) in 0.02 seconds
Thread count was 1 (of 8 available processors)
Solution count 1: 2
Optimal solution found (tolerance 1.00e-04)
Best objective 2.000000000000e+00, best bound 2.000000000000e+00, gap 0.0000%
In [12]:
m.printAttr(‘X’)
Variable X
————————-
x[2] 1
x[3] 1
Random graph¶
In [30]:
G = nx.gnp_random_graph(150, 0.1)
In [31]:
m = vertex_cover(G, relax=True)
Gurobi Optimizer version 9.1.2 build v9.1.2rc0 (mac64)
Thread count: 4 physical cores, 8 logical processors, using up to 8 threads
Optimize a model with 1087 rows, 150 columns and 2174 nonzeros
Model fingerprint: 0x142bf84d
Coefficient statistics:
Matrix range [1e+00, 1e+00]
Objective range [1e+00, 1e+00]
Bounds range [1e+00, 1e+00]
RHS range [1e+00, 1e+00]
Presolve time: 0.03s
Presolved: 1087 rows, 150 columns, 2174 nonzeros
Iteration Objective Primal Inf. Dual Inf. Time
0 0.0000000e+00 1.087000e+03 0.000000e+00 0s
169 7.5000000e+01 0.000000e+00 0.000000e+00 0s
Solved in 169 iterations and 0.04 seconds
Optimal objective 7.500000000e+01
In [26]:
for x in m.getVars():
if 0 < x.X < 1:
print("{} = {}".format(x.VarName, x.X))
x[0] = 0.5
x[1] = 0.5
x[2] = 0.5
x[3] = 0.5
x[4] = 0.5
x[5] = 0.5
x[6] = 0.5
x[7] = 0.5
x[8] = 0.5
x[9] = 0.5
x[10] = 0.5
x[11] = 0.5
x[12] = 0.5
x[13] = 0.5
x[14] = 0.5
x[15] = 0.5
x[16] = 0.5
x[17] = 0.5
x[18] = 0.5
x[19] = 0.5
x[20] = 0.5
x[21] = 0.5
x[22] = 0.5
x[23] = 0.5
x[24] = 0.5
x[25] = 0.5
x[26] = 0.5
x[27] = 0.5
x[28] = 0.5
x[29] = 0.5
x[30] = 0.5
x[31] = 0.5
x[32] = 0.5
x[33] = 0.5
x[34] = 0.5
x[35] = 0.5
x[36] = 0.5
x[37] = 0.5
x[38] = 0.5
x[39] = 0.5
x[40] = 0.5
x[41] = 0.5
x[42] = 0.5
x[43] = 0.5
x[44] = 0.5
x[45] = 0.5
x[46] = 0.5
x[47] = 0.5
x[48] = 0.5
x[49] = 0.5
x[50] = 0.5
x[51] = 0.5
x[52] = 0.5
x[53] = 0.5
x[54] = 0.5
x[55] = 0.5
x[56] = 0.5
x[57] = 0.5
x[58] = 0.5
x[59] = 0.5
x[60] = 0.5
x[61] = 0.5
x[62] = 0.5
x[63] = 0.5
x[64] = 0.5
x[65] = 0.5
x[66] = 0.5
x[67] = 0.5
x[68] = 0.5
x[69] = 0.5
x[70] = 0.5
x[71] = 0.5
x[72] = 0.5
x[73] = 0.5
x[74] = 0.5
x[75] = 0.5
x[76] = 0.5
x[77] = 0.5
x[78] = 0.5
x[79] = 0.5
x[80] = 0.5
x[81] = 0.5
x[82] = 0.5
x[83] = 0.5
x[84] = 0.5
x[85] = 0.5
x[86] = 0.5
x[87] = 0.5
x[88] = 0.5
x[89] = 0.5
x[90] = 0.5
x[91] = 0.5
x[92] = 0.5
x[93] = 0.5
x[94] = 0.5
x[95] = 0.5
x[96] = 0.5
x[97] = 0.5
x[98] = 0.5
x[99] = 0.5
In [32]:
m = vertex_cover(G, relax=False)
Gurobi Optimizer version 9.1.2 build v9.1.2rc0 (mac64)
Thread count: 4 physical cores, 8 logical processors, using up to 8 threads
Optimize a model with 1087 rows, 150 columns and 2174 nonzeros
Model fingerprint: 0x73eee736
Variable types: 0 continuous, 150 integer (150 binary)
Coefficient statistics:
Matrix range [1e+00, 1e+00]
Objective range [1e+00, 1e+00]
Bounds range [1e+00, 1e+00]
RHS range [1e+00, 1e+00]
Found heuristic solution: objective 120.0000000
Presolve removed 451 rows and 0 columns
Presolve time: 0.01s
Presolved: 636 rows, 150 columns, 1681 nonzeros
Variable types: 0 continuous, 150 integer (150 binary)
Root relaxation: objective 1.008745e+02, 487 iterations, 0.02 seconds
Nodes | Current Node | Objective Bounds | Work
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time
0 0 100.87454 0 147 120.00000 100.87454 15.9% - 0s
H 0 0 118.0000000 100.87454 14.5% - 0s
H 0 0 117.0000000 101.29767 13.4% - 0s
0 0 101.42147 0 149 117.00000 101.42147 13.3% - 0s
0 0 101.70637 0 149 117.00000 101.70637 13.1% - 0s
0 0 102.77085 0 149 117.00000 102.77085 12.2% - 0s
0 0 102.78276 0 149 117.00000 102.78276 12.2% - 0s
0 0 102.78276 0 149 117.00000 102.78276 12.2% - 0s
0 0 102.78276 0 149 117.00000 102.78276 12.2% - 0s
H 0 0 113.0000000 103.57941 8.34% - 0s
0 0 103.57941 0 149 113.00000 103.57941 8.34% - 0s
0 0 103.58000 0 149 113.00000 103.58000 8.34% - 0s
0 2 103.58000 0 149 113.00000 103.58000 8.34% - 0s
2179 789 106.93952 18 131 113.00000 106.93952 5.36% 48.6 5s
H 2525 873 112.0000000 106.93952 4.52% 51.5 5s
8772 1650 110.92000 35 93 112.00000 108.54545 3.08% 44.7 10s
Cutting planes:
Gomory: 1
Clique: 1
GUB cover: 3
Zero half: 7
RLT: 16
Explored 15731 nodes (627412 simplex iterations) in 12.73 seconds
Thread count was 8 (of 8 available processors)
Solution count 5: 112 113 117 ... 120
Optimal solution found (tolerance 1.00e-04)
Best objective 1.120000000000e+02, best bound 1.120000000000e+02, gap 0.0000%
In [ ]: