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].
