Оптимизация суммы префиксов Gurobi - PullRequest
Новая
       29

Оптимизация суммы префиксов Gurobi

2 голосов
/ 25 апреля 2019

Рассмотрим следующую модель Gurobi: 

import gurobipy as gb
import numpy as np
N = 100
x = np.random.randint(10, high=2*N, size=N)
model = gb.Model("ACC")
amp_i_vars = model.addVars(N, vtype=gb.GRB.BINARY, name='ai')
model.setObjective(amp_i_vars.sum(*), gb.GRB.MINIMIZE)
model.addConstrs(gb.quicksum(amp_i_vars[i] for i in range(r+1)) <= x[r] 
                 for r in range(N), "SumConstr")

Когда мы, по сути, просто пытаемся заполнить ai как можно большим количеством битов, чтобы сумма битов до позиции r никогда не превышала x[r].

Мой вопрос заключается в том, является ли GurobiPy «умным» в том, как он проходит через ограничение, т.е. если он вычисляет сумму префикса ai или вместо этого фактически пересчитывает сумму для каждого r<N. Первый случай будет линейным временем, тогда как второй будет квадратичным. У меня есть LP, который содержит много таких сумм и ограничений, и мне интересно или нет, было бы лучше создать отдельную переменную для хранения суммы префикса каждой последовательности, чтобы предотвратить повторное вычисление GurobiPy суммы для каждого ограничения, но я не не хочу этого делать, если он уже достаточно умен.

Ответы [ 2 ]

1 голос
/ 26 апреля 2019

Ваша точная формулировка имеет O (N ^ 2) ненулей, так что вы застряли с O (N ^ 2) алгоритмом для ее построения. Вы можете избежать повторного создания выражения с помощью этого более процедурного цикла. 

import gurobipy as grb
import numpy as np
np.random.seed(10)

N = 5000
x = np.random.randint(10, high=2*N, size=N)
obj = -np.random.randint(10, high=2*N, size=N)
model = gb.Model("ACC")

# more interesting objective
amp_i_vars = model.addVars(N, vtype=grb.GRB.BINARY, name='ai', obj=obj)
model.update()
cum = grb.LinExpr()
for i, ai in amp_i_vars.items():
    cum += ai
    model.addConstr(cum <= x[i])
model.optimize()

Однако вы можете сформулировать эквивалентную модель с O (n) ненулевыми значениями, добавив параллельный список переменных, представляющих совокупную сумму, и используя повторение cum [i] = cum [i - 1] + x [i] . Это также приведет к модели, которая решает гораздо быстрее. 

import gurobipy as grb
import numpy as np
N = 5000
np.random.seed(10)
x = np.random.randint(10, high=2*N, size=N)
obj = -np.random.randint(10, high=2*N, size=N)
model = gb.Model("ACC")

# more interesting objective function
amp_i_vars = model.addVars(N, vtype=grb.GRB.BINARY, name='ai', obj=obj)
# since cum_vars are variables, use simple upper bound
cum_vars = model.addVars(N, vtype=grb.GRB.CONTINUOUS, name='cum', ub=x)

prev_cum = 0
for i, (ai, cum) in enumerate(zip(amp_i_vars.values(), cum_vars.values())):
    model.addConstr(cum == prev_cum + ai, name="sum_constr." + str(i))
    prev_cum = cum
model.optimize()

Для N = 5000 это решает за 0,5 секунды против 16 секунд для плотной модели.

0 голосов
/ 25 апреля 2019

На слое моделирования gurobipy будет не"умным" и применяет описанную замену, поэтому он будет генерировать ограничения одно за другим, каждый раз пересчитывая частичные суммы. Вы можете попробовать ввести вспомогательные переменные для этих частичных сумм, но я предполагаю, что накладные расходы на моделирование " немой »метод становится заметным только в том случае, если суммы действительно велики.

...