代写代考 COMP3530 Gurobi demo_ Vertex Cover – cscodehelp代写

Gurobi demo_ Vertex Cover
import networkx as nx
import gurobipy as gb
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¶
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(),
vtype=gb.GRB.CONTINUOUS if relax else gb.GRB.BINARY,
# 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¶
G = nx.Graph()
G.add_edges_from([(1, 2), (2, 3), (3, 1)])
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
# 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
m.printAttr(‘X’)
Variable X
————————-
x[1] 0.5
x[2] 0.5
x[3] 0.5
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%
m.printAttr(‘X’)
Variable X
————————-
x[2] 1
x[3] 1
Random graph¶
G = nx.gnp_random_graph(150, 0.1)
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
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 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: GUB cover: 3 Zero half: 7 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%