Mixed integer programming

03.01.2020, 10:58	Elvis	Auf diesen Beitrag antworten »
Mixed integer programming Weiß jemand, ob man mit LPSOLVE den üblichen Ansatz zur Lösung von Sudokus mit binären Variablen realisieren kann ? Ich bin ziemlich sicher, dass mein Modell richtig ist, aber der Branch and Bound Algorithmus findet kein Ende. Von XPRESS war ich gewohnt, dass das Problem nach 5 Sekunden erledigt war, bei LPSOLVE ist nach 12 Stunden noch nichts sinnvolles passiert. Die Maschine frisst nur Strom aber tut nichts. Falls es jemand per Hand versuchen möchte, hier ist das Problem, und ich habe keine Geduld mehr. Es ist leicht abweichend zu Sudoku, denn die eingefärbten Bereiche ersetzen die 9 Unterquadrate. Zeilen, Spalten und Bereiche sollen jeweils die Zahlen von 1 bis 9 genau einmal enthalten. (Ich habe mir schon einen Wolf gerechnet und komme nicht weiter.)
23.01.2020, 13:04	Elvis	Auf diesen Beitrag antworten »
Problem gelöst. Weil ich keinen akzeptablen Optimierer finden konnte, habe ich das ganz normale Sudoku und dieses Extraspiel in Excel-VBA programmiert. Geht rattenschnell und kommt zuverlässig zu einer Lösung. Normale Probleme sind in wenigen Sekunden gelöst. Wenn "zu viele" Felder leer sind (z.B. hier nur 8 Felder vorbesetzt), dauert es länger, weil ich alternative Verzweigungen durchsuche und nicht wirklich intelligente Heuristiken eingebaut habe.
27.01.2020, 12:17	Ulrich Ruhnau	Auf diesen Beitrag antworten »
Würdest Du dein Excel-Sheet mal anhängen? Mich interessiert Dein Programm. Wie schließt Du überschüssige Möglichkeiten aus? Im übrigen ist mit die Lösung des Rätsels auch per Bleistift gelungen. Die Zahlen in einer Zeile müssen nur zyklisch vertausch werden um auf die darüber liegende Zeile zu kommen. Die unterste Zeile lautet: 4 2 1 7 6 9 8 5 3. Sonst spiele ich nicht Sudoku.
27.01.2020, 13:03	Elvis	Auf diesen Beitrag antworten »
Leere Felder werden mit den Ziffern 1 bis 9 besetzt, dann wird ausgehend von eindeutig besetzten Feldern alles in Zeile, Spalte, Block gelöscht, was den Ziffern von eindeutig besetzten Feldern entspricht (Sub Eliminieren). Ein minimal>1 besetztes Feld wird mehrfach kopiert (Sub Verzweigen) und über die dann eindeutig besetzten Felder eliminiert. Im "Turm" stapeln sich die noch zu bearbeitenden Tableaus, im "Keller" wird eliminiert (die Daleks lassen grüßen). Vor dem Programmstart müssen die benannten Zellen "Block" und "Feld" auf dem Sudoku oder dem Extraspiel stehen links oben. Wenn eine Lösung gefunden wurde wird diese ausgegeben und das Programm geht auf STOP. Das Programm erhebt keinen Anspruch auf Eleganz oder Professionalität, es sollte nur funktionieren. Wer etwas daran auszusetzen hat, darf es besser machen. (Ich war mal Fortran-Programmierer, deshalb bestehen meine VBA-Programme hauptsächlich aus for...next-Schleifen über i,j,k,l,n,p,q).

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »