Dantzig-Wolfe reformulation of a mixed integer program partially convexifies a subset of the constraints, i.e., it implicitly adds all valid inequalities for the associated integer hull. Projecting an optimal basic solution of the reformulation’s LP relaxation to the original space does is in general not yield a basic solution of the original LP relaxation. Cutting … Read more
This is a partial account of the fascinating history of Distance Geometry. We make no claim to completeness, but we do promise a dazzling display of beautiful, elementary mathematics. We prove Heron’s formula, Cauchy’s theorem on the rigidity of polyhedra, Cayley’s generalization of Heron’s formula to higher dimensions, Menger’s characterization of abstract semi-metric spaces, a … Read more
Finding the shortest path in a directed graph is one of the most important combinatorial optimization problems, having applications in a wide range of fields. In its basic version, however, the problem fails to represent situations in which the value of the objective function is determined not only by the choice of each single arc, … Read more
In this paper we consider the Asymmetric Quadratic Traveling Salesman Problem. Given a directed graph and a function that maps every pair of consecutive arcs to a cost, the problem consists in finding a cycle that visits every vertex exactly once and such that the sum of the costs is minimum. We propose an extended … Read more
In this paper, we investigate the two-period subproblems proposed by Akartunal{\i} et al. (2014) for big-bucket lot-sizing problems, which have shown a great potential for obtaining strong bounds for these problems. In particular, we study the polyhedral structure of the mixed integer sets related to two relaxations of these subproblems for the special case of … Read more
In many network applications, one searches for a connected subset of vertices that exhibits other desirable properties. To this end, this paper studies the connected subgraph polytope of a graph, which is the convex hull of subsets of vertices that induce a connected subgraph. Much of our work is devoted to the study of two … Read more
We consider the application of mixed-integer linear programming (MILP) solvers to the minimization of submodular functions. We evaluate common large-scale linear-programming (LP) techniques (e.g., column generation, row generation, dual stabilization) for solving a LP reformulation of the submodular minimization (SM) problem. We present heuristics based on the LP framework and a MILP solver. We evaluated … Read more
We study a single-commodity Robust Network Design problem (sRND) defined on an undirected graph. Our goal is to determine minimum cost capacities such that any traffic demand from a given uncertainty set can be satisfied by a feasible single-commodity flow. We consider two ways of representing the uncertainty set, either as a finite list of … Read more
In 2004 Newman suggested a semidefinite programming relaxation for the Linear Ordering Problem (LOP) that is related to the semidefinite program used in the Goemans-Williamson algorithm to approximate the Max Cut problem. Her model is based on the observation that linear orderings can be fully described by a series of cuts. Newman shows that her … Read more
Given a weighted undirected graph~$G$ and a nonnegative integer~$k$, the maximum~$k$-star colorable subgraph problem consists of finding an induced subgraph of~$G$ which has maximum weight and can be star colored with at most~$k$ colors; a star coloring does not color adjacent nodes with the same color and avoids coloring any 4-path with exactly two colors. … Read more