Generowanie interesujących problemów optymalizacji kombinatorycznej

Prowadzę kurs meta-heurystyki i muszę wygenerować ciekawe przykłady klasycznych problemów kombinatorycznych dla projektu semestralnego. Skupmy się na TSP. Zajmujemy się wykresami wymiarów$200$i większe. Próbowałem oczywiście wygenerować wykres z macierzą kosztów z wartościami pobranymi z losowego$U(0,1)$i odkrył, że (zgodnie z oczekiwaniami) histogram kosztu ścieżki (sporządzony przez próbkowanie wielu losowych ścieżek) ma bardzo wąski rozkład normalny ($\mu$ jest $~100$ ale $\sigma$ wynosi około $4$). Moim zdaniem oznacza to, że problem jest bardzo łatwy, ponieważ większość losowych ścieżek będzie poniżej średniej, a ścieżka kosztu minimalnego jest bardzo zbliżona do ścieżki losowej.

Wypróbowałem więc następujące podejście: Po wygenerowaniu $U(0,1)$-macierz, weź długi losowy spacer po wykresie i losowo (Bernoulli z $p=0.5$) podwoić lub zmniejszyć o połowę wartość krawędzi. To zwykle obniża wszystkie wartości, ostatecznie osiągając zero, ale jeśli zrobię odpowiednią liczbę kroków, mogę uzyskać rozkład z$\mu$ na około $2$ i $\sigma$ na około $1$.

Moje pytanie brzmi: czy to w ogóle dobra definicja interesującego problemu? Idealnie chciałbym mieć instancję, która jest wysoce multimodalna (dla najpopularniejszych funkcji sąsiedztwa) i która ma bardzo niewiele ścieżek w pobliżu wartości minimalnej, tak aby większość przypadkowych rozwiązań była bardzo daleka od optymalnej. Drugim pytaniem jest, biorąc pod uwagę ten opis, jak mogę wygenerować instancje o takich cechach?

Jedno ogólne podejście do generowania trudniejszych instancji jest następujące:

• Zacznij od przypadkowego wystąpienia problemu.
• Osadź „ukryty backdoor”: losowo wybierz dobre rozwiązanie (takie, które prawdopodobnie będzie znacznie lepsze niż jakiekolwiek rozwiązanie, które już istnieje) i zmodyfikuj instancję problemu, aby wymusić osadzenie tego rozwiązania w instancji problemu.

Na przykład w przypadku TSP możesz wykonać następujące czynności. Wygeneruj przypadkową instancję problemu, wybierając losową$U(0,1)$macierz kosztów. Następnie dostosuj wystąpienie problemu, aby ukryć w nim znacznie lepsze rozwiązanie: losowo wybierz wycieczkę, która odwiedza każdy wierzchołek dokładnie raz, i zmniejsz wagi krawędzi na tej trasie (np. Wygeneruj go losowo z$U(0,c)$ gdzie $c<1$; zmniejszyć istniejącą wagę; lub zmodyfikuj istniejącą krawędź z pewnym stałym prawdopodobieństwem). Ta procedura dostosowywania zapewnia, że ​​optymalnym rozwiązaniem będzie, z dużym prawdopodobieństwem, ta wybrana trasa specjalna. Jeśli masz szczęście i wybierzesz rozsądne osadzenie, nie będzie łatwo rozpoznać, gdzie ukryłeś specjalne rozwiązanie.

To podejście wywodzi się z ogólnych pomysłów w kryptografii, w których chcemy tworzyć jednokierunkowe problemy z zapadnią: gdzie problem jest trudny do rozwiązania bez znajomości tajnej zapadni, ale przy wiedzy o tajnej zapadni problem staje się bardzo łatwy. Było wiele prób osadzenia tajnych zapadni w różnych trudnych problemach (przy jednoczesnym zachowaniu twardości problemu, nawet po dodaniu zapadni), z różnym powodzeniem. Ale to ogólne podejście wydaje się być wykonalne dla twoich celów.

Powstałe problemy mogą być trudne , ale czy będą interesujące z praktycznego punktu widzenia? Nie wiem Bije mnie Wyglądają mi dość sztucznie, ale co ja wiem?

Jeśli twoim głównym celem jest wybranie wystąpień problemów, które są praktycznie istotne i reprezentatywne dla rzeczywistych zastosowań TSP, moja propozycja byłaby zupełnie inna. Zamiast tego zacznij od zbadania rzeczywistych aplikacji TSP, a następnie poszukaj reprezentatywnych wystąpień tych problemów i przekonwertuj je na odpowiadające im wystąpienia TSP - dzięki czemu pracujesz z wystąpieniami problemów wywodzącymi się z rzeczywistego problemu.

podejście, które często daje wysoką kontrolę nad naturą rozwiązań, polega na konwersji z jednego problemu NP na kompletny problem. teraz definiujesz „interesujące” w swoim pytaniu w sposób statystyczny, ale innym fajnym podejściem jest użycie klasycznych problemów z tej dziedziny. moim ulubionym jest faktoring / SAT. znalezienie „gładkich” liczb z wieloma czynnikami lub liczb pierwszych z tylko dwoma „czynnikami” (jednym i liczbą pierwszą) jest banalne. utwórz instancję SAT, aby rozwiązać faktorowanie, a rozwiązania są czynnikami (w rzeczywistości permutacjami czynników, ale także takich, których nie trudno policzyć z wyprzedzeniem).

zgodnie z tym podejściem istnieje naturalna definicja „interesujących” - twardych przypadków, których nie można rozwiązać w czasie P. i gwarantuje się, że takie podejście spowoduje powstanie trudnych instancji dla faktoryzacji liczb nieładnych, w przeciwnym razie rozwiązałoby to najbardziej otwarte pytanie w teorii złożoności, tj. twardość faktorowania .

następnie ewentualnie przekonwertuj na swój problem, w tym przypadku TSP. aby wypełnić tę odpowiedź, byłoby miło mieć bezpośrednią konwersję SAT do TSP, myślę, że tam są, ale ich nie znam. oto kilka odniesień do faktoringu do SAT w tym pytaniu: zmniejszenie problemu faktoryzacji liczb całkowitych do problemu całkowitego NP

jeśli nie lubisz faktorowania, nadal może być preferowane utworzenie instancji w SAT z różnych powodów. możesz zacząć od losowych instancji SAT dostrojonych do środka w łatwym i trudnym punkcie przejścia itp. lub możesz pracować z twardych instancji DIMACS , generowanych przez społeczność. lub utwórz inne logiczne „programy” w SAT.