Resumen de Enhancing discretized formulations: the knapsack reformulation and the star reformulation

Luís Gouveia, Pedro Moura

• Discretized formulations have proved to be useful for modeling combinatorial optimizations. The main focus of this work is on how to strengthen the linear programming relaxation of a given discretized formulation. More precisely, we will study and strengthen subproblems that arise in these formulations. In one case we will focus on the so-called knapsack reformulation which is based on viewing these models as the intersection of two polyhedra, one of them being a specialized knapsack problem. We will show that strong inequalities used in previous works are a special case of inequalities implied by the knapsack formulation. In the second case we will analyze a star-like subproblem and will provide an extended formulation for this problem as well as a set of inequalities on the original space, implied by the inequalities of the extended formulation. We will use a generalization of the Degree Constrained Spanning Tree problem as a setting for this study. In the present work, besides contextualizing these enhancements in terms of discretized models presented in previous works, we also compare and combine together them, for the first time.