Wiele rozwiązań podczas wykonywania ILP

Question

Aktualnie używam PuLP, aby rozwiązać problem z maksymalizacją. Działa dobrze, ale chciałbym móc uzyskać najlepsze rozwiązania, zamiast tylko jednego. Czy istnieje sposób, aby to zrobić w PuLP lub dowolnym innym wolnym/Python rozwiązanie? Wpadłem na pomysł, że losowo wybieram niektóre zmienne z optymalnego rozwiązania i wyrzucam je i ponownie uruchamiam, ale wydaje się, że to total hack.

Answer 1

Więc wymyśliłem, jak (przez RTFM), aby uzyskać wiele wymiarów. W moim kodzie zasadniczo mam:

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 

Działa to świetnie, ale zdałem sobie sprawę, że naprawdę muszę wybrać losową trasę. Mam 10 różnych zmiennych i przez wyrzucenie tylko kilku z nich, moje rozwiązania mają te same ważone vary we wszystkich permutacjach (czego można się spodziewać).

Answer 2

Jeśli twój problem jest szybki do rozwiązania, możesz spróbować ograniczyć cel z góry krok po kroku. Dla examle, jeśli celem wartość optymalnego rozwiązania jest X, spróbuj ponownie uruchomić problem z dodatkowym ograniczeniem:

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

gdzie etap redukcji eps zależy od wiedzy o problemie.

Oczywiście, jeśli wybierzesz po prostu eps na ślepo i otrzymasz rozwiązanie, nie wiesz, czy to rozwiązanie jest 2. najlepszym, dziesiątym najlepszym czy 1000-tym najlepszym ... Ale możesz przeprowadzić systematyczne wyszukiwanie (binarny, siatka) na parametrze eps (jeśli problem jest naprawdę szybki do rozwiązania).