Enhancements of Discretization Approaches for Non-Convex Mixed-Integer Quadratically Constraint Quadratic Programming

We study mixed-integer programming (MIP) relaxation techniques for the solution of non-convex mixed-integer quadratically constrained quadratic programs (MIQCQPs). We present two MIP relaxation methods for non-convex continuous variable products that enhance existing approaches. One is based on a separable reformulation, while the other extends the well-known MIP relaxation normalized multiparametric disaggregation technique (NMDT). In addition, … Read more

A $\sqrt{5}/2$-approximation algorithm for optimal piecewise linear approximations of bounded variable products

We investigate the optimal piecewise linear approximation of the bivariate product $ xy $ over rectangular domains. More precisely, our aim is to minimize the number of simplices in the triangulation underlying the approximation, while respecting a prescribed approximation error. First, we show how to construct optimal triangulations consisting of up to five simplices. Using … Read more

EETTlib – Energy-Efficient Train Timetabling Library

We introduce EETTlib, an instance library for the Energy-Efficient Train Timetabling problem. The task in this problem is to adjust a given timetable draft such that several key indicators relating to the energy consumption of the resulting railway traffic are minimized. These include peak power consumption, total energy consumption, loss in recuperation energy, fluctuation in … Read more

On Piecewise Linear Approximations of Bilinear Terms: Structural Comparison of Univariate and Bivariate Mixed-Integer Programming Formulations

Bilinear terms naturally appear in many optimization problems. Their inherent nonconvexity typically makes them challenging to solve. One approach to tackle this difficulty is to use bivariate piecewise linear approximations for each variable product, which can be represented via mixed-integer linear programming (MIP) formulations. Alternatively, one can reformulate the variable products as a sum of … Read more