Решение не возможно в линейном программировании в Python Gurobi - PullRequest
Новая
       82

Решение не возможно в линейном программировании в Python Gurobi

0 голосов
/ 22 октября 2019

Это продолжение этой темы . Я кодирую MILP с использованием Gurobi в Python, где цель состоит в том, чтобы максимизировать вознаграждение, гарантируя, что ограничение расстояния не нарушается.

Я, однако, получить решение невозможно. Я попробовал IIS, но он все равно не помог, потому что он показывает только ограничение, которое нарушается, но не решение. 

import random
import gurobipy as grb
import math

n = 4
Distance = 50000000

def distance(points, i, j):
  dx = points[i][0] - points[j][0]
  dy = points[i][1] - points[j][1]
  return math.sqrt(dx*dx + dy*dy)

random.seed(1)
points = []
for i in range(n):
  points.append((random.randint(0,100),random.randint(0,100)))
opt_model = grb.Model(name="MILP Model")

# <= Variables
x_vars = {}
for i in range(n):
   for j in range(n):
     x_vars[i,j] = opt_model.addVar(vtype=grb.GRB.BINARY,
                          name='e'+str(i)+'_'+str(j))
u={}
for i in range(1,n):
    u[i]=opt_model.addVar(vtype=grb.GRB.INTEGER,
                          name='e'+str(i))

# <= Constraint (Mandatory Edges and excluding vertexes) Eq(1)

opt_model.addConstr((grb.quicksum(x_vars[1,j] for j in range(1,n)))  == 1)
opt_model.addConstr((grb.quicksum(x_vars[i,n-1] for i in range(n-1)))  == 1)
opt_model.addConstr((grb.quicksum(x_vars[i,i] for i in range(n-1)))  == 0)
# <= Constraint (Distance) Eq(3)

for i in range(n-1):
  opt_model.addConstr(grb.quicksum(x_vars[i,j]*distance(points, i, j) for j in range(1,n)) <= Distance)

# <= Constraint (Equality & Single edge in and out) Eq(2)

for k in range(1, n-1):
  opt_model.addConstr(grb.quicksum(x_vars[i,k] for i in range(n-1))
                      == grb.quicksum(x_vars[k,j] for j in range(1, n)) <=1)

# <= Constraint (Subtour elimination) Eq(4) Eq(5)

for i in range(1,n):
  opt_model.addConstr(2 <= u[i] <= n)

for i in range(1,n):
    for j in range(1,n):
        opt_model.addConstr((u[i] - u[j] +1 <= (n-1)*(1-x_vars[j,i])))

# <= objective (maximize) Eq(1)

objective = grb.quicksum(x_vars[i,j]
                         for i in range(1, n-1)
                         for j in range(1, n))

opt_model.ModelSense = grb.GRB.MAXIMIZE
opt_model.setObjective(objective)
opt_model.update()
solution = opt_model.getAttr('x', x_vars )
print solution

1 Ответ

1 голос
/ 23 октября 2019

Вы забыли вызвать функцию оптимизации после обновления 

opt_model.ModelSense = grb.GRB.MAXIMIZE
opt_model.setObjective(objective)
opt_model.optimize()
...