Python Gurobi中线性整数编程的约束违反 [英] Constraint violation for Linear Integer Programming in Python Gurobi

问题描述

我正在尝试在Gurobi中实施LIP，但是某种程度上违反了与进入节点的单边和离开节点的单边有关的约束.以下是等式(我没有完全复制等式的总和极限，所以现在它的(i，j)0-N，但是无论如何都不应违反约束条件)

I am trying to implement LIP in Gurobi but somehow the constraints related to single edge into the node and single edge out of the node is being violated. The following are the equations (I am not copying the equations exactly interms of the summations limits so its (i,j) 0 - N for now, however the constraint should not be violated regardless )

因此，底部等式简单地指出应该有一条边进入并离开顶点或节点.但是，在下面的代码中，我添加了此约束，但是在某种程度上它在结果中被违反了.

So the bottom equation simply states that there should be one edge coming in and leaving the vertex or node. However in the following code I added this constraint but somehow it is getting violated in the result.

我已经筋疲力尽了，想找出可能是什么问题

I have quite exhausted my head trying to figure out what might be the issue

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

推荐答案

似乎您没有添加等于的约束

It seems like you did not add the constraint of equal

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

according to your code, it should be something like

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

实际上，根据方程式，目标函数应类似于以下代码

and actually, your objective function should be like the following code according to your equation

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

这篇关于Python Gurobi中线性整数编程的约束违反的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！