Robust optimization is an important technique to immunize optimization problems against data uncertainty. In the case of a linear program and an ellipsoidal uncertainty set, the robust counterpart turns into a second-order cone program. In this work, we investigate the efficiency of linearizing the second-order cone constraints of the latter. This is done using the … Read more
This paper presents various worst-case results on the positive semidefinite (psd) rank of a nonnegative matrix, primarily in the context of polytopes. We prove that the psd rank of a generic n-dimensional polytope with v vertices is at least (nv)^(1/4) improving on previous lower bounds. For polygons with v vertices, we show that psd rank … Read more
In this paper we characterize the slack matrices of cones and polytopes among all nonnegative matrices. This leads to an algorithm for deciding whether a given matrix is a slack matrix. The underlying decision problem is equivalent to the polyhedral verifi cation problem whose complexity is unknown. Citation April 2013 Article Download View Which Nonnegative Matrices … Read more
This paper deals with the Traveling Salesman Problem (TSP) with Draft Limits (TSPDL), which is a variant of the well-known TSP in the context of maritime transportation. In this recently proposed problem, draft limits are imposed due to restrictions on the port infrastructures. Exact algorithms based on three mathematical formulations are proposed and their performance … Read more
The positive semidefinite (psd) rank of a polytope is the smallest $k$ for which the cone of $k \times k$ real symmetric psd matrices admits an affine slice that projects onto the polytope. In this paper we show that the psd rank of a polytope is at least the dimension of the polytope plus one, … Read more
The Steiner Traveling Salesman Problem (STSP) is a variant of the Traveling Salesman Problem (TSP) that is particularly suitable when dealing with sparse networks, such as road networks. The standard integer programming formulation of the STSP has an exponential number of constraints, just like the standard formulation of the TSP. On the other hand, there … Read more
Large-sized extended formulations have the potential for providing high-quality bounds on some combinatorial optimization problems where the natural formulations perform poorly. This chapter discusses the use of some families of cuts that have been recently applied on extended formulations that are obtained by the discretization of the continuous variables occurring in the natural formulation of … Read more
Working in an extended variable space allows one to develop tight reformulations for mixed integer programs. However, the size of the extended formulation grows rapidly too large for a direct treatment by a MIP-solver. Then, one can use projection tools and derive valid inequalities for the original formulation, or consider an approximate extended formulation (f.i., … Read more
In this paper, we study deterministic dynamic lot-sizing problems with service level constraints on the total number of periods in which backorders can occur over the finite planning horizon. We give a natural mixed integer programming formulation for the single item problem (LS-SL-I) and study the structure of its solution. We show that an optimal … Read more
The mixing set with a knapsack constraint arises in deterministic equivalent of probabilistic programming problems with finite discrete distributions. We first consider the case that the probabilistic program has equal probabilities for each scenario. We study the resulting mixing set with a cardinality constraint and propose facet-defining inequalities that subsume known explicit inequalities for this … Read more