Lift and Project Methods for Machine Scheduling Through Theory and Experiments

Lift and projects methods, such as the hierarchies parameterized by a number of levels or rounds, are systematic approaches to design improved approximation algorithms by gradually tightening the integrality gap between the integer formulation and corresponding relaxation, at the cost of increased running time. For many problems the approximation factors of the best available relaxations are obtained by performing a constant number of rounds of these hierarchies. In the scheduling context only very few and very recent results are known that uses lift and project methods. Levey and Rothvoss give a $1+\varepsilon$ approximation algorithm for $Pm|prec, p_j = 1|C_{max}$ using $(\log(n))^{\Theta(\log \log n)}$ rounds of Sherali Adams (SA) hierarchy. After many years this is the only advance for a problem that is one of two problems remaining open in the list of Garey and Johnson's book and it is obtained by a weaker form of the Lasserre hierarchy. The recent breakthrough by Bansal, Srinivasan and Svensson shows that by using the first round of the Lasserre hierarchy it is possible to obtain a $(\frac{3}{2}-c)$-approximation algorithm with a small constant $c>0$ for the general problem of scheduling on unrelated parallel machine to minimizing the weighted completion times, solving a widely proposed open problem. Again this result is obtained by the Lasserre hierarchy. From the negative result point of view, we obtained the only known limitations of these hierarchies when applied to scheduling problems. For the Min-Sum scheduling problem (i.e., scheduling with job dependent cost functions on one machine) the integrality gap is unbounded even after $O(\sqrt{n})$ rounds of Lasserre. We proved that the configuration~LP for makespan scheduling on identical parallel machines admits a constant size gap even after $\Omega(n)$ number of rounds of PSD Â Lov\'asz-Schrijver and Sherali-Adams hierarchy. Besides the above results not much more is known for scheduling even though the technique is considered a ``hot topic'' for approximation algorithms. Indeed, hierarchies are a strong tool for approximation algorithms that might find strong applications also in scheduling as evidenced by the above 2 examples. Within projects 200020-109854 and 200020-122110/1 Approximation Algorithms for Machine Scheduling Through Theory and Experiments, we have inquired into some of the main problems in the area of machine scheduling and successfully addressed well-known open problems. The obtained results have been the first important advances on the open questions stated in Schuurman and Woeginger which have been open for more than 20 years by now. Within the last project 200020-144491/1 we have, among other results, deepen our knowledge about lift and project methods and obtained upper and lower bounds together with new tools and techniques for analyzing the Lasserre hierarchy by solving some open questions, simplifying and generalizing previous results and obtaining new tight bounds and analysis. We now need to focus this investigation to better exploit the competence and the noticeable experience we have developed on the mentioned problems and to verify new ideas and apply new techniques. More precisely, in this research project we want to investigate on the following topics.[Lift and Project Methods for Scheduling in Theory:] Within this project we want to deepen our understanding of these lift and project methods. More precisely we want to study the strengths and weaknesses of this technique when applied to basic and fundamental scheduling problems. While aiming to this goal it will be necessary to develop new methods and obtain basic results to analyze these relaxations. Indeed, only very few approaches are in general known for analyzing the Lasserre hierarchy and understanding this hierarchy is in general considered a very difficult task. These results can be of independent interest and can find applications in a broader context (as it happened for example in our recent papers we developed several techniques and prove several lower bounds not only related to scheduling).[Lift and Project Methods for Scheduling in Practice:] One critical area that we plan to address concerns how to make these methods practical. Lift and projects methods, like the Lasserre hierarchy, have been so far of highly theoretical interest but, to the best of our knowledge, with very limited or no practical applications in the area of approximation algorithms. Even problem-specific approaches would be very useful, but they too seem hard to come by. The IDSIA project team has developed many heuristics for several problems which have no worst-case guarantees on performance, but do well for typical problems. Our goal is to combine mathematical rigor and our expertise in heuristics methods to answer a question such as: Are these lift and project methods applicable also in practice? We plan to understand the applicability of these methods.