Začíname s YALMIPom: 06. Logická optimalizácia

Dnes si ukážeme, ako použiť YALMIP na riešenie problémov s binárnymi premennými.

Uvažujme nasledovný problém: ste hlavným architektom mesta, ktoré má 6 mestských častí (označíme ich písmenami A až F). Za úlohu máte postaviť minimálny počet požiarnych staníc (v každej časti môže byť max. jedna) tak, aby bola každá časť pokrytá požiarnikmi do 15 minút. Cestovné časy medzi jednotlivými mestskými časťami sú nasledovné:

Zadefinujme optimalizované premenné A, B, C, D, E, a F, ktoré budú mať hodnotu 1 ak v príslušnej časti postavíme stanicu a 0 v opačnom prípade. Keďže premenné nadobúdajú iba binárne hodnoty, na ich vytvorenie použijeme príkaz binvar:

binvar A B C D E F

Cieľom je minimalizovať počet postavených staníc, čo sa dá napísať v tvare

ucelovka = A + B + C + D + E + F;

Formulácia ohraničení si vyžaduje trochu uvažovania. Vezmime si prvý riadok tabuľky. Časť A bude pokrytá do 15 minút ak postavíme stanicu buď v časti A alebo v časti B (pre všetky ostatné umiestnenia je čas dojazdu vyšší ako požadovaných 15 minút). To môžeme zapísať v tvare

ohranicenia = [ true(A | B) ];

pričom A | B bude pravdivé vtedy a len vtedy, keď A alebo B (prípadne oboje zároveň) budú jednotkové. Ohraničenie používa príkaz true, ktorý vyžaduje, aby v ňom uvedený výrok (teda A | B) bol pravdivý.

Pokrytie druhej časti (riadok B tabuľky) bude zabezpečené, ak stanica bude buď v A (dojazd 10 minút), alebo v B (dojazd 0 minút), alebo v F (dojazd 10 minút):

ohranicenia = ohranicenia + [ true(A | B | F) ];

Aplikovaním rovnakého postupu na mestské časti C, D, E a F dostávame

ohranicenia = ohranicenia + [ true(C | D) ];     % cast C
ohranicenia = ohranicenia + [ true(C | D | E) ]; % cast D
ohranicenia = ohranicenia + [ true(D | E | F) ]; % cast E
ohranicenia = ohranicenia + [ true(B | E | F) ]; % cast F

S takto definovanými ohraničeniami a účelovou funkciou môžeme problém vyriešíť pomocou príkazu optimize:

info = optimize(ohranicenia, ucelovka)

yalmiptime: 0.3347
solvertime: 0.0040
      info: 'Successfully solved (GUROBI-GUROBI)'
   problem: 0

Optimálne hodnoty rozhodovacích premenných získame cez value:

value([A B C D E F])

ans =

 0     1     0     1     0     0

Ako vidíme, minimálny počet požiarnych staníc je 2 a majú byť postavené v mestských častiach B a D.

Hore uvedený postup však platí iba pre jednu konkrétnu maticu dojazdov. Uvažujme teraz všeobecný scenár, kde máme n mestských častí, pričom dojazdy medzi nimi sú v matici M. Minimálny čas dojazdu označíme ako tmin. Všeobecná formulácia bude nasledovná:

n = size(M, 1);    % pocet casti
x = binvar(1, n);  % optimalizovane premenne
ucelovka = sum(x); % minimalizuj pocet stanic
ohranicenia = [];
for i = 1:n
  % pre kazdu cast najdi kandidatov v dosahu
  kandidati = find(M(i, :) <= tmin);
  % pozadujeme, aby bola stanica aspon v jednej z kandidatskych casti
  ohranicenia = ohranicenia + [ true(or(x(kandidati))) ];
end
info = optimize(ohranicenia, ucelovka)
value(x)

Zdroj: http://www.doc.ic.ac.uk/~br/berc/integerprog.pdf