/system/images/000/000/219/Logo_Journ_es_Optimisation__2012_Outl_default.png

Including an Industrial Optimization Day

HEC Montréal, May 7 - 9, 2012

JOPT2012

HEC Montréal, May 7 — 9, 2012

Schedule Authors My Schedule
Cal add eabad1550a3cf3ed9646c36511a21a854fcb401e3247c61aefa77286b00fe402

WB8 Dégénérescence en optimisation lisse / Degeneracy in Smooth Optimization

May 9, 2012 11:00 AM – 12:15 PM

Location: Transat

Chaired by Dominique Orban

3 Presentations

  • Cal add eabad1550a3cf3ed9646c36511a21a854fcb401e3247c61aefa77286b00fe402
    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.

  • Cal add eabad1550a3cf3ed9646c36511a21a854fcb401e3247c61aefa77286b00fe402
    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.

  • Cal add eabad1550a3cf3ed9646c36511a21a854fcb401e3247c61aefa77286b00fe402
    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.

Back