Mixed-Integer Reformulations of Resource-Constrained Two-Stage Assignment Problems

The running time for solving a mixed-integer linear optimization problem (MIP) strongly depends on the number of its integral variables. Bader et al. [Math. Progr. 169 (2018) 565–584] equivalently reformulate an integer program into an MIP that contains a reduced number of integrality constraints, when compared to the original model. Generalizing the concept of totally … Read more

Efficient Formulations and Decomposition Approaches for Power Peak Reduction in Railway Traffic via Timetabling

Over the last few years, optimization models for the energy-efficient operation of railway traffic have received more and more attention, particularly in connection with timetable design. In this work, we study the effect of load management via timetabling. The idea is to consider trains as time-flexible consumers in the railway power supply network and to … Read more

Subdeterminants and Concave Integer Quadratic Programming

We consider the NP-hard problem of minimizing a separable concave quadratic function over the integral points in a polyhedron, and we denote by D the largest absolute value of the subdeterminants of the constraint matrix. In this paper we give an algorithm that finds an epsilon-approximate solution for this problem by solving a number of … Read more

Staircase Compatibility and its Applications in Scheduling and Piecewise Linearization

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 new special case, which we call staircase compatibility, generalizes common properties in several applications and allows for a linear description of the integer feasible … Read more

Totally Unimodular Congestion Games

We investigate a new class of congestion games, called Totally Unimodular Congestion Games, in which the strategies of each player are expressed as binary vectors lying in a polyhedron defined using a totally unimodular constraint matrix and an integer right-hand side. We study both the symmetric and the asymmetric variants of the game. In the … Read more

A primal-simplex based Tardos’ algorithm

In the mid-eighties Tardos proposed a strongly polynomial algorithm for solving linear programming problems for which the size of the coefficient matrix is polynomially bounded by the dimension. Combining Orlin’s primal-based modification and Mizuno’s use of the simplex method, we introduce a modification of Tardos’ algorithm considering only the primal problem and using simplex method … Read more

Efficient Heuristic Algorithms for Maximum Utility Product Pricing Problems

We propose improvements to some of the best heuristic algorithms for optimal product pricing problem originally designed by Dobson and Kalish in the late 1980’s and in the early 1990’s. Our improvements are based on a detailed study of a fundamental decoupling structure of the underlying mixed integer programming (MIP) problem and on incorporating more … Read more