4 Presentations

• 
  03:30 PM - 03:55 PM

  Some new Perspectives on Solving BIP Using Balas Method

  • Joseph Ryan Glover, Ryerson University
  • Vinh Quan, presenter, University of Toronto at Scarborough
  • Saeed Zolfaghari, Ryerson University

  We will show that when using the best-first search strategy with Balas’ additive algorithm for solving 0-1 integer programming problems, the first candidate solution found is the optimal solution. In addition, a simple record keeping method for depth-first search or LIFO is presented. The method provides the ability to calculate, at any point of the search, the theoretical maximum number of remaining nodes to be evaluated in the B&B tree. Finally, we will show the many benefits derived from ordering the objective function coefficients prior to solving the problem.

• 
  03:55 PM - 04:20 PM

  Incorporating Dantzig-Wolfe Decomposition Into Branch and Bound by Cutting Planes

  • Rui Chen, presenter, Cornell Tech
  • Oktay Gunluk, Cornell ORIE
  • Andrea Lodi, Cornell Tech

  Dantzig-Wolfe (DW) decomposition is a well-known technique in mixed integer programming (MIP) for decomposing and convexifying constraints to obtain potentially strong dual bounds. We investigate Fenchel cuts that are derivable from DW decomposition and show that they can provide equally strong bounds as DW decomposition. These cuts in the primal space can be incorporated into a standard branch-and-cut algorithm to utilize the dual information obtained from DW decomposition. We test our approach on MIP problems where DW decomposition can efficiently provide strong dual bounds. Numerical results show that the proposed cuts are helpful for accelerating the solution of such problems under the branch-and-cut framework without the sophistication of implementing branch and price.

• 
  04:20 PM - 04:45 PM

  Une méthode de décomposition basée sur l'interaction d'approximations internes et externes de polyèdres connus implicitement

  • Francois Lamothe, presenter, UQAM

  Le renforcement des relaxations linéaires des programmes linéaires en nombres entiers est un sujet de recherche actif depuis des décennies. En effet, de nombreuses méthodes, tel que le Branch and Bound, utilisent les bornes renvoyées par ces relaxation pour accélérer leur résolution ou produire des solutions de meilleure qualité. Dans cette présentation, nous étudions ces renforcements sous l'angle des méthodes de décomposition comme les décompositions de Dantzig-Wolfe et de Fenchel. Nous commençons par présenter géométriquement ces méthodes en montrant qu'elles créent des approximations internes ou externes d'un polyèdre qu'elles cherchent à approcher. Puis, nous présentons une nouvelle méthode de décomposition. Celle-ci utilise un problème maître de Dantzig-Wolfe pour créer une approximation interne, un problème maître de Fenchel pour créer une approximation externe et un sous-problème de Fenchel pour gérer l'interaction entre ces deux approximations. Cette nouvelle méthode a été comparée expérimentalement avec les méthodes de la littérature sur des instances du problème de flot insécable et a obtenu des résultats très prometteurs.

• 
  04:45 PM - 05:10 PM

  Automated Repair of Layout Bugs in Web Pages with Linear Programming

  • Stéphane Jacquet, presenter, Polytechnique Montréal
  • Xavier Chamberland-Thibeault, Université du Québec à Chicoutimi
  • Sylvain Hallé, Université du Québec à Chicoutimi

  In some webpages, there are layout bugs that are caused by overlapping, misalignments or the protruding of some of its elements. We suggest a technique to apply corrections by using a Mixed
  Integer Linear Programming formulation. A solver then gives the new characteristics of the elements of the web page, which are then incorporated into the web page. The approach has been implemented and tested
  on samples of real-world web pages; describing a zone of influence aims to reduce the size
  of the optimization problem, and a solution can often be computed in a few seconds
  on commodity hardware.