Jacek Gondzio

Polynomial worst-case iteration complexity of quasi-Newton primal-dual interior point algorithms for linear programming

  • Francisco N. C. Sobral
  • Jacek Gondzio
    • Categories Linear Programming, Linear, Cone and Semidefinite Programming, Nonlinear Optimization Tags , , ,

    Quasi-Newton methods are well known techniques for large-scale numerical optimization. They use an approximation of the Hessian in optimization problems or the Jacobian in system of nonlinear equations. In the Interior Point context, quasi-Newton algorithms compute low-rank updates of the matrix associated with the Newton systems, instead of computing it from scratch at every iteration. … Read more

    A Sparse Interior Point Method for Linear Programs arising in Discrete Optimal Transport

  • Filippo Zanetti
  • Jacek Gondzio
    • Categories Convex Optimization, Linear Programming, Transportation Tags , , , ,

    Discrete Optimal Transport problems give rise to very large linear programs (LP) with a particular structure of the constraint matrix. In this paper we present an interior point method (IPM) specialized for the LP originating from the Kantorovich Optimal Transport problem. Knowing that optimal solutions of such problems display a high degree of sparsity, we … Read more

    A new stopping criterion for Krylov solvers applied in Interior Point Methods

  • Jacek Gondzio
  • Filippo Zanetti
    • Categories Convex Optimization Tags , , , ,

    A surprising result is presented in this paper with possible far reaching consequences for any optimization technique which relies on Krylov subspace methods employed to solve the underlying linear equation systems. In this paper the advantages of the new technique are illustrated in the context of Interior Point Methods (IPMs). When an iterative method is … Read more

    A new matheuristic and improved instance generation for kidney exchange programmes

  • Maxence Delorme
  • Jacek Gondzio
  • William Pettersson
  • Sergio García
  • Joerg Kalcsics
  • David Manlove
  • James Trimble
    • Categories Biomedical Applications, Combinatorial Optimization Tags , ,

    Kidney exchange programmes increase the rate of living donor kidney transplants, and operations research techniques are vital to such programmes. These techniques, as well as changes to policy regarding kidney exchange programmes, are often tested using random instances created by a Saidman generator. We devise a new matheuristic that can optimally solve a benchmark set … Read more

    Sparse Approximations with Interior Point Methods

  • Valentina De Simone
  • Daniela di Serafino
  • Jacek Gondzio
  • Spyridon Pougkakiotis
  • Marco Viola
    • Categories Applications - Science and Engineering, Convex and Nonsmooth Optimization, Nonlinear Optimization Tags , , , , , , ,

    Large-scale optimization problems that seek sparse solutions have become ubiquitous. They are routinely solved with various specialized first-order methods. Although such methods are often fast, they usually struggle with not-so-well conditioned problems. In this paper, specialized variants of an interior point-proximal method of multipliers are proposed and analyzed for problems of this class. Computational experience … Read more

    ADMM and inexact ALM: the QP case

  • Stefano Cipolla
  • Jacek Gondzio
    • Categories Quadratic Programming Tags , ,

    Embedding randomization procedures in the Alternating Direction Method of Multipliers (ADMM) has recently attracted an increasing amount of interest as a remedy to the fact that the direct n-block generalization of ADMM is not necessarily convergent ($n \geq 3$). Even if, in practice, the introduction of such techniques could mitigate the diverging behaviour of the … Read more

    New algorithms for hierarchical optimisation in kidney exchange programmes

  • Maxence Delorme
  • Jacek Gondzio
  • William Pettersson
  • Sergio García
  • Joerg Kalcsics
  • David Manlove
    • Categories Applications - OR and Management Sciences, Combinatorial Optimization, Integer Programming Tags , , , ,

    Kidney exchange programmes (KEPs) across the world help match donors and recipients to identify kidney transplantations. Almost all KEPs use a hierarchical set of objectives to determine an optimal set of transplants to perform, and integer linear programming is often used to find such optimal matchings. In this work, we identify the barriers in existing … Read more

    Stability in the the Hospitals / Residents problem with Couples and Ties: Mathematical models and computational studies

  • Maxence Delorme
  • Jacek Gondzio
  • William Pettersson
  • Sergio García
  • Joerg Kalcsics
  • David Manlove
    • Categories Applications - OR and Management Sciences, Combinatorial Optimization, Integer Programming Tags , , ,

    In the well-known Hospitals/Residents problem (HR), the objective is to find a stable matching of doctors (or residents) to hospitals based on their preference lists. In this paper, we study HRCT, the extension of HR in which doctors are allowed to apply in couples, and in which doctors and hospitals can include ties in their … Read more

    Improving solve times of stable matching problems through preprocessing

  • Maxence Delorme
  • Jacek Gondzio
  • William Pettersson
  • Sergio García
  • Joerg Kalcsics
  • David Manlove
    • Categories Combinatorial Optimization, Integer Programming, Optimization Software Benchmark Tags , , ,

    We present new theory, heuristics and algorithms for preprocessing instances of the Stable Marriage with Ties and Incomplete lists (SMTI), the Hospitals/Residents with Ties (HRT), and the Worker-Firms with Ties (WFT) problems. We show that instances of these problems can be preprocessed by removing from the preference lists of some agents entries that correspond to … Read more

    A New Preconditioning Approach for an Interior Point-Proximal Method of Multipliers for Linear and Convex Quadratic Programming

  • Luca Bergamaschi
  • Jacek Gondzio
  • John W. Pearson
  • Ángeles Martínez
  • Spyridon Pougkakiotis
    • Categories Convex Optimization, Linear Programming, Quadratic Programming Tags , , , ,

    In this paper, we address the efficient numerical solution of linear and quadratic programming problems, often of large scale. With this aim, we devise an infeasible interior point method, blended with the proximal method of multipliers, which in turn results in a primal-dual regularized interior point method. Application of this method gives rise to a … Read more