3 Presentations

• 
  11:30 AM - 11:55 AM

  A column generation approach for the recursive circle packing problem

  • Ambros Gleixner, Zuse Institute Berlin
  • Stephen Maher, presenter, Lancaster University
  • Benjamin Mueller, Zuse Institute Berlin
  • Joao Pedro Pedroso, Faculdade de Ciências, Universidade do Porto

  Packing rings into a minimum number of rectangles is an optimization problem that appears naturally in the logistics operations of the tube industry. Considering each rectangle as a transportation container, minimal transportation costs are given by recursively packing rings into the smallest number of rectangles. No exact solution methods exist for the recursive circle packing problem (RCPP)---a more difficult variant of the circle packing problem---with the best heuristic algorithms only able to find solutions for small instances. A cutting stock formulation of the RCPP is described that reduces the difficulty of the problem that arises due to the recursive nature. An exact column generation algorithm is developed by applying a Dantzig-Wolfe reformulation to the cutting stock formulation of the RCPP. The exact column generation algorithm is demonstrated to outperform previous heuristic approches by providing improved upper bound solutions and strong lower bounds for a large collection of test instances.

• 
  11:55 AM - 12:20 PM

  Logical Benders Decomposition for Quadratic Programs with Complementarity Constraints and Binary Variables

  • John Mitchell, presenter, RPI
  • Jong-Shi Pang, University of Southern California
  • Andreas Wächter, Northwestern University
  • Francisco Jara-Moroni, Northwestern University

  We study a logical Benders decomposition approach to solving binary-constrained quadratic programs with linear complementarity constraints. It is based on a satisfiability master problem to which feasibility cuts are added that are computed from primal and dual subproblems for chosen complementarity pieces and binary variables. Interpreting the logical Benders decomposition approach from a branch-and-bound point of view, we propose several new methods for strengthening the feasibility cuts and guiding the master problem solution. Their efficiency is assessed by numerical experiments.

• 
  12:20 PM - 12:45 PM

  Adding robustness and speeding up the hybrid approach for interior point methods linear system solution

  • Aurelio Oliveira, presenter, Unicamp
  • Cecilia Castro, University of Campinas
  • Manolo Heredia, University of Campinas

  Modifications in the controlled Cholesky factorization (CCF) parameters and a new basis choice for the splitting preconditioner are proposed. The goal is to add robustness and speed up the hybrid approach to solve the linear systems arising from interior point methods. The parameters that control the fill-in and the diagonal fault correction approach are improved reducing restarts when computing the CCF. Regarding the splitting preconditioner, new column orderings are used in order to guarantee a condition number uniformly limited by a constant which depends only upon the original data. Numerical results with large-scale LP problems illustrate the new approach efficiency.