4 Presentations

• 
  10:30 AM - 10:55 AM

  Combining Lagrangean relaxation and Benders decomposition to solve a tight linearization of binary quadratic programs

  • Andrea Lodi, Polytechnique Montreal
  • Borzou Rostami, École de technologie supérieure
  • Carlos Zetina, presenter, CIRRELT

  We present an algorithm that combines Lagrangean relaxation and Benders decomposition to solve a tight linearization of general binary quadratic programs. For the case of single allocation hub location, we derive a closed form to calculate optimal Lagrangean multipliers of a set of coupling constraints which we relax. This allows for the decomposition of the Benders subproblem and the use of a multi-cut Benders decomposition without compromising the strength of the obtained Benders cuts. Computational experiments show this to be a promising method.
• 
  10:55 AM - 11:20 AM

  A Benders decomposition based algorithm for the quadratic capacitated hub location problem

  • Emine Gündoğdu, presenter, CIRRELT and UdeM
  • Sinan Gürel, Middle East Technical University, Ankara, Turkey

  We consider a hub location problem where both the objective function and capacity constraints have nonlinear terms consisting of multiplication of binary variables. We propose an exact branch-and-check algorithm. In the algorithm, we generate feasibility and optimality cuts and compare the performance of this algorithm with two different optimality cuts.

  Keywords: Benders Decomposition Based Algorithm, Nonlinear Hub Location Problem, MIQCP
• 
  11:20 AM - 11:45 AM

  Exact algorithms for multilevel capacitated facility location problems with concave costs

  • Aditya Malik, presenter, John Molson School of Business
  • Ivan Contreras, Université Concordia
  • Navneet Vidyarthi, Concordia University

  We study multi-level capacitated facility location problems with concave costs in which production, warehousing, and distribution costs are considered to be concave functions of the quantities produced, stored and distributed. We present and compare two exact branch-and-bound algorithms based on a mixed-integer nonlinear program and on a pure nonlinear continuous program.
• 
  11:45 AM - 12:10 PM

  Benders decomposition for large-scale quadratic capacitated facility location

  • Ivan Contreras, presenter, Université Concordia
  • Carlos Zetina, CIRRELT
  • Sachin Jayaswal, Indian Institute of Management Ahmedabad
  • Navneet Vidyarthi, Concordia University

  We study a class of quadratic capacitated p-location problems with single assignments where a non-convex quadratic term is introduced to account for the interaction cost between facilities and customer assignments. We propose an exact branch-and-cut algorithm based a Benders reformulation in which the network flow structure is exploited to efficiently separate cuts.