LIMITI DELL'APPROCCIO RISOLUTIVO DI PROGRAMMI LINEARI INTERI MEDIANTE FORMULAZIONI ESTESE

One of the possible ways to approach integer linear problems is to employ extended formulations, a technique which consists of expressing the convex hull of the corresponding feasible regions in a higher-dimensional space through auxiliary variables, in order to reduce the number of constraints (called size). The objective is to ensure that, as the number of variables in the original problem increases, the size grows at most polynomially, allowing the possibility to use an algorithm provided by Linear Programming theory. In this thesis, we analyze the limitations of this approach, which sometimes make it unviable. In particular, we focus on a result illustrated by Yannakakis in 1991, which establishes a lower bound on the size of an extended formulation, linked to the concept of non-negative rank of the slack matrix of the polytope that describes the problem. We also consider an argument presented by Rothvoß in 2011, which proves that there exist integer linear problems that lack an extended formulation of polynomial size.

Uno dei possibili approcci risolutivi per problemi lineari interi consiste nell'utilizzo di formulazioni estese, ovvero la tecnica di esprimere l'inviluppo convesso delle corrispondenti regioni ammissibili in uno spazio di dimensione maggiore aumentando il numero di variabili, al fine di ridurre il numero di vincoli (size). L'obiettivo è fare in modo che, al crescere del numero n di variabili del problema originale, la size cresca al più come un polinomio in n, in modo da poter utilizzare un algoritmo risolutivo fornito dalla teoria della Programmazione Lineare. In questa trattazione andiamo ad analizzare le limitazioni di tale approccio, che lo rendono talvolta impraticabile. In particolare ci concentriamo su un risultato di Yannakakis del 1991, che stabilisce un primo limite inferiore alla size di una formulazione estesa, collegato al concetto di rango non-negativo della matrice di slack del politopo che descrive il problema. Descriviamo poi un argomento esposto da Rothvoß nel 2011, in cui viene dimostrato che esistono problemi lineari interi privi di una formulazione estesa di size polinomiale.