Constraint violation for Linear Integer Programming in Python Gurobi

Question

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

1tan 1tan · Accepted Answer · 2019-10-22T00:50:50

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)

Constraint violation for Linear Integer Programming in Python Gurobi

1 Answers