最小化Gurobi优化中的最大值

Question

我正在开发一个模型来使用 gurobi 和 python 来解决 MIP 问题。该问题涉及一组预定义路线的旅行时间。我试图实现的 objective 功能之一是最小化所选路线的最长行程时间。这个的数学表示是： min f = max(Dij * Zij)
其中 D 是每条路线 ij 的行程时间，Z 是分配变量，指示路线 ij 是否是解决方案的一部分，因此，如果未选择路线，则表达式的计算结果为 0。在中建模的最佳方法是什么python 的 Gurobi?

Answer 1

以下是在 MIP/Gurobi 中设置最小最大约束的方法。

想法：首先，创建一个名为max_distance.的新变量，这是 MIP 将尝试最小化的变量。

现在添加约束，每个 (i,j) 组合一个，这样：

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

以上将负责将 max_distance 推到至少与最大的 Dij 一样大。 objective 函数将使 max_distance 尽可能小。

要使后面的代码正常工作，您必须做两件事。

在您的实际约束中添加 'select' Zij 的首选集
用你的实际距离替换我的随机值。

Gurobi (Python) MinMax

代码

以下是您在 Gurobi (Python) 中的处理方式。我没有安装 Gurobi，因此尚未验证。就是为了说明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()

并打印出选中的Zij's。希望对您有所帮助。

最小化Gurobi优化中的最大值

Minimize the max value in Gurobi optimaztion

python

linear-programming

gurobi

Gurobi (Python) MinMax