# CS作业代写 Gurobi demo_ Vertex Cover – cscodehelp代写

Gurobi demo_ Vertex Cover

In :

import networkx as nx
import gurobipy as gb

In :

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 :

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

G = nx.Graph()
G.add_edges_from([(1, 2), (2, 3), (3, 1)])

In :

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 :

# print out solution
for x in m.getVars():
print(“{} = {}”.format(x.VarName, x.X))

x = 0.5
x = 0.5
x = 0.5

In :

m.printAttr(‘X’)

Variable X
————————-
x 0.5
x 0.5
x 0.5

In :

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 :

m.printAttr(‘X’)

Variable X
————————-
x 1
x 1

Random graph¶

In :

G = nx.gnp_random_graph(150, 0.1)

In :

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 :

for x in m.getVars():
if 0 < x.X < 1: print("{} = {}".format(x.VarName, x.X)) x = 0.5 x = 0.5 x = 0.5 x = 0.5 x = 0.5 x = 0.5 x = 0.5 x = 0.5 x = 0.5 x = 0.5 x = 0.5 x = 0.5 x = 0.5 x = 0.5 x = 0.5 x = 0.5 x = 0.5 x = 0.5 x = 0.5 x = 0.5 x = 0.5 x = 0.5 x = 0.5 x = 0.5 x = 0.5 x = 0.5 x = 0.5 x = 0.5 x = 0.5 x = 0.5 x = 0.5 x = 0.5 x = 0.5 x = 0.5 x = 0.5 x = 0.5 x = 0.5 x = 0.5 x = 0.5 x = 0.5 x = 0.5 x = 0.5 x = 0.5 x = 0.5 x = 0.5 x = 0.5 x = 0.5 x = 0.5 x = 0.5 x = 0.5 x = 0.5 x = 0.5 x = 0.5 x = 0.5 x = 0.5 x = 0.5 x = 0.5 x = 0.5 x = 0.5 x = 0.5 x = 0.5 x = 0.5 x = 0.5 x = 0.5 x = 0.5 x = 0.5 x = 0.5 x = 0.5 x = 0.5 x = 0.5 x = 0.5 x = 0.5 x = 0.5 x = 0.5 x = 0.5 x = 0.5 x = 0.5 x = 0.5 x = 0.5 x = 0.5 x = 0.5 x = 0.5 x = 0.5 x = 0.5 x = 0.5 x = 0.5 x = 0.5 x = 0.5 x = 0.5 x = 0.5 x = 0.5 x = 0.5 x = 0.5 x = 0.5 x = 0.5 x = 0.5 x = 0.5 x = 0.5 x = 0.5 x = 0.5 In : 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 [ ]: