Metodo Branch and Bound

[Desirio]

Buonasera, vorrei una delucidazione sul metodo branch and bound applicato ai problemi di PLI e in particolare ai problemi di PL01 ovvero quei problemi in cui le variabili possono assumere solo valori binari su {0,1}.

Il problema che sto cercando di risolvere è il seguente e vorrei sapere se il ragionamento alla base della risposta è corretto o meno.

- Se a una iterazione del metodo B&B generica seleziono un problema aperto (da risolvere) in quella iterazione posso o chiudere il problema oppure dividere il problema in due sottoproblemi.

Quindi osservazioni

1) sicuramente al termine della prima iterazione ho o zero problemi aperti nella lista oppure 2: 3 non possono esserci sicuramente essendo di PL01.

2) Se ho zero problemi non entro neanche nella seconda iterazione. Supponiamo di averne 2 di problemi aperti {P1, P2}.
Ne seleziono uno e lo risolvo, ad esempio P1.
Posso chiuderlo o dividerlo in due sottoproblemi. Se lo chiudo al termine della seconda ho un problema aperto, se lo divido al termine della seconda ho 3 sottoproblemi aperti.

Come è possibile che al termine della seconda iterazione abbia 2 sottoproblemi aperti?
Dove sto sbagliando?
Grazie