Limitations of linear programming as a model of approximate computation

Abstract

Linear programming has proved to be one of the most powerful and widely used tools inalgorithm design and especially in the design of approximation algorithms. It has provedits expressive power by modeling diverse types of problems in planning, routing, scheduling,assignment, and design. The popularity of linear programming raised the questionwhether for every algorithm there is a linear formulation or relaxation that captures itsmerits.In the last decade, the virtual "completeness" of linear programming-based algorithms wasquestioned. Although this line of thought goes at least as back as the late 80s with thefamous work of Yannakakis [66], it wasn’t until the early 00’s that the community startedto systematically study the limitations of linear programming methods. In particular,the first line of results that incarnated that questioning was the proof of the limitationsof lift-and-project methods for solving various problems. Those methods, when appliedto a relaxation, define hierarchies of increasingly strengthened relaxations. Their poweris such that proving a hardness result for some problem for a lift and project hierarchycan be taken as evidence that linear programming in general cannot efficiently solve thatproblem.Exploring the power of linear programming for combinatorial optimization problems hasbeen recently receiving renewed attention through the model of Extended Formulations.In this model we are concerned whether there are compact formulations or approximaterelaxations for combinatorial optimization problems, allowing the use of any set or typeof variables. The model of Extended Formulations is more general than that of lift-andprojecthierarchies and is arguably the most general model that truly captures pure linearprogramming methods.In this thesis we take the direction of exploring the limitation of linear programming.Most of the thesis’s results are concerned with linear programming approximability of thecapacitated versions of the metric facility location problem such as the capacitated facilitylocation (Cfl) and lower bounded facility location (Lbfl), problems which, while they canbe approximated within a constant factor using local search, they are not known to admit efficient relaxation based approximations. The failure for many years of the combinatorialoptimization community to devise efficient relaxations for such problems has created acertain sensation. We give impossibility results in the hierarchy and in the extendedformulations models and we also consider an other, independent family of relaxations.We note that our ideas and methods are of general value and independent interest. Thisis especially true for the extended formulations where we devise a general method forlower bounding the size of linear programs.Regarding our hierarchy related results, we show that the relaxations obtained from thenatural LP at Ω(n) levels of the semidefinite Lovasz-Schrijver hierarchy for mixed pro- ´grams, and at Ω(n) levels of the Sherali-Adams hierarchy, have an integrality gap of Ω(n),where n is the number of facilities of the instance. Both hierarchies yield an exact for-mulation for Cfl in at most n levels for the families of instances we consider and thusour bounds are asymptotically tight. For the families of instances we consider, bothhierarchies yield at the nth level an exact formulation for Cfl. Thus our bounds areasymptotically tight. Building on our methodology for the Sherali-Adams result, we provethat the standard Cfl relaxation enriched with the submodular inequalities of [1], a generalizationof the flow-cover valid inequalities, has also an Ω(n) gap and thus not boundedby any constant. This disproves a long-standing conjecture of [46].We propose a framework for proving lower bounds on the size of extended formulations.We do so by introducing specific types of extended relaxations that we call product anddistributional relaxations. Then we show that for every approximate extended formulationof a polytope P, there is a product or distributional relaxation that has the same size andis at least as strong. We provide a methodology for proving lower bounds on the sizeof approximate product and distributional relaxations by lower bounding the chromaticnumber of an underlying hypergraph, whose vertices correspond to gap-inducing vectors.As an application of our method we show for Cfl an exponential lower bound on the sizeof a restricted type of extended formulations which we call mixed product relaxations.We finally introduce the family of proper relaxations which generalizes to its logical extremethe classic star relaxation and captures general configuration-style LPs. We characterizethe behavior of proper relaxations for Cfl and Lbfl through a sharp threshold phenomenon.

