Проблема с Gurobi - Добавление usercuts с функцией обратного вызова - PullRequest
Новая
       21

Проблема с Gurobi - Добавление usercuts с функцией обратного вызова

1 голос
/ 26 февраля 2020

В настоящее время я работаю над составом MILP, который я хочу решить, используя Gurobi с подходом ветвления и разреза. Моя модель представляет собой вариант классической c проблемы с доставкой и доставкой во времени Windows (PDPTW), для которой определены несколько классов допустимых неравенств. Когда запускается решатель ветвей и границ, я хочу добавить эти неравенства (т.е. я хочу добавить сокращения), если выполняются определенные условия в текущем узле. Моя проблема заключается в следующем:

Мои переменные определены как словари, что облегчает их использование при формулировании ограничений, потому что я легко могу использовать их исходную индексацию. Пример того, как я определяю переменные, приведен ниже 

tauOD = {}
# Start- End-Service time of trucks
for i in range(0,Nt):
    tauOD[i,0]=model.addVar(lb=0.0, ub=truckODTime[i][0],
                             vtype=GRB.CONTINUOUS,name='tauOD[%s,%s]'%(i,0))
    tauOD[i,1]=model.addVar(lb=0.0, ub=truckODTime[i][1],
                             vtype=GRB.CONTINUOUS,name='tauOD[%s,%s]'%(i,1))

Как только моя модель определена в терминах переменных, ограничений и функции стоимости, в классической c задаче ветвления и ограничения я бы просто используйте model.optimize (), чтобы начать процесс. В этом случае я использую команду model.optimize (my_callback), где my_callback - это функция обратного вызова, которую я определил для добавления вырезов. Моя проблема в том, что функция обратного вызова по некоторым причинам не любит переменные модели, определенные как словари. Единственный обходной путь, который я нашел: Это всего лишь фиктивный пример, показывающий, что я могу добавлять разрезы с использованием переменных порядка в моем решении, а не их индексации. Например, я хотел бы иметь возможность написать ограничение внутри моего обратного вызова как

x [0,3,0] + x [0,5,0] <= 1 </p>

, но единственное, что я могу сделать, это написать

this_Sol [123] + this_Sol [125] <= 1 (при условии, что x [0,3,0] является 124-й переменной моего вектора решения, а x [0,5,0] - 126-е место). Хотя знание порядка переменных выполнимо, поскольку оно зависит от того, как я их создаю при настройке модели, это гораздо более сложный процесс (и подверженный ошибкам), а не возможность использовать индексы, как я делаю при определении исходные ограничения моей модели (см. пример ниже): </p> 

###################
### CONSTRAINTS ###
###################
# For each truck, one active connection from origin depot
for i in range(0,Nt):
    thisLHS = LinExpr()
    for j in range(0,sigma):
        thisLHS += x[0,j+1,i]
    thisLHS += x[0,2*sigma+1,i]
    model.addConstr(lhs=thisLHS, sense=GRB.EQUAL, rhs=1,
                            name='C1_'+str(i))

Кто-нибудь из вас сталкивался с подобной проблемой? Мой друг сказал мне, что Gurobi по некоторым причинам не любит переменные, определенные как словари внутри функции обратного вызова, но я не знаю, как это обойти. Любая помощь будет принята с благодарностью. Спасибо!

Алессандро

1 Ответ

0 голосов
/ 27 февраля 2020

Вы должны сделать копию переменных по их диктату.

Чтобы получить индекс переменной, вы также должны сделать копию списков и индексов.

Попробуйте это: 

model._I = model.I
model._J = model.J
model._K = model.K
model._x = model.x

Вам нужны списки индексов тезисов, чтобы вы могли Можно l oop каждая целевая переменная x, чтобы проверить некоторые условия. Как и при написании обычного ограничения для вашей модели.

Затем внутри вашего обратного вызова вы можете выполнить итерации индекса: 

def mycallback(model,where):
    if where == GRB.Callback.MIPNODE:

        x = model.cbGetSolution(model._x)

        for i in model._I:
            if sum([x[i,j,k] for j in model._J for k in model._K]) > 1:
                Add_the_cut()
...