An Exact Approach for Convex Adjustable Robust Optimization

Adjustable Robust Optimization (ARO) is a paradigm for facing uncertainty in a decision problem, in case some recourse actions are allowed after the actual value of all input parameters is revealed. While several approaches have been introduced for the linear case, little is known regarding exact methods for the convex case. In this work, we … Read more

Models and Algorithms for the Weighted Safe Set Problem

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

Adaptive robust optimization with discrete uncertainty

In this paper, we study adaptive robust optimization problems with discrete uncertainty. We first show that an adaptive robust counterpart of the multiple knapsack problem includes $\Sigma_2^P$-hard problems. Then, we theoretically prove the validity of a non-trivial reformulation of this class of problems which can be solved by an enumerative algorithm akin to a Branch-and-Benders-cut … Read more

Adaptive robust optimization with objective uncertainty

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 solution algorithm for chance-constrained problems with integer second-stage recourse decisions

We study a class of chance-constrained two-stage stochastic optimization problems where the second-stage recourse decisions belong to mixed-integer convex sets. Due to the nonconvexity of the second-stage feasible sets, standard decomposition approaches cannot be applied. We develop a provably convergent branch-and-cut scheme that iteratively generates valid inequalities for the convex hull of the second-stage feasible … Read more

K-Adaptability in stochastic optimization

We consider stochastic problems in which both the objective function and the feasible set are affected by uncertainty. We address these problems using a K-adaptability approach, in which K solutions for the underlying problem are computed before the uncertainty dissolves and afterwards the best of them can be chosen for the realised scenario. This paradigm … Read more

A Branch-and-Price Algorithm for the Minimum Sum Coloring Problem

A proper coloring of a given graph is an assignment of colors (integer numbers) to its vertices such that two adjacent vertices receives di different colors. This paper studies the Minimum Sum Coloring Problem (MSCP), which asks for fi nding a proper coloring while minimizing the sum of the colors assigned to the vertices. This paper presents … Read more

Casting light on the hidden bilevel combinatorial structure of the k-Vertex Separator problem

Given an undirected graph, we study the capacitated vertex separator problem which asks to find a subset of vertices of minimum cardinality, the removal of which induces a graph having a bounded number of pairwise disconnected shores (subsets of vertices) of limited cardinality. The problem is of great importance in the analysis and protection of … Read more

On Integer and Bilevel Formulations for the k-Vertex Cut Problem

The family of Critical Node Detection Problems asks for finding a subset of vertices, deletion of which minimizes or maximizes a predefined connectivity measure on the remaining network. We study a problem of this family called the k-vertex cut problem. The problems asks for determining the minimum weight subset of nodes whose removal disconnects a … Read more

The Vertex k-cut Problem

Given an undirected graph G = (V, E), a vertex k-cut of G is a vertex subset of V the removing of which disconnects the graph in at least k connected components. Given a graph G and an integer k greater than or equal to two, the vertex k-cut problem consists in finding a vertex … Read more