Problem bei der Lösung eines großen MIQP-Problems

Question

Ich löse bei jedem Schritt eines modellprädiktiven Steuerungsproblems ein MIQP-Optimierungsproblem in großem Maßstab. Die Problembeschreibung ist wie folgt.\begin{align} \min_{u} \quad (x_{k}&-x_\text{ref})^{T}Q(x_{k}-x_\text{ref}) + (P_{k}-P_{\text{ref},k})^{T}R(P_{k}-P_{\text{ref},k}) \\ \text{s.t. } x_{k+1}&=Ax_{k}+Bu_{k} \\ P_{k} &= \mathbb{I}^{T}u_{k}\\ u_{k} &\in \{0.25,0.50,0.75,1.0\}\\ \underline{x}&\leq x_{k}\leq \overline{x} \end{align} wo $Q$ und $R$ sind positiv definitiv, $\underline{x}$ und $\overline{x}$ repräsentieren die unteren und oberen Grenzen von $x$, $x_{ref}$ und $P_{ref}$ sind die Referenzwerte bei jedem Schritt $k$. Darüber hinaus,$P_{k} = \sum_{i} u_{k}^{i}$ Dies ist die Summe aller Entscheidungsvariablen im Zeitschritt $k$.

Das Problem, das ich habe, ist die Entscheidungsvariable $u$ ist in $\mathbb{R}^{1000}$Das Problem betrifft also eine große Anzahl von ganzzahligen Variablen, die nicht einmal binär sind.

Ich habe versucht, dieses Optimierungsproblem bei jeder Iteration mit Gurobi zu lösen, konnte es jedoch überhaupt nicht lösen. Danach kontaktierte ich das Gurobi- Supportcenter und versuchte auf der Grundlage ihrer Vorschläge, die Parameter ( MIPGap , MIPHeuristics ) zu optimieren , um zumindest eine praktikable Lösung zu finden. Aber es hat auch die Leistung der Aufgabe nicht verbessert. Auf der anderen Seite muss ich innerhalb von 60 Sekunden eine praktikable Lösung finden, die der realen Anwendung entspricht.

Ich würde mich sehr freuen, wenn mir jemand bei den folgenden Problemen helfen könnte.

1. Ist dieses Problem NP-schwer? Wenn ja, gibt es eine Möglichkeit, diese Art von großem Problem auf der Grundlage der oben gezeigten Formulierung zu lösen.
2. Ich bin mit McCormick-Hüllkurven und Big-M-Relaxationen vertraut, aber da die Entscheidungsvariablen nicht binär sind, kann ich diese Techniken hier irgendwie anwenden, ich meine Constraint-Relaxationen?
3. Gibt es einen mächtigen Löser, den ich außer Gurobi ausprobieren kann?

Dankeschön.

Answer 1

TL; DR: Einige Optimierungsprobleme sind schwierig und erfordern viel Arbeit, um sie zu lösen.

Lassen Sie mich zunächst Ihre Fragen beantworten:

1. Ja, das ist NP-schwer, aber das sagt nichts darüber aus, ob es leicht zu lösen ist oder nicht. Die meisten MIPs sind NP-hart, werden jedoch extrem häufig gelöst. Meine Lieblingsbehandlung kommt mit freundlicher Genehmigung von Paul Rubin (siehe hier ).

2. Sie können Ihre Ganzzahlen jederzeit in Binärdateien konvertieren. Also wenn du hast$u \in \{0,1,2,3\}$können Sie dies in konvertieren $y_k\in \{0,1\}$, wo $u = \sum \limits_k ky_k$, $\sum \limits_k y_k = 1$ und $k\in\{0,1,2,3\}$. Dann können Sie die traditionellen McCormick-Relaxationen und Big-M-Formulierungen aus den Lehrbüchern anwenden. Beachten Sie, dass Sie McCormick-Relaxationen auch für eine gebundene Ganzzahlvariable durchführen können.

3. Ich arbeite für Gurobi, daher lautet meine offensichtliche Antwort "Nein" :) Da es sich jedoch um ein MPC-Problem handelt, erhalten Sie tatsächlich einiges an Struktur. Zunächst würde ich versuchen, mit kürzeren Horizontlängen zu arbeiten und zu sehen, wie sich die Leistung dadurch verschlechtert. Als nächstes würde ich mich entspannen$u_k$und zu sehen, welche Art von Ergebnissen Sie erhalten. Dies wird die LP-Lockerung des Problems sein, und aus der Protokolldatei, die Sie im Community-Forum von Gurobi gepostet haben, geht hervor, dass sich die Untergrenze nicht viel bewegt. Dies kann also ein guter Anfang sein.

Im Allgemeinen müssen Sie möglicherweise einige spezielle Ansätze erstellen. Beachten Sie jedoch, dass Sie hier wirklich die Leistungsoptimierung durchführen. Nach den Kommentaren von Yair Altman sollten Sie bei der Leistungsoptimierung immer ein quantitatives Ziel haben. So bietet Ihnen Gurobi beispielsweise extrem schnell eine heuristische Lösung, jedoch ist die MIP-Lücke ziemlich groß. Sie müssen also herausfinden, welche MIP-Lücke für Sie akzeptabel ist, und dann Schichten von Algorithmen hinzufügen, um diese Leistung zu erzielen.

EDIT: Danke an Paul Rubin und Rob Pratt für das Erkennen von Fehlern in meinen Gleichungen.