integer linear programming

A regular perspective on solving the irregular strip packing problem with the dotted-board model: a mosaic approach and a divide-and-conquer strategy

Categories Combinatorial Optimization, Integer Programming Tags , , , ,

Since its introduction in 2013, the dotted-board model has been widely used by the cutting and packing research community to tackle irregular packing problems. However, despite its popularity, little research has aimed at improving its performance when solved via off-the-shelf integer programming solvers, beyond the known strategy of merging pairwise incompatibility constraints into clique constraints … Read more

The colored knapsack problem: structural properties and exact algorithms

Categories (Mixed) Integer Linear Programming, Combinatorial Optimization, Dynamic Programming Tags , , , ,

We introduce and study a novel generalization of the classical Knapsack Problem (KP), called the Colored Knapsack Problem (CKP). In this problem, the items are partitioned into classes of colors and the packed items need to be ordered such that no consecutive items are of the same color. We establish that the problem is weakly … Read more

Extending the reflect flow formulation to variable-sized one-dimensional cutting and skiving stock problems

Categories Combinatorial Optimization, Integer Programming Tags , , ,

Flow formulations have been widely studied for the one-dimensional cutting stock problem and several of its extensions. Among these, the so-called reflect model has shown the best empirical performance when solved directly with a general-purpose integer linear programming solver due to its reduced number of variables and constraints. However, existing adaptations of reflect for the … Read more

An exact approach for the Train Single-Routing Selection Problem

Categories (Mixed) Integer Linear Programming, Applications - OR and Management Sciences, Transportation Tags , , , ,

Given a set of train routes with route costs and a set of compatible route pairs with pairing costs, the Train Single-Routing Selection Problem (TSRSP) seeks to assign one route to each train, minimizing the total cost while ensuring pairwise compatibility among the selected routes. This problem is of significant practical relevance in rail traffic … Read more

An efficient solution methodology for the airport slot allocation problem with preprocessing and column generation

Categories Airline Optimization, Scheduling, Transportation Tags , , , ,

Airport coordination is a demand control mechanism that maximizes the use of existing infrastructure at congested airports. Aircraft operators submit a list of regular flights that they wish to operate over a five to seven-month period and a designated coordinator is responsible for allocating the available airport slots, which represent the permission to operate a … Read more

Pattern-based ILP models for the one-dimensional cutting stock problem with setup cost

Categories (Mixed) Integer Linear Programming, Production and Logistics Tags , , , ,

The One-Dimensional Cutting Stock Problem with Setup Cost (CSP-S) is a cutting problem that seeks a cutting plan with a minimum number of objects and a minimum number of different patterns. This problem gains relevance in manufacturing settings, where time consuming operations to set up the knives of the cutting machine for the new patterns … Read more

Determining locations and layouts for parcel lockers to support supply chain viability at the last mile

Categories (Mixed) Integer Linear Programming, Facility Planning and Design, Transportation Tags , , , ,

The pandemic caused by the corona virus SARS-CoV-2 raised many new challenges for humanity. For instance, governments imposed regulations such as lockdowns, resulting in supply chain shocks at different tiers. Additionally, delivery services reached their capacity limits because the demand for mail orders soared temporarily during the lockdowns. We argue that one option to support … Read more

Mathematical models for the minimization of open stacks problem

Categories Applications - OR and Management Sciences Tags , , , ,

In this paper, we address the Minimization of Open Stacks Problem (MOSP). This problem often appears during production planning of manufacturing industries, such as in the cutting of objects to comply with space constraints around the cutting machine in the glass, furniture, and metallurgical industries. The MOSP is also pertinent to the field of VLSI … Read more

Energy-efficient Automated Vertical Farms

Categories Combinatorial Optimization, Production and Logistics Tags , , , ,

Autonomous vertical farms (VFs) are becoming increasingly more popular, because they allow to grow food minimising water consumption and the use of pesticides, while greatly increasing the yield per square metre, compared with traditional agriculture. To meet sustainability goals, however, VFs must operate at maximum efficiency; it would be otherwise impossible to compete with the … Read more