Balancedness in the Weighted Rectangles Partitioning Problem

A rectangle is subdivided into pixels which are either active or inactive. The weighted rectangles partitioning problem (WRP) is finding a partition of the active pixels into weighted, smaller rectangles and maximizing the total weight. Using an IP formulation, instances with an integral relaxation polyhedron are characterized by the balancedness of the problem matrix. Is … Read more

An Overview of Nested Decomposition for Multi-Level Optimization Problems

Nested multi-level structures are frequently encountered in many real-world optimization problems. Decomposition techniques are a commonly applied approach used to handle nested multi-level structures; however, the typical problem-specific focus of such techniques has led to numerous specialized formulations and solution methods. This lack of generalized results for nested multi-level optimization problems is addressed in this … Read more

An Integrated Rolling Horizon and Adaptive-Refinement Approach for Disjoint Trajectories Optimization

Planning of trajectories, i.e. paths over time, is a challenging task. Thereby, the trajectories for involved commodities often have to be considered jointly as separation constraints have to be respected. This is for example the case in robot motion or air traffic management. Involving these discrete separation constraints in the planning of best possible continuous … Read more

A Theoretical and Computational Analysis of Full Strong-Branching

Full strong-branching (henceforth referred to as strong-branching) is a well-known variable selection rule that is known experimentally to produce significantly smaller branch-and-bound trees in comparison to all other known variable selection rules. In this paper, we attempt an analysis of the performance of the strong-branching rule both from a theoretical and a computational perspective. On … Read more

On Polytopes with Linear Rank with respect to Generalizations of the Split Closure

In this paper we study the rank of polytopes contained in the 0-1 cube with respect to $t$-branch split cuts and $t$-dimensional lattice cuts for a fixed positive integer $t$. These inequalities are the same as split cuts when $t=1$ and generalize split cuts when $t > 1$. For polytopes contained in the $n$-dimensional 0-1 … Read more

Incorporating Holding Costs in Continuous-TimeService Network Design: New Model, Relaxation, and Exact Algorithm

The continuous-time service network design problem (CTSNDP) occurs widely in practice. It aims to minimize the total operational cost by optimizing the schedules of transportation services and the routes of shipments for dispatching, which can occur at any time point along a continuous planning horizon. In order to be cost effective, shipments often wait to … Read more

On the generation of Metric TSP instances with a large integrality gap by branch-and-cut.

This paper introduces a computational method for generating metric Travelling Salesperson Problem (TSP) instances having a large integrality gap. The method is based on the solution of an NP-hard problem, called IH-OPT, that takes in input a fractional solution of the Subtour Elimination Problem (SEP) on a TSP instance and compute a TSP instance having … Read more

Integer Optimization Model and Algorithm for the Stem Cell Culturing Problem

In this paper, we present a novel scheduling problem, the stem cell culturing problem (SCP), which is identified in an attempt to improve the productivity of a manufacturing system producing a commercialized autologous stem cell therapeutic product for treating an incurable disease. For a given therapeutic product along with the corresponding manufacturing process, which is … Read more

A decomposition approach for integrated locomotive scheduling and driver rostering in rail freight transport

In this work, we consider the integrated problem of locomotive scheduling and driver rostering in rail freight companies. Our aim is to compute an optimal simultaneous assignment of locomotives and drivers to the trains listed in a given order book. Mathematically, this leads to the combination of a set-packing problem with compatibility constraints and a … Read more

On fault-tolerant low-diameter clusters in graphs

Cliques and their generalizations are frequently used to model “tightly knit” clusters in graphs and identifying such clusters is a popular technique used in graph-based data mining. One such model is the $s$-club, which is a vertex subset that induces a subgraph of diameter at most $s$. This model has found use in a variety … Read more