Python Gurobi 中线性整数规划的约束违反

Question

我正在尝试在 Gurobi 中实现 LIP，但不知何故违反了与单边进入节点和单边离开节点相关的约束。以下是方程式（我并没有完全根据求和限制复制方程式，所以现在它的 (i,j) 0 - N，但是无论如何都不应该违反约束 ）

所以下面的等式只是说明应该有一条边进入和离开顶点或节点。然而，在下面的代码中，我添加了这个约束，但结果却以某种方式违反了它。

我费尽了脑力想弄清楚可能是什么问题

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

Answer 1

你好像没有加上equal的约束

根据您的代码，它应该类似于

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 函数应该类似于以下代码

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

Python Gurobi 中线性整数规划的约束违反

Constraint violation for Linear Integer Programming in Python Gurobi

python

linear-programming

gurobi

integer-programming