3 Presentations

• 
  11:00 AM - 11:25 AM

  Customizing the Solution Process of COIN-OR's Linear Solvers with Python

  • Mehdi Towhidi, presenter, École Polytechnique de Montréal
  • Dominique Orban, GERAD - Polytechnique Montréal

  We introduce CyLP, an open-source application to model and solve linear and mixed-integer linear programs in Python. CyLP wraps around solvers from COINOR---a repository of open-source optimization software. In addition to a mere interface, CyLP allows modification of the solution process via python scripts. In linear programming, users can easily define customized pivot rules. In MIPs, CyLP allows users to customize the branch-and-cut tree transversal method. We illustrate these features by implementing the positive edge pivot rule, an efficient pivot rule for degenerate linear programs.

• 
  11:25 AM - 11:50 AM

  Superlinear Convergence of Primal-Dual Interior-Point Methods in the Absence of Strict Complementarity

  • Zoumana Coulibaly, presenter, École Polytechnique de Montréal

  In the absence of strict complementarity, the powerful interior-point methods exhibit, in the best case, a linear convergence rate on nonlinear problems. In this talk, we propose a cheap and
  efficient dual update strategy to recover the Q-superlinear convergence of the iterates. We present numerical results on a test set of non strictly complementary problems.

• 
  11:50 AM - 12:15 PM

  The Bitter Truth About Interior-Point Methods

  • Dominique Orban, presenter, GERAD - Polytechnique Montréal
  • Chen Greif, University of British Columbia
  • Erin Moulding, University of British Columbia

  Interior-point methods feature prominently in the solution of constrained optimization problems, and involve the need to solve a sequence of 3x3 block indefinite system which become increasingly ill-conditioned throughout the iteration. To solve these systems, it is common practice to perform a block Gaussian elimination, and then either solve the resulting reduced 2x2 block indefinite system that has a typical saddle-point form, or further reduce the system to the normal equations and apply a symmetric positive-definite solver. We explore whether the step of reducing the system from 3x3 block form to a 2x2 block form necessarily pays off. We use energy estimates to obtain bounds on the eigenvalues of the matrices in question, which indicate that in fact at least in terms of spectral structure, it may be better to keep the system in its original unreduced form rather than perform a partial elimination.