Comparison of IP and CNF Models for Control of Automated Valet Parking Systems

In automated valet parking system, a central computer controls a number of robots which have the capability to move in two directions, under cars, lift a car up, carry it to another parking slot, and drop it. We study the theoretical throughput limitations of these systems: Given a car park layout, an initial configuration of … Read more

Fooling Sets and the Spanning Tree Polytope

In the study of extensions of polytopes of combinatorial optimization problems, a notorious open question is that for the size of the smallest extended formulation of the Minimum Spanning Tree problem on a complete graph with n nodes. The best known lower bound is \Omega(n^2), the best known upper bound is O(n^3). In this note … Read more

Compact formulations of the Steiner traveling salesman problem and related problems

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