Нарушение ограничения для линейного целочисленного программирования в Python Gurobi - PullRequest
Новая
       99

Нарушение ограничения для линейного целочисленного программирования в Python Gurobi

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

Я пытаюсь реализовать LIP в Gurobi, но каким-то образом нарушаются ограничения, связанные с одним ребром в узле и одним ребром вне узла. Ниже приведены уравнения ( Я не копирую уравнения точно в промежутках пределов суммирования, поэтому его (i, j) 0 - N на данный момент, однако ограничение не должно нарушаться независимо от )

enter image description here

Таким образом, нижнее уравнение просто утверждает, что должен быть один край, входящий и выходящий из вершины или узла. Тем не менее, в следующем коде я добавил это ограничение, но каким-то образом оно нарушается в результате.

Я исчерпал себя, пытаясь выяснить, в чем может быть проблема 

import gurobipy as grb
import math
n = 4

set_I = range(0, n)
set_J = range(0, n)


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")


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))
# <= Constraint (Distance)

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

# <= Constraint (coming in to node and going out should be 1 each)
for i in range(n):
  opt_model.addConstr(grb.quicksum(x_vars[i,j] for j in range(n)) <= 1)
opt_model.update()

# <= objective is to maximize

objective = grb.quicksum(x_vars[i,j]
                         for i in set_I
                         for j in set_J)
opt_model.ModelSense = grb.GRB.MAXIMIZE
opt_model.setObjective(objective)
opt_model.update()

opt_model.optimize()
solution = opt_model.getAttr('x', x_vars )

print solution

import pandas as pd
opt_df = pd.DataFrame.from_dict(x_vars, orient="index",
                                columns = ["variable_object"])
opt_df.index = pd.MultiIndex.from_tuples(opt_df.index,
                               names=["column_i", "column_j"])
opt_df.reset_index(inplace=True)
# Gurobi
opt_df["solution_value"] = opt_df["variable_object"].apply(lambda item: item.X)

print opt_df

1 Ответ

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

Похоже, вы не добавили ограничение равное

в соответствии с вашим кодом, это должно быть что-то вроде 

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

, и на самом деле ваша целевая функция должна выглядеть следующим образомкод по вашему уравнению 

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