[Scip] Frage zu scipo_enfolp

[Tobias Achterberg]

Hallo Marco,

[for those non-Germans: sorry that this discussion is not in English. But since Marco
started in German, I will continue in German.]


die Antwort auf Deine Frage liegt in den Unterschieden von "Constraints" und "Rows" sowie
"enfolp" und "sepalp" callback.

Zunaechst musst Du Dir darueber klar werden, ob Du "Constraints" oder "Rows" separieren
willst. Ein "Constraint" ist ein abstraktes Objekt, fuer das das SCIP-Framework selbst
keinerlei Information ueber die Semantik hat. SCIP erhaelt im Wesentlichen nur einen
Pointer auf abstrakte Constraint-Daten und weiss, welcher Constraint Handler dafuer
zustaendig ist. Bedenke, dass auch alle mitgelieferten Constraint Handler wie der lineare
Constraint Handler nur "externe" Komponenten sind, die man so auch als "normal
sterblicher" SCIP-User haette implementieren koennen.

Eine "Row" hingegen ist eine Zeile der LP-Relaxierung, fuer die SCIP alle Informationen
verwaltet. Im Normalfall will man daher "Rows" separieren, da man ja direkt Zeilen in die
LP-Relaxierung bringen will. Der Umweg ueber lineare Constraints (um dann vom linearen
Constraint Handler die "Rows" in das LP eintragen zu lassen) ist etwas umstaendlich und
fuehrt auch zu den von Dir beschriebenen Effekten. Ich erklaere kurz, was passiert:

1. Das (leere) LP wird geloest. Die Loesung ist (bei Minimierung und nicht-negativer
Zielfunktion) der Nullvektor.
2. In der Separierungs-Phase passiert nichts, da der Constraint Handler fuer das einzige
Constraint (Deiner) keinen "sepalp" Callback hat.
3. Nun wird im Enforcement Dein Constraint Handler aufgerufen, der die Loesung als
verletzt erklaert, in dem er ein (oder mehrere) lineare Constraints generiert. Dies sind
aber "nur" Constraints, die zunaechst mal noch nichts mit der LP Relaxierung zu tun haben.
4. Das Hinzufuegen von Constraints sollte in der Tat das nochmalige Loesen des LPs
ausloesen. Und da Du die "initial"- und "separate"-Flags gesetzt hast, sollte die
LP-Relaxierung des linearen Constraints (was einfach nur das Constraint selbst ist) auch
im LP landen. Moeglicherweise ist die "sepafreq" des linearen Constraint Handlers nicht
auf einem Wert, der die Separierung am aktuellen Knoten erlaubt. Dies ist z.B. in den
Default-Settings der Fall, wenn Du nicht mehr am Root-Knoten bist. Angenommen, das ist
tatsaechlich so, dann passiert also nichts und das LP bleibt weiterhin leer.
5. Dein LP-Enforcement kommt zuerst; der lineare Constraint Handler war noch gar nicht
dran. Du findest dasselbe verletzte Constraint nochmal, gibst CONSADDED zurueck, die
Enforcement-Loop wird abgebrochen, der lineare Constraint Handler kommt immernoch nicht
dran, und Du hast eine Endlosschleife.

Falls das Problem nicht das in 4. beschriebene ist, so wird Dir das Hinzufuegen von

#define SCIP_DEBUG

ganz am Anfang von src/scip/solve.c eine detaillierte Ausgabe produzieren, was SCIP so
alles treibt. Vielleicht kannst Du dadurch herausfinden, was schieflaeuft.

Ich glaube, was Du eigentlich tun willst ist das Separieren von "Rows" in der
"sepalp"-Methode. Da solltest Du natuerlich auch nicht nur eine "Row" hinzufuegen, sondern
gleich viele verletzte Zeilen.
Im Wesentlichen kann man sagen, der "sepalp"-Call dient dazu, stark verletzte Rows zu
separieren, die man effizient finden kann. Der "enfolp"-Call sollte im Wesentlichen nur
einen Zulaessigkeits-Test machen und nur im Notfall weitere "Rows" oder auch "Constraints"
hinzufuegen.