Ο Γραµµικός Προγραµµατισµός έχει αποδειχθεί ως ένα από τα ισχυρότερα και ευρέως χρησιµοποιούµενα εργαλεία όσον αφορά τη σχεδίαση αλγορίθµων και ιδιαίτερα των προσεγγιστικών αλγορίθµων. Η εκφραστική του δύναµη είναι εµφανής στη µοντελοποίηση προβληµάτων διαφόρων τύπων όπως τη δροµολόγηση, τον χρονοπρογραµµατισµό εργασιών και την ανάθεση πόρων. Η δηµοφιλία του Γραµµικού Προγραµµατισµού έγειρε το ερώτηµα αν για κάθε αλγόριθµο υπάρχει ένα ισοδύναµο γραµµικό πρόγραµµα. Την περασµένη δεκαετία η ϕαινοµενική ¨πληρότητα¨ του γραµµικού προγραµµατισµού αµϕισβητήθηκε. Αν και η αµφισβήτηση αυτή µπορεί να ανιχνευτεί τουλάχιστον από τα τέλη της δεκαετίας του 1980 µε την περίφηµη εργασία του Γιαννακάκη [66], µόνο στις αρχές της δεκαετίας του 2000 η κοινότητα άρχισε συστηµατικά να µελετά τους περιορισµούς µεθόδων γραµµικού προγραµµατισµού. Πιο συγκεκριµένα, η πρώτη γραµµή αποτελεσµάτων που πραγµάτωνε αυτή την αµφισβήτηση είχε να κάνει µε την απόδειξη των περιορισµών τωνlift-and-project µεθόδων για την επίλυση διαφόρων προβληµάτων. Αυτές οι µέθοδοι, όταν εφαρµοστούν σε µία γραµµική χαλάρωση, ορίζουν µία ιεραρχία γραµµικών χαλαρώσεων αυξανοµένης ισχύος. Η δύναµή τους είναι τέτοια ώστε ένα αρνητικό αποτέλεσµα για κάποιο πρόβληµα για µία lift-and-project ιεραρχία µπορεί να ερµηνευθεί ως ένδειξη της αδυναµίας του γραµµικού προγραµµατισµού να λύσει το πρόβληµα. Η εξερεύνηση της δύναµης του γραµµικού προγραµµατισµού έλαβε το ανανεωµένο ενδιαφέρον της κοινότητας µέσω του µοντέλου των Extended Formulations. Ο στόχος του µοντέλου αυτού είναι να απαντηθεί αν υπάρχει ή όχι µικρού µεγέθους γραµµική χαλάρωση για ένα πρόβληµα επιτρέποντας τη χρήση οποιουδήποτε συνόλου µεταβλητών. Το µοντέλο τωνExtended Formulations είναι πιο γενικό από αυτό των lift-and-project ιεραρχιών και µπορεί κάλλιστα να υποστηριχθεί ότι εύστοχα περιγράφει την δύναµη του γραµµικού προγραµµατισµού. Σε αυτή τη διατριβή επιλέχθηκε ο δρόµος της µελέτης των περιορισµών του γραµµικού προγραµµατισµού.Τα περισσότερα από τα αποτελέσµατα που παρουσιάζονται έχουν να κάνουνµε την προσεγγισιµότητα µέσω γραµµικού προγραµµατισµού facility location προβληµάτων µε χωρητικότητες όπως το capacitated facility location (Cfl) και το lower bounded facilitylocation (Lbfl), προβλήµατα για τα οποία, αν και µπορούν να προσεγγιστούν µε σταθερό λόγο προσέγγισης, δεν είναι γνωστό αν υπάρχει αποτελεσµατικός προσεγγιστικός αλγόριθµος ϐασισµένος σε γραµµική χαλάρωση. Η επί πολλά έτη αποτυχία της κοινότητας να ϐρειµία τέτοια χαλάρωση έχει προκαλέσει αίσθηση. ∆ίνουµε αρνητικά αποτελέσµατα στα µοντέλα των ιεραρχιών και των extended formulations και επίσης µελετούµε µία ανεξάρτητη από τα προηγούµενα οικογένεια χαλαρώσεων. Επισηµαίνουµε ότι οι ιδέες και οι µέθοδοι είναι γενικότερης αξίας και όχι αναγκαστικά συνυφασµένες µε κάποιο συγκεκριµένο πρόβληµα. Αυτό έχει ιδιαίτερη ισχύ για τα extended formulations όπου σχεδιάζουµε µία καινούρια µέθοδο για τη ϕραγή από κάτω του µεγέθους των γραµµικών προγραµµάτων. Σχετικά µε τα αποτελέσµατά µας σε ιεραρχίες, δείχνουµε ότι οι χαλαρώσεις που προκύπτουν από το κλασσικό γραµµικό πρόγραµµα για το Cfl σε Ω(n) επίπεδα της semidefiniteLovasz-Schrijver ´ ιεραρχίας για mixed προγράµµατα και σε Ω(n) επίπεδα της Sherali-Adams ιεραρχίας, έχουν integrality gap Ω(n). Και οι δύο ιεραρχίες δίνουν ένα ακριβές formulationτο πολύ σε n επίπεδα και εποµένως τα αποτελέσµατά µας είναι ασυµπτωτικά σφικτά. Χρησιµοποιώντας τις ιδέες και τις µεθόδους που αναπτύχθηκαν για το αποτέλεσµα για τηνSherali-Adams ιεραρχία, αποδεικνύουµε ότι το κλασσικό γραµµικό πρόγραµµα για το Cflέχει µη ϕραγµένο integrality gap ακόµα και µετά την εισαγωγή των submodular inequalitiesτου [1], µία γενίκευση των flow-cover valid inequalities. Το τελευταίο αποτέλεσµα απαντά αρνητικά σε µία επί χρόνια ανοικτή εικασία [46]. Προτείνουµε µία µεθοδολογία για το ϕράξιµο του µεγέθους των extended formulations. Αυτό το πετυχαίνουµε κάνοντας χρήση συγκεκριµένων τύπων extended formulations που ορίζουµε, τα product και τα distributional relaxations. ΄Επειτα αποδεικνύουµε ότι για οποιοδήποτε προσεγγιστικό extended formulation ενός πολυτόπου P υπάρχει ένα productή distributional formulation που έχει το ίδιο µέγεθος και είναι τουλάχιστον το ίδιο ισχυρό. ∆ίνουµε µία µέθοδο απόδειξης κάτω ϕραγµάτων για προσεγγιστικά product και distributionalrelaxations µε το να ϕράσσεται ο χρωµατικός αριθµός ενός σχετικού υπεργραφήµατος, του οποίου οι κορυφές αντιστοιχούν σε διανύσµατα που προκαλούν gap. Ως εφαρµογή της µεθοδολογίας µας δείχνουµε εκθετικό ϕράγµα στο µέγεθος για το Cfl ενός ειδικού τύπουextended formulations τα οποία ονοµάζουµε mixed product relaxations. Τέλος εισάγουµε και µελετούµε την οικογένεια των proper relaxations τα οποία γενικεύουν το star relaxation και µοντελοποιεί γενικά configuration-style LPs. Χαρακτηρίζουµε τη συµπεριφορά των proper relaxations για το Cfl και Lbfl µέσω ενός ϕαινοµένου κατωφλίου.