Newer
Older
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
from __future__ import print_function
from ortools.linear_solver import pywraplp
import numpy as np
import support
import sys
import os
def lower_bound(instance):
# Instantiate a mixed-integer solver, naming it SolveIntegerProblem.
solver = pywraplp.Solver('SolveIntegerProblem',pywraplp.Solver.CBC_MIXED_INTEGER_PROGRAMMING)
n = instance.n.value
#capacity
capacity = instance.capacity.value
#number of vehicles
K = instance.number_of_vehicles
# variable definitions.
X = {(i,j):0 for i in range(n) for j in range(i) }
for i in range(n):
for j in range(i):
if j==0:
x = solver.IntVar(0.0,2.0,str(i)+":"+str(j))
elif instance.x[i,j].fixed == True:
x = solver.IntVar(instance.x[i,j].value,instance.x[i,j].value,str(i)+":"+str(j))
else:
x = solver.IntVar(0.0,1.0,str(i)+":"+str(j))
X[(i,j)] = x
# degree constraints
C_deg = []
for count in range(n):
constraint = solver.Constraint(2 if count>0 else 2*K,2 if count>0 else 2*K)
for k in X.keys():
i,j = k
if i==count or j==count:
constraint.SetCoefficient(X[k],1)
else:
constraint.SetCoefficient(X[k],0)
C_deg.append(constraint)
# capacity constraints
C_cap = []
# Objective
objective = solver.Objective()
for k in X.keys():
objective.SetCoefficient(X[k],instance.costs[k])
objective.SetMinimization()
"""Solve the problem and print the solution."""
try:
result_status = solver.Solve()
except:
raise NameError("pas de résultat")
#assert result_status == pywraplp.Solver.OPTIMAL
#assert solver.VerifySolution(1e-7, True)
# The objective value of the solution.
return solver.Objective().Value()