B07
Refine
Year of publication
- 2016 (4) (remove)
Language
- English (4)
Has Fulltext
- yes (4) (remove)
Keywords
- Clique Problem (1)
- Complementarity Constraints (1)
- Euler and St. Venant equations (1)
- MINLP (1)
- MPEC (1)
- Mixed-Integer Nonlinear Optimization (1)
- Multiple-Choice Constraints (1)
- Networks (1)
- Piecewise Linearization (1)
- Primal Heuristic (1)
Nonconvex mixed-binary nonlinear optimization problems frequently appear in practice and are typically extremely hard to solve. In this paper we discuss a class of primal heuristics that are based on a reformulation of the problem as a mathematical program with equilibrium constraints. We then use different regularization schemes for this class of problems and use an iterative solution procedure for solving series of regularized problems. In the case of success, these procedures result in a feasible solution of the original mixed-binary nonlinear problem. Since we rely on local nonlinear programming solvers the resulting method is fast and we further improve its reliability by additional algorithmic techniques. We show the strength of our method by an extensive computational study on 662 MINLPLib2 instances, where our methods are able to produce feasible solutions for 60% of all instances in at most 10s.
We consider optimal control problems for the flow of gas or fresh water in pipe networks as well as drainage or sewer systems in open canals. The equations of motion are taken to be represented by the nonlinear isothermal Euler gas equations, the water hammer equations, or the St.~Venant equations for flow. We formulate model hierarchies and derive an abstract model for such network flow problems including pipes, junctions, and controllable elements such as valves, weirs, pumps, as well as compressors. We use the abstract model to give an overview of the known results and challenges concerning equilibria, well-posedness, controllability, and optimal control. A major challenge concerning the optimization is to deal with switching on-off states that are inherent to controllable devices in such applications combined with
continuous simulation and optimization of the gas flow. We formulate the corresponding mixed-integer nonlinear optimal control problems and outline a decomposition approach as a solution technique.
Detailed modeling of gas transport problems leads to nonlinear
and nonconvex mixed-integer optimization or feasibility models
(MINLPs) because both the incorporation of discrete controls of the
network as well as accurate physical and technical modeling is
required in order to achieve practical solutions. Hence, ignoring
certain parts of the physics model is not valid for practice. In the
present contribution we extend an approach based on linear relaxations
of the underlying nonlinearities by tailored model reformulation
techniques yielding block-separable MINLPs. This combination of
techniques allows us to apply a penalty alternating direction method
and thus to solve highly detailed MINLPs for large-scale real-world
instances. The practical strength of the proposed method is
demonstrated by a computational study in which we apply the method to
instances from steady-state gas transport
including both pooling effects with respect to the mixing of gases of
different composition and a highly detailed compressor station model.
We consider the clique problem with multiple-choice constraints (CPMC) and characterize a case where it is possible to give an efficient description of the convex hull of its feasible solutions. This case, which we call staircase compatibility, generalizes common properties in applications and allows for a linear description of the integer feasible solutions to (CPMC) with a totally unimodular constraint matrix
of polynomial size. We derive two such totally unimodular reformulations for the problem: one that is obtained by a strengthening of the compatibility constraints
and one that is based on a representation as a dual network flow problem. Furthermore, we show a natural way to derive integral solutions from fractional solutions to the problem by determining integral extreme points generating this fractional
solution. We also evaluate our reformulations from a computational point of view by applying them to two different real-world applications. The first one is
a problem in railway timetabling where we try to adapt a given timetable slightly such that energy costs from operating the trains are reduced. The second one is the piecewise linearization of non-linear flow problems on a gas network. In both cases, we are able to reduce the solution times significantly by passing to the theoretically stronger formulations of the problem.