Integer Programming with Complementarity Constraints by Ismael R. de Farias, Jr.

This work by Ismael R. de Farias, Jr. explores Integer Programming with Complementarity Constraints, focusing on problem definitions, formulations, SOS1 branching, cutting planes, and computational results. The study includes applications in transportation scheduling and map display, along with comparisons between different formulations and instances tested.

• Integer Programming
• Complementarity Constraints
• Optimization
• Formulations
• Cutting Planes

villescas_b Follow

Uploaded on Sep 21, 2024 | 0 Views

Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

Presentation Transcript

1. Integer Programming with Complementarity Constraints Ismael R. de Farias, Jr. 1 Joint work with Ernee Kozyreff1and Ming Zhao 2 1Texas Tech 2SAS

2. 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

3. 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

4. Problem definition Integer Programming with Complementarity Constraints MINLP 2014 Ismael de Farias 4/20

5. Problem definition Integer Programming with Complementarity Constraints MINLP 2014 Ismael de Farias 5/20

6. 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

7. 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

8. SOS1 Cut 1 Integer Programming with Complementarity Constraints MINLP 2014 Ismael de Farias 8/20

9. SOS1 Cut 2 Integer Programming with Complementarity Constraints MINLP 2014 Ismael de Farias 9/20

10. 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

11. 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

12. Results Continuous instances: number of instances solved Integer Programming with Complementarity Constraints MINLP 2014 Ismael de Farias 12/20

13. Results Continuous instances: solution time Time with Default 1800 82% Time with Default + SOS1 Cuts 900 12% Time with Default 800 Time with Default + SOS1 Cuts 1000 Integer Programming with Complementarity Constraints MINLP 2014 Ismael de Farias 13/20

14. Results Binary instances: number of instances solved Integer Programming with Complementarity Constraints MINLP 2014 Ismael de Farias 14/20

15. Results Binary instances: solution time 13% 39% Integer Programming with Complementarity Constraints MINLP 2014 Ismael de Farias 15/20

16. Results 10,000-IP instances: number of instances solved Integer Programming with Complementarity Constraints MINLP 2014 Ismael de Farias 16/20

17. Results 10,000-IP instances: solution time 96% 0.2% Integer Programming with Complementarity Constraints MINLP 2014 Ismael de Farias 17/20

18. 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

19. 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

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

21. 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