Algorithms for Bilevel and Semi-Infinite and Generalized Semi-Infinite Programs

 

Hierarchical Optimization

Hierarchical optimization problems are problems where an upper-level problem is constrained by the solution of an embedded lower-level problem. This problem family encompasses (generalized) semi-infinite programs and bilevel programs. Algorithms have been developed for the solution of various types of hierarchical problems.

 

(Generalized) Semi-Infinite Programs ((G)SIPs)

These are optimization problems with a finite number of variables and an infinite number of constraints. Based on the discretization of the constraint-space, algorithms have been developed that guarantee the global solution of both SIPs and GSIPs in finite time under mild assumptions (Mitsos 2015, Mitsos 2011). Besides providing strong convergence guarantees and competitive solution times, these algorithms are comparatively easy to implement. Paradigmatic GAMS implementations of the SIP algorithm and the GSIP algorithm are available for download. Further improvements on the algorithms are currently in development and will also be published open-source.

Another solution approach to SIPs is relaxation-based bounding (Mitsos 2008). Implementations of the developed algorithms are available for cooperative projects.

 

Bilevel Programs

In bilevel programs, the lower-level program is given by an explicit minimization/maximization instruction. Members of this problem family are much harder to solve than SIPs in the general case. However, a strategy similar to the discretization approach for SIPs can be used. Algorithms have been developed based on discretization and bounding of the lower-level objective to solve bilevel programs globally (Mitsos 2008, Mitsos 2010). These are applicable to both the NLP and MINLP case of bilevel programs. The corresponding implementations are available for cooperative projects.

If you are interested in using this software please feel free to contact us.