Refine
Language
- English (4)
Keywords
- Aggregation (1)
- Branch-and-cut (1)
- Clique Problem (1)
- Combinatorial optimization (1)
- Mixed-integer programming (1)
- Multiple-Choice Constraints (1)
- Network design (1)
- Piecewise Linearization (1)
- Scheduling (1)
- Total Unimodularity (1)
In this work, we present an exact approach for solving network design problems that is based on an iterative graph aggregation procedure. The scheme allows existing preinstalled capacities. Starting with an initial aggregation, we solve a sequence of network design master problems over increasingly fine-grained representations of the original network. In each step, a subproblem is solved that either proves optimality of the solution or gives a directive where to refine the representation of the network in the subsequent iteration. The algorithm terminates with a globally optimal solution to the original problem. Our implementation uses a standard integer programming solver for solving the master problems as well as the subproblems. The computational results on random and realistic instances confirm the profitable use of the iterative aggregation technique. The computing time often reduces drastically when our method is compared to solving the original problem from scratch.
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.
In many real-world mixed-integer optimisation problems from engineering, the side
constraints can be subdivided into two categories: constraints which describe a certain logic to model a feasible allocation of resources (such as a maximal number of available assets, working time requirements, maintenance requirements, contractual obligations, etc.),
and constraints which model physical processes and the related quantities (such as current,
pressure, temperature, etc.). While the first type of constraints can often easily be stated in
terms of a mixed-integer program (MIP), the second part may involve the incorporation of
complex non-linearities, partial differential equations or even a black-box simulation of the
involved physical process. In this work, we propose the integration of a trained tree-based
classifier – a decision-tree or a random forest, into a mixed-integer optimization model as a
possible remedy. We assume that the classifier has been trained on data points produced
by a detailed simulation of a given complex process to represent the functional relationship
between the involved physical quantities. We then derive MIP-representable reformulations
of the trained classifier such that the resulting model can be solved using state-of-the-art
solvers. At the hand of several use cases in terms of possible optimisation goals, we show
the broad applicability of our framework that is easily extendable to other tasks beyond
engineering. In a detailed real-world computational study for the design of stable direct-
current power networks, we demonstrate that our approach yields high-quality solutions
in reasonable computation times.
Stochastic Optimization (SO) is a classical approach for optimization under uncertainty that typically requires knowledge about the probability distribution of uncertain parameters. As the latter is often unknown, Distributionally Robust Optimization (DRO) provides a strong alternative that determines the best guaranteed solution over a set of distributions (ambiguity set). In this work, we present an approach for DRO over time that uses online learning and scenario observations arriving as a data stream to learn more about the uncertainty. Our robust solutions adapt over time and reduce the cost of protection with shrinking ambiguity. For various kinds of ambiguity sets, the robust solutions converge to the SO solution. Our algorithm achieves the optimization and learning goals without solving the DRO problem exactly at any step. We also provide a regret bound for the quality of the online strategy which converges at a rate of $ O(\log T / \sqrt{T})$, where $T$ is the number of iterations. Furthermore, we illustrate the effectiveness of our procedure by numerical experiments on mixed-integer optimization instances from popular benchmark libraries and give practical examples stemming from telecommunications and routing. Our algorithm is able to solve the DRO over time problem significantly faster than standard reformulations.