Branch-and-cut for SOS1 constrained linear problems

Branch-and-cut for SOS1 constrained linear problems

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

Outline Problem definition and formulation Valid inequalities Instances tested, Platform and Parameters used Computational results Continued research Acknowledgement Integer Programming with Complementarity Constraints Ismael de Farias MINLP 2014 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 Ismael de Farias

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

Ismael de Farias MINLP 2014 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 Ismael de Farias MINLP 2014

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 Ismael de Farias MINLP 2014

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

MINLP 2014 9/20 Instances and Platform Texas Techs 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 Ismael de Farias

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

Results Continuous instances: solution time Time with Default 82 + Time with Default SOS1 Cuts % Time with Default Time with Default + SOS1 Cuts 800 100

0 Integer Programming with Complementarity Constraints Ismael de Farias 180 0 900 12 % MINLP 2014 13/ 20

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

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

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

Ismael de Farias MINLP 2014 17/ 20 Results Better strategy (with or without SOS1 cuts) Number of instances solved more efficiently with each method Integer Programming with Complementarity Constraints Ismael de Farias MINLP 2014

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 Ismael de Farias

MINLP 2014 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 Ismael de Farias MINLP 2014 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 Ismael de Farias

MINLP 2014 21/ 20

Recently Viewed Presentations

  • Development of TCM Internal Medicine - Acupuncture People

    Development of TCM Internal Medicine - Acupuncture People

    * * * * * * Formula: Modifications: Fever due to Kidney yin def. -- Zhi Bai Di Huang Wan; Kidney Yang def. -- You Gui Wan; Wu Bi Shan Yao Wan Shan yao Rou Cong Rong Tu Si Zi...
  • Professor Jorg Steinbach - Engineering Council

    Professor Jorg Steinbach - Engineering Council

    Jörg Steinbach Vice-president of the Technische Universität Berlin Past-President of SEFI * * Accreditation Accreditation is a process in which certification of competency, authority, or credibility is presented. Organizations that issue credentials or certify third parties against official ...
  • Western Front Battles - yardvmc

    Western Front Battles - yardvmc

    The battle field was covered with mud and craters due to torrential rains and previous attacks which had destroyed drainage systems The soldiers, animals, arms and provisions were all stuck in the mud More than 16 000 Canadian casualties The...
  • NCI CBIIT Re-engaged

    NCI CBIIT Re-engaged

    The views expressed are my own and not a reflection of DHHS, NIH or NCI policy. Some history. Back to the dawn of time…my first BRIITE. And some very emotional imagery. BRIITE 2001. November 16 and 17th. ... RAS Initiative...
  • KAHOOT-OPANA Log onto Kahoot.it on your phone browser

    KAHOOT-OPANA Log onto Kahoot.it on your phone browser

    Log onto "Kahoot.it" on your phone browser. Enter game PIN code from the main screen. Type in your nickname. Look at the main screen and use your device as a controller to make your answer
  • What's in your wallet? - Meetup

    What's in your wallet? - Meetup

    Need a predictive approach from available data Firmographics (Sales, Industry, Employees) IBM Sales and transaction history Existing Approaches to Wallet Modeling Bottom up: learn a model for individual companies Get "true" wallet values through surveys Very expensive Small, typically not...
  • Reading and Writing KS2 - Moorgate

    Reading and Writing KS2 - Moorgate

    Journalistic Writing and diaries. Poems - personification and powerful imagery. Letters - Formal and informal . ... children are expected to join their letters fluently and develop their own neat, cursive style. We use a cursive handwriting style with our...
  • Department of Computer Science Undergraduate Events More details

    Department of Computer Science Undergraduate Events More details

    Slide . MDPs: Policy. The robot needs to know what to do as the decision process unfolds… It starts in a state, selects an action, ends up in another state selects another action….