Eine nuetzliche Vorgehensweise fuer Dich koennte folgende sein:
- Im sepalp-Callback separierst Du alles, was sich schnell finden laesst. Du kannst die
Suche abbrechen, wenn Du eine bestimmte Anzahl an Cuts gefunden hast.
- Du setzt Deine "enfoprio" auf < 0, so dass Du erst nach dem integrality constraint
handler drankommst. Das fuehrt dazu, dass Du Dir nur im Enforcement nur noch ganzzahlige
Loesungen angucken musst. In diesem Fall gibt es haeufig deutlich schnellere Algorithmen
auf Graphen; z.B. koennte die Loesung Kanten auswaehlen, und Du musst jetzt nur noch per
Tiefensuche Kreise in dem induzierten Graphen finden. Die verletzen Cuts solltest Du
trotzdem als "Rows" hinzufuegen.
- Du implementierst optional noch eine geeignete Domain Propagation im "consprop"-Callback.


Wenn Du zu faul bist, die Propagierung zu implementieren, dann kannst Du natuerlich doch
wieder dazu zurueckgehen, Constraints anstatt Rows zu separieren. In diesem Fall wuerde
dann der Propagierer des linearen Constraint Handlers zumindest die Propagierung der
erzeugten linearen Constraints uebernehmen. Da Dein Constraint Handler aber das Gesamtbild
kennt, solltest Du in der Lage sein, eine viel effizientere und auch staerkere
Propagierung zu implementieren. Insgesamt ist aber natuerlich die Propagierung fuer die
Korrektheit des Algorithmus nicht notwendig. Sie kann aber deutliche
Performance-Steigerungen bringen.


Gruss,

Tobias


Marco Rügen wrote:
> Hi,
> 
> ich benutze Scip 1.1.0/Soplex1.4.0 um ein Binary Linear Program zu lösen.
> 
> Das besondere an meinem Problem ist, dass ich Constraints nicht im 
> vorraus hinzufügen möchte sondern erst wenn die bestimmte Ungeleichungen 
> verletzt wurden.
> Ich möchte also ein Minimierungproblem lösen, dass zunächst keine 
> Constraints enthält.
> 
> Was ich getan habe:
> 
> Einen (und nur den einen) Constraint handler implementiert:
> 
> ConshdlrTriangles(
>       )
>       : ObjConshdlr("triangles", "Graph cluster triangles",
>          -1000000, 2, 1, -1, -1, -1, 0,
>          FALSE, FALSE, FALSE, TRUE)
> 
> So hat der Constraint Handler für das Constraint enforcement die höchste 
> Priorität und der Constraint Handler für den Feasibility check die 
> zweithöchste.
> 
> Was ich denke, dass SCIP nun tut:
> 
> SCIP relaxiert zunächst die Binary constraints und löst das LP.
> Mit dieser LP Lösung ruft Scip die Callback function scip_enfolp meines 
> constraint handlers auf.
> In dieser Funktion überprüfe ich, ob eine der Ungleichungen nicht 
> erfüllt wurde. Falls nicht füge ich dem Problem die entsprechenden 
> Constraints hinzu.
> Habe ich neue Constraints hinzugefügt, setze ich das *resut argument auf 
> den Wert SCIP_CONSADDED.
> 
> Jetzt löst SCIP hoffentlich das LP nochmal (weil es ja neue Constraints 
> gibt).
> Wird scip_enfolp aber das nächste mal aufgerufen, so verletzt die 
> aktuelle LP solution immer noch Ungleichungen, für die ich bereits 
> vorher Constraints hinzugefügt habe.
> 
> Wo liegt das Problem?
> 
> 
> Nochmal was ich eigentlich tun will:
> Constraints hinzufügen gleich nachdem SCIP für den jeweils bisherigen 
> Satz an Constraints eine valide LP Lösung gefunden hat.
> 
> Vielen Dank,
> Marco
> 
> Zur Information:
> 
> Bsp. füge ich für die Ungleichung x1+x2-x3<=1 das Constraint 
> folgendermaßen hinzu:
> SCIP_CONS* cons1;
> SCIP_CALL_EXC(SCIPcreateConsLinear(scip, & cons1, 
> string(string(x1->name)+x2->name+x3->name+"_1").c_str(), 0, NULL, NULL, 
> -SCIPinfinity(scip), 1, TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, 
> FALSE, FALSE, FALSE));
>     
> SCIP_CALL_EXC(SCIPaddCoefLinear(scip, cons1, x1,  1.0));
> SCIP_CALL_EXC(SCIPaddCoefLinear(scip, cons1, x2,  1.0));
> SCIP_CALL_EXC(SCIPaddCoefLinear(scip, cons1, x3, -1.0));
> SCIP_CALL_EXC(SCIPaddCons(scip, cons1));
> _______________________________________________
> Scip mailing list
> Scip at zib.de
> http://listserv.zib.de/mailman/listinfo/scip