computational experiments

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

Effective Solution Algorithms for Bulk-Robust Optimization Problems

Categories 0-1 Programming, Network Optimization, Robust Optimization Tags , , , ,

Bulk-robust optimization is a recent paradigm for addressing problems in which the structure of a system is affected by uncertainty. It considers the case in which a finite and discrete set of possible failure scenarios is known in advance, and the decision maker aims to activate a subset of available resources of minimum cost so … 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

Models and Algorithms for the Weighted Safe Set Problem

Categories Branch and Cut Algorithms, Graphs and Matroids Tags , , ,

Given a connected graph G = (V, E), a Safe Set S is a subset of the vertex set V such that the cardinality of each connected component in the subgraph induced by V \ S does not exceed the cardinality of any neighbor connected component in the subgraph induced by S. When the vertices … Read more

Adjustable robust optimization with objective uncertainty

Categories Applications - OR and Management Sciences, Convex Optimization, Robust Optimization Tags , , , , ,

In this work, we study optimization problems where some cost parameters are not known at decision time and the decision flow is modeled as a two-stage process within a robust optimization setting. We address general problems in which all constraints (including those linking the first and the second stages) are defined by convex functions and … Read more

A new branch-and-filter exact algorithm for binary constraint satisfaction problems

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

A binary constraint satisfaction problem (BCSP) consist in determining an assignment of values to variables which is compatible with a set of constraints. The problem is called binary because the constraints involve only pairs of variables. The BCSP is a cornerstone problem in Constraint Programming (CP), appearing in a very wide range of real-world applications. … Read more

Integer Optimization with Penalized Fractional Values: The Knapsack Case

Categories 0-1 Programming, Combinatorial Optimization Tags , , ,

We consider integer optimization problems where variables can potentially take fractional values, but this occurrence is penalized in the objective function. This general situation has relevant examples in scheduling (preemption), routing (split delivery), cutting and telecommunications, just to mention a few. However, the general case in which variables integrality can be relaxed at cost of … Read more

Exact Approaches for the Knapsack Problem with Setups

Categories 0-1 Programming, Integer Programming Tags , , , ,

We consider a generalization of the knapsack problem in which items are partitioned into classes, each characterized by a fixed cost and capacity. We study three alternative Integer Linear Programming formulations. For each formulation, we design an efficient algorithm to compute the linear programming relaxation (one of which is based on Column Generation techniques). We … Read more