Минимизируйте максимальное значение в Gurobi optimaztion - PullRequest
Новая
       46

Минимизируйте максимальное значение в Gurobi optimaztion

0 голосов
/ 09 июня 2018

Я разрабатываю модель для решения проблемы MIP с использованием gurobi и python.Проблема связана с временем в пути по набору заранее определенных маршрутов.Одна из целевых функций, которые я пытаюсь реализовать, заключается в минимизации максимального времени в пути для выбранных маршрутов.Математическое представление этого: min f = max (Dij * Zij)
, где D - время в пути для каждого маршрута ij, а Z - переменная назначения, указывающая, является ли маршрут ij частью решения, так что если маршрутне выбирается, тогда выражение оценивается как 0. Как лучше всего смоделировать это в Gurobi для python?

1 Ответ

0 голосов
/ 10 июня 2018

Вот как вы можете установить ограничение min max в MIP / Gurobi.

Идея : Сначала создайте новую переменную с именем max_distance. Это то, что MIP будет пытатьсяминимизировать.

Теперь добавьте ограничения, по одному для каждой (i, j) комбинации, так что: 

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

Выше будет заботиться о том, чтобы значение max_distance было как минимум таким же большимкак самый большой Dij.И целевая функция сделает max_distance настолько малой, насколько это возможно.

Чтобы код, который следует за кодом, работал, вы должны сделать две вещи.1. Добавьте фактические ограничения, которые «выбирают» предпочтительный набор Zij 2. Замените мои случайные значения фактическими расстояниями.

Код Gurobi (Python) для MinMax

Вот как вы 'Я подхожу к нему в Gurobi (Python).У меня не установлен Gurobi, так что это не было проверено.Он должен проиллюстрировать идею минимума макс. 

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 = model.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()

и распечатать выбранный Зидж.Надеюсь, это поможет.

...