CODEWITHSUNDEEP
pythonlinear-programminggurobi
David Oliver
David Oliver

Reputation: 127

Minimize the max value in Gurobi optimaztion

I am developing a model to solve a MIP problem using gurobi and python. The problem involves travel times over a set of predefined routes. One of the objective functions I am trying to realize is to minimize the maximum travel time for the selected routes. A mathematical representation of this is: min f = max(Dij * Zij)
where D is the travel time for each route ij and Z is the assignment variable indicating whether route ij is part of the solution, so that if the route is not selected then the expression evaluates to 0. What is the best way to model this in Gurobi for python?

Upvotes: 5

Views: 7052

Answers (1)

Ram Narasimhan
Ram Narasimhan

Reputation: 22506

Here's how you can set up a min max constraint in MIP/Gurobi.

Idea: First, create a new variable called max_distance. This is what the MIP will try to minimize.

Now add constraints, one for each (i,j) combination, such that:

  dist[i][j] * Z[i][j] <= max_distance

The above will take care of pushing max_distance to be at least as large as the largest Dij. And the objective function will make max_distance as small as possible.

To make the code that follows work, you have to do two things.

  1. Add in your actual constraints that 'select' the preferred set of Zij
  2. Replace my random values with your actual distances.

Gurobi (Python) Code for MinMax

Here's how you'd approach it in Gurobi (Python). I don't have Gurobi installed, so this hasn't been verified. It is to illustrate the idea of min max.

import sys
import math
import random
import itertools
from gurobipy import *
    
#Create 10 points (nodes i and j) with random values. 
# replace this with your distances.    
N=10
random.seed(1)
points = [(random.randint(0,100),random.randint(0,100)) for i in range(n)]
dist = {(i,j) :
    math.sqrt(sum((points[i][k]-points[j][k])**2 for k in range(2)))
    for i in range(n) for j in range(i)}

m = Model()

# minimize 1 * maxDistvar
mdvar = m.addVar(lb=0.0, obj=1.0, GRB.CONTINUOUS, "maxDistvar")   

# Create the Zij variables
vars = tupledict()
for i,j in dist.keys():
    vars[i,j] = m.addVar(vtype=GRB.BINARY,
                        name='z[%d,%d]'%(i,j))

#set up limit max distance constraints
# Maxdistvar is greater than or equal to the largest dist[i, j]
for i in range(N):
    for j in range(i):
        m.addConstr(vars[i,j]*dist[i, j] <= mdvar, 'maxDist[%d,%d]'%(i,j))

# Also, add your constraints that 'select' \
# certain Zij to be 0 or 1 based on other criteria
# These will decide if Zij is part of your solution.
    
# Solve
m.optimize()

And print out the selected Zij's. Hope that helps.

Upvotes: 5

Related Questions