MATHEON-B19: MINLP
Nicht konvexe gemischt-ganzzahlige nicht linear Programmierung
Beschreibung
The goal of this project is to bring together the expertise of SCIP and LaGO for the development of a general purpose LP based branch-and-cut solver for nonconvex MINLPs. Thus, we plan to develop and implement cut generation techniques (e.g., linearizations of convexifications) to cut off infeasible points from an LP relaxation, heuristics (e.g., local search in a nonlinear program (NLP)) to find feasible solution candidates, branching- and node selection rules, and domain propagation methods.
In the beginning, we will approach the solution of the broad class of mixed-integer all-quadratic problems (MIQQP), i.e., MINLPs where f(x) and g(x) are quadratic functions. Such constraints appear, for instance, whenever different materials are mixed in technical or chemical processes. Further on, methods for the treatment of other common nonlinear functions and their composition should be developed. An important aspect which had a remarkable impact on MILP solvers but has not found much attention in existing MINLP codes so far is preprocessing. This includes reformulations and model reductions that can be deduced from the problem formulation and that are favorable for the applied algorithm. Therefore, also an adequate in-memory representation of the MINLP demands for special attention. To allow an easy applicability of the developed techniques, interfaces to the modeling systems ZIMPL [Koc04] and GAMS and the instance language OSiL will be developed.
In the following, the developed software will be extended step by step to handle more general nonconvex MINLPs.
Applications of the developed software are, among others, in fare planning, mine production planing, and the optimization of the design and operation of complex energy conversion systems [AOVNT07, JTV07, JTV09]. Further, the optimization of MINLPs under uncertainties constitutes a challenging application for the developed software. While the deterministic equivalents of stochastic MINLPs are large-scale, their structure offers an interesting starting point for decomposition algorithms [GKNRW02].
Ansprechpartner
Mitarbeiter
- Martin Grötschel
- Werner Römisch
- Andreas Bley
- Ambros Gleixner
- Thorsten Koch
- Marc Pfetsch
Partner
- ZIB Project NLIP: Application of the developed software for the solution of open-pit mine production scheduling problems.
- ZIB Project VPP: Application of the developed software for the solution of vehicle positioning problems.
- TU Darmstadt, Research Group Optimization: Development of an NLP infrastructure in SCIP and interface to the NLP solver DONLP.
- TU Braunschweig, Institute for Mathematical Optimization: Development of SCIP to support implementation of MINLP plugins.
- GAMS Development: Development of a GAMS interface to an extended SCIP version.
Finanzierung
- DFG Research Center Matheon: Mathematics for Key Technologies.
Dauer
10/2008 - 04/2009