• Optymalizacja liczb całkowitych

Liniowe problemy z optymalizacją, które wymagają, aby niektóre zmienne były liczbami całkowitymi, to mieszane programy całkowite.

Zmienne te mogą wystąpić na kilka sposobów:

  • Zmienne liczby całkowite reprezentujące liczbę elementów, takich jak samochody czy telewizory, a problem polega na tym, by określić, ile sztuk każdego produktu wyprodukować, aby zmaksymalizować zysk.
    Takie problemy można zwykle skonfigurować jako standardowe problemy z optymalizacją liniową, z dodatkowym wymaganiem, aby zmienne muszą być liczbami całkowitymi. Przykład tego rodzaju problemu znajdziesz w następnej sekcji.

  • Zmienne logiczne, które reprezentują decyzje za pomocą wartości 0–1.
    Przeanalizujmy problem, który obejmuje przypisywanie pracowników do zadań (patrz Cesja). Aby skonfigurować taki problem, możesz zdefiniować zmienne logiczne xi,j, które mają wartość 1, jeśli instancja robocza i jest przypisana do zadania j, lub 0 w innym przypadku.

Jeśli chcesz się dowiedzieć czegoś więcej o optymalizacji liczb całkowitych, polecamy książkę kucharską Moska dotyczącą modelowania.

Narzędzia,

Google oferuje kilka sposobów rozwiązywania problemów z MIP:

Którego rozwiązania mam użyć?

Nie ma jednolitej reguły, która pozwoli Ci zdecydować, czy użyć rozwiązania MIP, czy rozwiązania CP-SAT. W przybliżeniu:

  • Rozwiązania MIP lepiej sprawdzają się w przypadku zadań, które można skonfigurować jako standardowy tag strony docelowej, ale z dowolnymi zmiennymi całkowitymi, jak w pierwszym przykładzie powyżej.
  • Rozwiązanie CP-SAT lepiej sprawdza się w przypadku problemów, w których większość zmiennych jest wartością logiczną, jak w drugim przykładzie powyżej.

W przypadku typowych adresów MIP ze zmiennymi całkowitymi i logicznymi często nie ma wyraźnej różnicy w szybkości między 2 rozwiązaniami, więc wybór możesz wybrać według osobistych preferencji.

Przykłady rozwiązań MIP i CP-SAT znajdziesz w sekcji Rozwiązywanie problemów z projektem i innych sekcjach projektu.

Innym sposobem na rozwiązanie problemów z programowaniem liczb całkowitych jest użycie rozwiązania przepływu sieci.
Przykład znajdziesz w sekcji Przypisanie jako problem z minimalnym przepływem kosztów.
W przypadku problemu, który można skonfigurować jako przepływ sieci, narzędzie do rozwiązywania problemów minimalnych kosztów może być szybsze niż rozwiązanie MIP lub CP-SAT. Jednak nie wszystkie MIP można skonfigurować w ten sposób.