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
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 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
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
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
The traveling salesman problem (TSP) asks for a shortest tour through all vertices of a graph with respect to the weights of the edges. The symmetric quadratic traveling salesman problem (SQTSP) associates a weight with every three vertices traversed in succession. If these weights correspond to the turning angles of the tour, we speak of … Read more
In Vertex Coloring Problems, one is required to assign a color to each vertex of an undirected graph in such a way that adjacent vertices receive different colors, and the objective is to minimize the cost of the used colors. In this work we solve four different coloring problems formulated as Maximum Weight Stable Set … Read more
We study the Knapsack Problem with Conflict Graph (KPCG), an extension of the 0-1 Knapsack Problem, in which a conflict graph describing incompatibilities between items is given. The goal of the KPCG is to select the maximum profit set of compatible items while satisfying the knapsack capacity constraint. We present a new Branch-and-Bound approach to … Read more
Stochastic Programming (SP) has long been considered as a well-justified yet computationally challenging paradigm for practical applications. Computational studies in the literature often involve approximating a large number of scenarios by using a small number of scenarios to be processed via deterministic solvers, or running Sample Average Approximation on some genre of high performance machines … Read more
Two dimensional cutting problems are about obtaining a set of rectangular items from a set of rectangular stock pieces and are of great relevance in industry, whenever a sheet of wood, metal or other material has to be cut. In this paper, we consider the 2-stage two-dimensional knapsack (2TDK) problem which requires finding the maximum … Read more