0

This is continuation of this thread. I am coding MILP using Gurobi in Python where the objective is to maximize the rewards while ensuring the distance constraint is not violated.

I am however getting solution is infeasible. I tried the IIS but it still didnt help because it only shows the constraint that is being violated but not the solution.

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
  • computing IIS leads to this message "Cannot compute IIS on a feasible model"
    – gfdsal
    Oct 22, 2019 at 20:03

1 Answer 1

1

You forgot to call the optimize function after update

opt_model.ModelSense = grb.GRB.MAXIMIZE
opt_model.setObjective(objective)
opt_model.optimize() 
1
  • Allright it works now. I also want to know if you know what is the best way to show only nodes that resulted in solution so I dont have to look into all the nodes. Somehow the following code doesnt work and gets all the nodes selected = grb.tuplelist((i,j) for i,j in x_vars.keys() if x_vars.values() > 0.5)
    – gfdsal
    Oct 23, 2019 at 12:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.