Report

Integer Programming with Complementarity Constraints Ismael R. de Farias, Jr. 1 Joint work with Ernee Kozyreff 1 and Ming Zhao 2 1Texas Tech 2SAS Outline Problem definition and formulation Valid inequalities Instances tested, Platform and Parameters used Computational results Continued research Acknowledgement Integer Programming with Complementarity Constraints MINLP 2014 Ismael de Farias 2/20 Problem definition Definition A set of variables is a special ordered set of type 1, or a SOS1, if, in the problem solution, at most one variable in the set can be non-zero. We will restrict ourselves to nonintersecting SOS1s Applications Transportation Scheduling Map display Integer Programming with Complementarity Constraints MINLP 2014 Ismael de Farias 3/20 Problem definition Integer Programming with Complementarity Constraints MINLP 2014 Ismael de Farias 4/20 Problem definition Integer Programming with Complementarity Constraints MINLP 2014 Ismael de Farias 5/20 Formulation SOS1 branching “Usual” MIP formulation (Dantzig, 1960) “Log” formulation (Vielma and Nemhauser, 2010; also Vielma, Ahmed, and Nemhauser, 2012) Comparison over 1,260 instances Usual MIP Log Instances solved 806 503 Wins (faster) 799 81 Integer Programming with Complementarity Constraints MINLP 2014 Ismael de Farias 6/20 SOS1 cutting planes Two families of facet defining Lifted Cover Inequalities derived in de Farias et al (2002) (not tested computationally), and improved in de Farias et al (2014), which are valid for where Integer Programming with Complementarity Constraints MINLP 2014 Ismael de Farias 7/20 SOS1 Cut 1 Integer Programming with Complementarity Constraints MINLP 2014 Ismael de Farias 8/20 SOS1 Cut 2 Integer Programming with Complementarity Constraints MINLP 2014 Ismael de Farias 9/20 Instances and Platform Texas Tech’s High Performance Computer Center Intel Xeon 2.8 GHz, 24GB RAM, 1024 nodes Integer Programming with Complementarity Constraints MINLP 2014 Ismael de Farias 10/20 MIP solver and Parameters tested GUROBI 5.0.1 in… Branch-and-bound Branch-and-bound + SOS1 Cuts Default Default + SOS1 Cuts * Branch-and-bound = Default – Presolve – MIP Cuts – Heuristics Maximum number of cuts derived: 1,000 of each type Maximum CPU time allowed: 3,600 seconds Integer Programming with Complementarity Constraints MINLP 2014 Ismael de Farias 11/20 Results Continuous instances: number of instances solved Integer Programming with Complementarity Constraints MINLP 2014 Ismael de Farias 12/20 Results Continuous instances: solution time Time with Default 1800 Time with Default 82% + SOS1 Cuts 900 Time with Default 12% 800 Time with Default + SOS1 Cuts 1000 Integer Programming with Complementarity Constraints MINLP 2014 Ismael de Farias 13/20 Results Binary instances: number of instances solved Integer Programming with Complementarity Constraints MINLP 2014 Ismael de Farias 14/20 Results Binary instances: solution time 13% 39% Integer Programming with Complementarity Constraints MINLP 2014 Ismael de Farias 15/20 Results 10,000-IP instances: number of instances solved Integer Programming with Complementarity Constraints MINLP 2014 Ismael de Farias 16/20 Results 10,000-IP instances: solution time 96% 0.2% Integer Programming with Complementarity Constraints MINLP 2014 Ismael de Farias 17/20 Results Better strategy (with or without SOS1 cuts) Number of instances solved more efficiently with each method Integer Programming with Complementarity Constraints MINLP 2014 Ismael de Farias 18/20 Summary of results The use of SOS1 cuts was imperative on our continuous and general integer instances. “Usual” MIP formulation for SOS1 performed better than the “Log” formulation. Integer Programming with Complementarity Constraints MINLP 2014 Ismael de Farias 19/20 Continued Research Why were SOS1 cuts so effective for problems with integer variables with large values of u? How can SOS1 cuts be modified to be effective for the case of binary variables? Study branching strategies for SOS1 Study problems with both positive and negative coefficients in the constraint matrix Study solution approaches to KKT systems, in particular LCP Integer Programming with Complementarity Constraints MINLP 2014 Ismael de Farias 20/20 Acknowledgement We are grateful to the Office of Naval Research for partial support to this work through grant N000141310041 Integer Programming with Complementarity Constraints MINLP 2014 Ismael de Farias 21/20