Recovering Dantzig-Wolfe Bounds by Cutting Planes

Dantzig-Wolfe (DW) decomposition is a well-known technique in mixed-integer programming for decomposing and convexifying constraints to obtain potentially strong dual bounds. We investigate Fenchel cuts that can be derived using the DW decomposition algorithm and show that these cuts can provide the same dual bounds as DW decomposition. We show that these cuts, in essence, … Read more

Handling Sub-symmetry in Integer Programming using Activation Handlers

Symmetry in integer programs (IPs) can be exploited in order to reduce solving times. Usually only symmetries of the original IP are handled, but new symmetries may arise at some nodes of the branch-and-bound tree. While symmetry-handling inequalities (SHIs) can easily be used to handle original symmetries, handling sub-symmetries arising later on is more intricate. … Read more

A Unified Framework for Symmetry Handling

Handling symmetries in optimization problems is essential for devising efficient solution methods. In this article, we present a general framework that captures many of the already existing symmetry handling methods (SHMs). While these SHMs are mostly discussed independently from each other, our framework allows to apply different SHMs simultaneously and thus outperforming their individual effect. … Read more

Comparing league formats from a business oriented view: the case of Argentina’s National Basketball League

During the last decades, the use of advanced optimization algorithms to generate sports timetables has caught the attention of both academics and practitioners. From a managerial standpoint, the competition’s structure and the design of the league’s schedule represent key strategic decisions with a direct impact in terms of revenue and other important indicators. Argentina’s National … Read more

Integer Programming Models for Round Robin Tournaments

Round robin tournaments are omnipresent in sport competitions and beyond. We propose two new integer programming formulations for scheduling a round robin tournament, one of which we call the matching formulation. We analytically compare their linear relaxations with the linear relaxation of a well-known traditional formulation. We find that the matching formulation is stronger than … Read more

Relaxations and Duality for Multiobjective Integer Programming

Multiobjective integer programs (MOIPs) simultaneously optimize multiple objective functions over a set of linear constraints and integer variables. In this paper, we present continuous, convex hull and Lagrangian relaxations for MOIPs and examine the relationship among them. The convex hull relaxation is tight at supported solutions, i.e., those that can be derived via a weighted-sum … Read more

Temporal Bin Packing with Half-Capacity Jobs

Motivated by applications in cloud computing, we study a temporal bin packing problem with jobs that occupy half of a bin’s capacity. An instance is given by a set of jobs, each with a start and end time during which it must be processed, i.e., assigned to a bin. A bin can accommodate two jobs … Read more

Maximizing resilience in large-scale social networks

Motivated by the importance of social resilience as a crucial element in cascading leaving of users from a social network, we study identifying a largest relaxed variant of a degree-based cohesive subgraph: the maximum anchored k-core problem. Given graph G=(V,E) and integers k and b, the maximum anchored k-core problem seeks to find a largest … Read more

A Stochastic Optimization Approach to Energy-Efficient Underground Timetabling under Uncertain Dwell and Running Times

We consider a problem from the context of energy-efficient underground railway timetabling, in which an existing timetable draft is improved by slightly changing departure and running times. In practice, synchronization between accelerating and braking trains to utilize regenerative braking plays a major role for the energy-efficiency of a timetable. Since deviations from a planned timetable … Read more

Mathematical models and decomposition methods for the two-bar charts packing problem

We consider the two-bar charts packing (2-BCPP), a recent combinatorial optimization problem whose aim is to pack a set of one-dimensional items into the minimum number of bins. As opposed to the well-known bin packing problem, pairs of items are grouped to form bar charts, and a solution is only feasible if the first and … Read more