Несколько решений при выполнении ILP

Question

В настоящее время я использую PuLP для решения проблемы максимизации. Он отлично работает, но я бы хотел получить N-лучшие решения вместо одного. Есть ли способ сделать это в PuLP или любом другом свободном/Python решении? Я играл с идеей просто случайного выбора некоторых переменных из оптимального решения и выбрасывания их и повторного запуска, но это похоже на общий взлом.

Answer 1

Так что я понял, как (по RTFM) получить несколько soutions. В моем коде я по существу есть:

number_unique = 1 # The number of variables that should be unique between runs 

model += objective 
model += constraint1 
model += constraint2 
model += constraint3 

for i in range(1,5): 
    model.solve() 
    selected_vars = [] 
    for p in vars: 
     if p_vars[p].value() != 0: 
      selected_vars.append(p) 
    print_results() 

    # Add a new constraint that the sum of all of the variables should 
    # not total up to what I'm looking for (effectively making unique solutions) 
    model += sum([p_vars[p] for p in selected_vars]) <= 10 - number_unique 

Это прекрасно работает, но я понял, что мне действительно нужно идти случайный маршрут. У меня есть 10 разных переменных, и, только выкинув пару из них, мои решения, как правило, имеют одинаковые взвешенные веса во всех перестановках (что и следовало ожидать).

Answer 2

Если ваша проблема быстро решена, вы можете попытаться ограничить цель сверху. Для нелогич-, если цель значение оптимального решения X, попытайтесь повторно запустить задачу с дополнительным ограничением:

problem += objective <= X - eps, "" 

где стадия восстановления eps зависит от знания проблемы.

Конечно, если вы просто слепаете в некотором смысле eps и получите решение, вы не знаете, является ли решение вторым лучшим, 10-м лучшим или 1000-м лучшим ... Но вы можете провести систематический поиск (двоичный, сетка) по параметру eps (если проблема очень быстро решена).