{"id":2492,"date":"2024-04-19T19:26:53","date_gmt":"2024-04-19T19:26:53","guid":{"rendered":"https:\/\/elo-x.eu\/?p=2492"},"modified":"2024-05-31T14:19:07","modified_gmt":"2024-05-31T14:19:07","slug":"algorithms-for-solving-hard-optimization-problems","status":"publish","type":"post","link":"https:\/\/elo-x.eu\/?p=2492","title":{"rendered":"Algorithms for solving hard optimization problems"},"content":{"rendered":"\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t\t
\n\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t

Algorithms for solving hard optimization problems<\/h2>\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t
\n\t\t\t\n\t\t\t\t\t\t<\/span>\n\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t\t
\n\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\t

Andrea Ghezzi,\u00a0University of Freiburg
<\/span><\/span><\/p>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t

\n\t\t\t\t\t\t
\n\t\t\t\t\t
\n\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\t

In my research, I focus on optimization methods and algorithms that aim to “solve” problems in different classes. All these problems share one thing, they are terribly hard to solve. On the one hand, we investigate algorithms for computing solutions of mixed-integer nonlinear programs (MINLPs), where the complexity lies in the combination of nonlinear and combinatorial optimization. On the other hand, we regard nonlinear programs (NLPs) that arise from nonlinear model predictive control (NMPC). Here the major hurdle is to solve NLPs online and on resourced-constrained hardware.<\/p>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t

\n\t\t\t\t\t\t
\n\t\t\t\t\t
\n\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t
\n\t\t\t\n\t\t\t\t\t\t<\/span>\n\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t

Solving mixed-integer nonlinear programs<\/h2>\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t\t
\n\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\t

[1] Ghezzi*, Van Roy*, Sager, Diehl, “A sequential Benders-based mixed-integer quadratic programming algorithm” – submitted, 2024<\/em><\/p>\n

[2] Ghezzi, Simpson, B\u00fcrger, Zeile, Sager, Diehl, “A Voronoi-based mixed-Integer Gauss-Newton algorithm for MINLP Arising in optimal control”, ECC 2023 <\/p>\n

* Equal contribution<\/em><\/p>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t

\n\t\t\t\t\t\t
\n\t\t\t\t\t
\n\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\t

\u00a0<\/p>

For continuous decision spaces, nonlinear programs (NLPs) can be efficiently solved via sequential quadratic programming (SQP) and, more generally, sequential convex programming (SCP). These algorithms linearize only the nonlinear equality constraints and keep the outer convex structure of the problem intact. We aim to develop algorithms that extend the SQP\/SCP methodology to mixed-integer nonlinear programs (MINLPs) and leverage the availability of efficient mixed-integer quadratic programming (MIQP) solvers.\u00a0<\/p>

Our latest algorithm, S-B-MIQP, presented in [1], is a heuristic method without any global optimality guarantee, it converges to the exact integer solution when applied to convex MINLP with a linear outer structure. The conducted numerical experiments on existing benchmarks demonstrate that the proposed algorithm is competitive with other open-source solvers for MINLP. Finally, we demonstrate via numerical simulations that the developed algorithm work out-of-the-box for mixed-integer optimal control problems (MIOCPs) transcribed into MINLPs via direct methods. These problems are characterized by numerous nonlinear equality constraints, a major hurdle for generic MINLP solvers.<\/p>

Checkout our open-source MINLP toolbox package:\u00a0<\/b>minlp-toolbox<\/a><\/p>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t

\n\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\t\t\t\t
\n\t\t\t\t\t\t\t\t\t\t\"\"\t\t\t\t\t\t\t\t\t\t\t
Benchmarking S-B-MIQP [1] with other open-source general purpose MINLP solvers on a subset of MINLP instances contained in the MINLPLib.<\/figcaption>\n\t\t\t\t\t\t\t\t\t\t<\/figure>\n\t\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t\t
\n\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t
\n\t\t\t\n\t\t\t\t\t\t<\/span>\n\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t

Imitation learning from nonlinear model predictive control<\/h2>\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t\t
\n\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\t

[3] Ghezzi*, Hoffman*, Frey, Boedecker, Diehl, “Imitation Learning from Nonlinear MPC via the Exact Q-Loss and its Gauss-Newton Approximation”, CDC 2023<\/p>

* Equal contribution<\/em>
<\/p>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t

\n\t\t\t\t\t\t
\n\t\t\t\t\t
\n\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\t

We proposed a novel loss function for imitation learning from NMPC that … <\/p>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t

\n\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\t\t\t\t
\n\t\t\t\t\t\t\t\t\t\t\"\"\t\t\t\t\t\t\t\t\t\t\t
Comparing learned policies against MPC policy on controlling an inverted pendulum on a cart (cartpole). Policies: left plot from top to bottom: Behavioral Cloning, exact Q-loss, approximated Q-loss, MPC. Left plot: policy rollout - applied control actions. Right plot: angular velocity - constraint satisfaction. <\/figcaption>\n\t\t\t\t\t\t\t\t\t\t<\/figure>\n\t\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<\/div>\n\t\t","protected":false},"excerpt":{"rendered":"

Algorithms for solving hard optimization problems Andrea Ghezzi,\u00a0University of Freiburg In my research, I focus on optimization methods and algorithms that aim to “solve” problems in different classes. All these problems share one thing, they are terribly hard to solve. On the one hand, we investigate algorithms for computing solutions of mixed-integer nonlinear programs (MINLPs), … <\/p>\n

Continue reading “Algorithms for solving hard optimization problems”<\/span><\/a><\/p>\n","protected":false},"author":6,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"elementor_header_footer","format":"standard","meta":{"footnotes":""},"categories":[22],"tags":[],"class_list":["post-2492","post","type-post","status-publish","format-standard","hentry","category-projects"],"_links":{"self":[{"href":"https:\/\/elo-x.eu\/index.php?rest_route=\/wp\/v2\/posts\/2492","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/elo-x.eu\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/elo-x.eu\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/elo-x.eu\/index.php?rest_route=\/wp\/v2\/users\/6"}],"replies":[{"embeddable":true,"href":"https:\/\/elo-x.eu\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=2492"}],"version-history":[{"count":43,"href":"https:\/\/elo-x.eu\/index.php?rest_route=\/wp\/v2\/posts\/2492\/revisions"}],"predecessor-version":[{"id":2698,"href":"https:\/\/elo-x.eu\/index.php?rest_route=\/wp\/v2\/posts\/2492\/revisions\/2698"}],"wp:attachment":[{"href":"https:\/\/elo-x.eu\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=2492"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/elo-x.eu\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=2492"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/elo-x.eu\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=2492"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}