Jacek Gondzio


Professor of Optimization

School of Mathematics
University of Edinburgh, Scotland, UK

Publications (1990-present)
Recent Reports (2013-present)


Curriculum Vitae (   May 2017)


Employment

I hold a Master of Engineering degree in Electronics (1983) and a PhD in Automatic Control and Robotics (1989), both from the Department of Electronics, Warsaw University of Technology.

From 1989 till September 1993 I was an Assistant Professor at the Systems Research Institute of the Polish Academy of Sciences, Warsaw, Poland.

From October 1993 till September 1998 I was a Research Fellow in LogiLab at the Department of Management Studies of the University of Geneva, Switzerland.

I have been in Edinburgh since October 1st, 1998: Lecturer (1998-2000), Reader (2000-2005), Professor (2005-present).

Research Interests

My research interests include the theory and implementation of large scale optmization methods. I have been involved in the development of the simplex, simplex-type and interior point methods for linear, quadratic and nonlinear programming, cutting plane methods for convex nondifferentiable optimization and column generation approaches for combinatorial optimization.

Ongoing Research Projects

Elected

Editorships

Referee for:

Software

Completed project


Publications

Papers in refereed journals:

prepared in 1990:
  1. J. Gondzio and A. Ruszczynski, A sensitivity method for basis inverse representation in multistage stochastic linear programming problems, Journal of Optimization Theory and Applications 74 (1992), 221-242.
  2. J. Gondzio, Stable algorithm for updating dense LU factorization after row or column exchange and row and column addition or deletion, Optimization 23 (1992) 7-26.
  3. J. Gondzio, On exploiting original problem data in the inverse representation of linear programming bases, ORSA Journal on Computing 6 (1994) No 2, 193-206.
prepared in 1991:
  1. J. Gondzio, Splitting dense columns of constraint matrix in interior point methods for large scale linear programming, Optimization 24 (1992), 285-297.
  2. J. Gondzio, Implementing Cholesky factorization for interior point methods of linear programming, Optimization 27 (1993) 121-140.
  3. J. Gondzio and D. Tachat, The design and application of IPMLO - a FORTRAN library for linear optimization with interior point methods, RAIRO Recherche Operationnelle 28 (1994) No 1, 37-56.
prepared in 1992:
  1. A. Altman and J. Gondzio, An efficient implementation of a higher order primal-dual interior point method for large sparse linear programs, Archives of Control Sciences 2 (1992) No 1/2, 23-40.
  2. A. Altman and J. Gondzio, HOPDM - A higher order primal-dual method for large scale linear programming. European Journal of Operational Research 66 (1993) 159-161.
  3. J. Gondzio and M. Makowski, Solving a class of LP problems with a primal-dual logarithmic barrier method, European Journal of Operational Research 80 (1995) 184-192.
prepared in 1993:
  1. J. Gondzio, Another simplex-type method for large scale linear programming, Control and Cybernetics 25 (1996) No 4, 739-760.
prepared in 1994:
  1. J. Gondzio, Presolve analysis of linear programs prior to applying an interior point method, INFORMS Journal on Computing 9, No 1, Winter 1997, 73-91.
  2. J.-L. Goffin, J.Gondzio, R. Sarkissian and J.-P. Vial, Solving nonlinear multicommodity flow problems by the analytic center cutting plane method, Mathematical Programming 76 (1996) No 1, 131-154.
  3. J. Gondzio, Multiple centrality corrections in a primal dual method for linear programming, Computational Optimization and Applications 6 (1996) 137-156.
prepared in 1995:
  1. J. Gondzio, HOPDM (version 2.12) - A Fast LP Solver Based on a Primal-Dual Interior Point Method, European Journal of Operational Research 85 (1995) 221-225.
  2. J. Gondzio, R. Sarkissian and J.-P. Vial, Using an Interior Point Method for the Master Problem in a Decomposition Approach, European Journal of Operational Research 101 (1997) 577-587.
  3. J. Gondzio, O. du Merle, R. Sarkissian and J.-P. Vial, ACCPM - A Library for Convex Optimization Based on an Analytic Center Cutting Plane Method, European Journal of Operational Research 94 (1996) 206-211.
prepared in 1996:
  1. J. Gondzio, Warm Start of the Primal-Dual Method Applied in the Cutting Plane Scheme, Mathematical Programming 83 (1998) No 1, 125-143.
prepared in 1997:
  1. J. Gondzio and J.-P. Vial, Warm Start and Epsilon-subgradients in the Cutting Plane Scheme for Block-angular Linear Programs, Computational Optimization and Applications 14 (1999) 17-36.
  2. E. Fragniere, J. Gondzio R. Sarkissian and J.-P. Vial, Structure Exploiting Tool in Algebraic Modeling Languages, Management Science 46 (2000) 1145-1158.
prepared in 1998:
  1. A. Altman and J. Gondzio, Regularized Symmetric Indefinite Systems in Interior Point Methods for Linear and Quadratic Optimization, Optimization Methods and Software 11-12 (1999) No 1-4, 275-302.
  2. J. Gondzio, R. Sarkissian and J.-P. Vial, Parallel Implementation of a Central Decomposition Method for Solving Large Scale Planning Problems, Computational Optimization and Applications 19 (2001) No 1, 5-29.
  3. E. Fragniere, J. Gondzio and J.-P. Vial, Building and Solving Large-scale Stochastic Programs on an Affordable Distributed Computing System, Annals of Operations Research 99 (2000) No 1-4, 167-187.
  4. E. Fragniere, J. Gondzio and R. Sarkissian, Efficient Management of Multiple Sets to Extract Complex Structures from Mathematical Programs, Annals of Operations Research 104 (2001) No 1-4, 67-87.
prepared in 1999:
  1. J. Gondzio and R. Kouwenberg, High Performance Computing for Asset Liability Management, Operations Research 49 (2001) No 6, 879-891.
prepared in 2000:
  1. J. Gondzio, R. Kouwenberg and T. Vorst, Hedging options under transaction costs and stochastic volatility, Journal of Economic Dynamics and Control 27 (2003) No 6, 1045-1068.
  2. J. Gondzio and R. Sarkissian, Parallel interior point solver for structured linear programs, Mathematical Programming 96 (2003) No 3, 561-584.
prepared in 2001:
  1. J. Gondzio and A. Grothey, Reoptimization with the primal-dual interior point method, SIAM Journal on Optimization 13 (2003) No 3, pp. 842-864.
prepared in 2002:
  1. L. Bergamaschi, J. Gondzio and G. Zilli, Preconditioning Indefinite Systems in Interior Point Methods for Optimization, Computational Optimization and Applications 28 (2004) No 2, pp. 149-171.
    Received the 2004 COAP Best Paper Award.
prepared in 2003:
  1. V. Ejov, J. Filar and J. Gondzio, An Interior Point Heuristic for the Hamiltonian Cycle Problem via Markov Decision Processes, Journal of Global Optimization 29 (2004) No 3, pp. 315-334.
  2. J. Gondzio and A. Grothey, Parallel Interior Point Solver for Structured Quadratic Programs: Application to Financial Planning Problems, Annals of Operations Research 152 (2007) No 1, pp. 319-339.
prepared in 2004:
  1. J. Gondzio and A. Grothey, Solving Nonlinear Portfolio Optimization Problems with the Primal-Dual Interior Point Method, European Journal of Operational Research 181 (2007) No 3, pp. 1019-1029.
  2. F.P. Ganneau, F.J. Ulm, J. Gondzio and E.J. Garboczi, An algorithm for computing the compressive strength of heterogeneous cohesive-frictional materials - Application to cement paste, Computers and Geotechnics 34 (2007) No 4, pp. 254-266.
  3. J. Gondzio and A. Grothey, Exploiting Structure in Parallel Implementation of Interior Point Methods for Optimization, Computational Management Science 6 (2009) pp. 135–160.
prepared in 2005:
  1. L. Bergamaschi, J. Gondzio, M. Venturin and G. Zilli, Inexact Constraint Preconditioners for Linear Systems Arising in Interior Point Methods, Computational Optimization and Applications 36 (2007) No 2-3, pp. 137-147.
    See the Erratum (9 June 2008) COAP 49 (2011) pp. 401-406.
  2. M. Colombo and J. Gondzio, Further Development of Multiple Centrality Correctors for Interior Point Methods, Computational Optimization and Applications 41 (2008) No 3, pp. 277-305.
prepared in 2006:
  1. G. Al-Jeiroudi, J. Gondzio and J.A.J. Hall, Preconditioning Indefinite Systems in Interior Point Methods for Large Scale Linear Optimization, Optimization Methods and Software 23 (2008) No 3, pp. 345-363.
  2. J. Gondzio and A. Grothey, A New Unblocking Technique to Warmstart Interior Point Methods based on Sensitivity Analysis, SIAM Journal on Optimization 19 (2008) No 3, pp. 1184-1210.
  3. M. Colombo, J. Gondzio and A. Grothey, A Warm-Start Approach for Large-Scale Stochastic Linear Programs, Mathematical Programming 127 (2011) 371-397.
prepared in 2007:
  1. G. Al-Jeiroudi and J. Gondzio, Convergence Analysis of Inexact Infeasible Interior Point Method for Linear Optimization, Journal of Optimization Theory and Applications. 141 (2009) pp. 231-247.
  2. S. Bellavia, J. Gondzio and B. Morini, Regularization and Preconditioning of KKT Systems Arising in Nonnegative Least-Squares Problems, Numerical Linear Algebra with Applications 16 (2009) pp. 39-61.
  3. A. Pages, J. Gondzio and N. Nabona, Warmstarting for Interior Point Methods Applied to the Long-Term Power Planning Problem, European Journal on Operational Research 197 (2009) pp. 112-125.
  4. J. Goncalves, R.H. Storer and J. Gondzio, A Family of Linear Programming Algorithms Based on an Algorithm by von Neumann, Optimization Methods and Software 24 (2009) pp. 461–478.
  5. E. Fragniere, J. Gondzio and X. Yang, Operations Risk Management by Optimally Planning the Qualified Workforce Capacity, European Journal on Operational Research 202 (2010) pp. 518-527.
  6. K. Woodsend and J. Gondzio, Exploiting Separability in Large Scale Linear Support Vector Machine Training, Computational Optimization and Applications 49 (2011) 241–269.
prepared in 2008:
  1. H. Du, P.-J. Chung, J. Gondzio and B. Mulgrew, Robust Transmit Beamforming Based on Probabilistic Constraint, Technical Report ERGO-08-002, School of Mathematics, The University of Edinburgh, January 24, 2008, revised May 31, 2008. (abstract and PDF). Presented at: EUSIPCO-2008. August 25-29, 2008, Lausanne, Switzerland.
  2. P.-J. Chung, H. Du and J. Gondzio, A Probabilistic Constraint Approach for Robust Transmit Beamforming with Imperfect Channel Information, Technical Report ERGO-08-003, School of Mathematics, The University of Edinburgh, September 29, 2008. (abstract and PDF). Presented at: EUSIPCO-2009. August 24--28, 2009, Glasgow, UK.
prepared in 2009:
  1. K. Woodsend and J. Gondzio, Hybrid MPI/OpenMP Parallel Linear Support Vector Machine Training, Journal of Machine Learning Research 20 (2009) pp 1937-1953.
  2. M. Colombo, A. Grothey, J. Hogg, K. Woodsend and J. Gondzio, A Structure-conveying Modelling Language for Mathematical and Stochastic Programming, Mathematical Programming Computation 1 (2009) pp 223–247.
  3. X. Yang, J. Gondzio and A. Grothey, Asset-Liability Management Modelling with Risk Control by Stochastic Dominance, Journal of Asset Management 11 (2010) pp 73-93.
  4. S. Bellavia, J. Gondzio and B. Morini, Computational Experience with Numerical Methods for Nonnegative Least-Squares Problems, Numerical Linear Algebra with Applications 18 (2011) pp. 363-385.
  5. J. Gondzio, Matrix-Free Interior Point Method, Computational Optimization and Applications 51 (2012) pp. 457-480. Published online October 14, 2010: DOI 10.1007/s10589-010-9361-3.
prepared in 2010:
  1. E. Fragniere, J. Gondzio, N. S. Tuchschmid and Qun Zhang, Non-parametric Liquidity Adjusted VaR Model: A Stochastic Programming Approach, Journal of Financial Transformation 28 (2010) pp 111-118. Final PDF.
  2. P.-J. Chung, H. Du and J. Gondzio, A Probabilistic Constraint Approach for Robust Transmit Beamforming with Imperfect Channel Information, IEEE Transactions on Signal Processing 59 (2011) No 6, 2773-2782.
prepared in 2011:
  1. J. Gondzio, Interior point methods 25 years later, European Journal of Operational Research 218 (2012) pp. 587-601. Published online: October 8, 2011. DOI 10.1016/j.ejor.2011.09.017.
  2. J. Gondzio, P. González-Brevis, P. Munari, New Developments in the Primal-Dual Column Generation Technique, European Journal of Operational Research 224 (2013) 41-51. Published online: July 31, 2012. DOI 10.1016/j.ejor.2012.07.024.
  3. S. Bellavia, J. Gondzio and B. Morini, A Matrix-Free Preconditioner for Sparse Symmetric Positive Definite Systems and Least-Squares Problems, SIAM Journal on Scientific Computing 35 (2013) No 1, pp. A192-A211.
prepared in 2012:
  1. P. Munari and J. Gondzio, Using the Primal-Dual Interior Point Algorithm within the Branch-Price-and-Cut Method, Computers and Operations Research 40 (2013) No 8, pp. 2026–2036.
  2. J. Gondzio, Convergence Analysis of an Inexact Feasible Interior Point Method for Convex Quadratic Programming, SIAM Journal on Optimization 23 (2013) No 3, pp. 1510-1527.
  3. K. Fountoulakis, J. Gondzio and P. Zhlobich, Matrix-free Interior Point Method for Compressed Sensing Problems, Mathematical Programming Computation 6 (2014), pp. 1-31. Published online Dec 6, 2013.
  4. J. Gondzio, J. Gruca, J.A.J. Hall, W. Laskowski and M. Zukowski, Solving Large-Scale Optimization Problems Related to Bell’s Theorem, Journal of Computational and Applied Mathematics 263C (2014), pp. 392-404. Published online Jan 11, 2014.
prepared in 2013:
  1. J. Gondzio and P. González-Brevis, A New Warmstarting Strategy for the Primal-Dual Column Generation Method, Mathematical Programming A 152 (2015) 113--146. Published online May 22, 2014.
  2. J. Gondzio, P. González-Brevis and P. Munari, Large-scale Optimization with the Primal-Dual Column Generation Method. Mathematical Programming Computation 8 (2016) 47--82. Published online September 3, 2015.
    See also its last version as a Technical Report ERGO-13-014: (abstract, PDF).
  3. R. Tappenden, P. Richtarik and J. Gondzio, Inexact Coordinate Descent: Complexity and Preconditioning, Journal of Optimization Theory and Applications (to appear). Published online: February 29, 2016.
    See also the Technical Report ERGO-13-007 version. (abstract, PDF).
prepared in 2014:
  1. K. Fountoulakis and J. Gondzio, A Second-Order Method for Strongly Convex L1-Regularization Problems, Mathematical Programming A 156 (2016) 189-219. Published online 01 March 2015.
  2. I. Dassios, K. Fountoulakis and J. Gondzio, A Preconditioner for a Primal-dual Newton Conjugate Gradients Method for Compressed Sensing Problems, SIAM Journal on Scientific Computing 37 (2015) A2783--A2812.
prepared in 2015:
  1. K. Fountoulakis and J. Gondzio, Performance of First- and Second-Order Methods for L1-regularized Least Squares Problems, Computational Optimization and Applications 65 (2016) 605--635.
    See also its last version as a Technical Report ERGO-15-005: (abstract, PDF) March 30, 2015.
    Reports on the solution of the optimization problem with 1 trillion (1012) variables.

  2. J. Gondzio, Crash Start of Interior Point Methods, European Journal of Operational Research 255 (2016) 308--314.
    See also its last version as a Technical Report ERGO-15-012: (abstract, PDF) October 5, 2015.
prepared in 2016:
  1. J.W. Pearson and J. Gondzio, Fast Interior Point Solution of Quadratic Programming Problems Arising from PDE-Constrained Optimization, accepted for publication in Numerische Mathematik.
    See also its last version as a Technical Report ERGO-15-013: School of Mathematics, The University of Edinburgh. (abstract, PDF).

Other publications:

  1. J. Gondzio and T. Terlaky, A Computational View of Interior Point Methods for Linear Programming, in: Advances in Linear and Integer Programming, J. Beasley (ed.), Chapter 3, pp 103-144, Oxford University Press, Oxford, England 1996. See the book.

  2. E.D. Andersen, J. Gondzio, C. Meszaros, and X. Xu, Implementation of Interior Point Methods for Large Scale Linear Programming, in: Interior Point Methods in Mathematical Programming, T. Terlaky (ed.), Chapter 6, pp. 189-252, Kluwer Academic Publisher, 1996. See the book and an old version of the TR 1996.3 (PS file).

  3. E. Fragniere, J. Gondzio and R. Sarkissian, Customized Block Structures in Algebraic Modeling Languages: The Stochastic Programming Case, Proceedings of the IFAC Symposium on Computation in Economics, Finance and Engineering: Economics Systems, CEFES/IFAC98, Sean Holly (ed.), pp. 141-144, Springer Verlag, Berlin, 2000. TR (PS file, 4MB).

  4. J.A. Filar, J. Gondzio, A. Haurie A, et al., Decomposition and Parallel Processing Techniques for Two-time Scale Controlled Markov Chains, Proceedings of the 39th IEEE Conference on Decision and Control, Vols 1-5, pp. 711-716, 2000.

  5. E. Fragniere and J. Gondzio, Optimization Modeling Languages, in: P. Pardalos and M. Resende (eds.), Handbook of Applied Optimization, Oxford University Press, June 2002, pp. 993-1007. See the book and an old version of the TR (PDF file).

  6. E. Fragniere and J. Gondzio, Stochastic Programming from Modeling Languages, in: S. Wallace and W. Ziemba (eds.) Applications of Stochastic Programming, SIAM Series on Optimization, 2005, Chapter 7, pp. 95-113. See the book and an old version of the TR (PDF file).

  7. J. Gondzio and A. Grothey, Direct Solution of Linear Systems of Size 109 Arising in Optimization with Interior Point Methods, R. Wyrzykowski, J. Dongarra, N. Meyer and J. Wasniewski (eds.), Parallel Processing and Applied Mathematics PPAM 2005, Lecture Notes in Computer Science, 3911, Springer-Verlag, Berlin, 2006, pp 513-525. TR (PDF file).
    Reports on the solution of the optimization problem with 1 billion (109) variables.

  8. J. Gondzio and A. Grothey, Solving Nonlinear Financial Planning Problems with 109 Decision Variables on Massively Parallel Architectures, M. Costantino, C.A. Brebbia (eds.), Computational Finance and its Applications II, WIT Transactions on Modelling and Simulation, 43, WIT Press, 2006. (abstract, PDF).

  9. K. Woodsend and J. Gondzio, High-Performance Parallel Support Vector Machine Training, R. Ciegis, D. Henty, B. Kagstrom, J. Zilinskas (eds.), Parallel scientific computing and optimization: advances and applications. Springer optimization and its applications, vol 27, Springer, Berlin, 2009, pp 83–92.

  10. A. Grothey, J. Hogg, K. Woodsend, M. Colombo and J. Gondzio, A structure-conveying parallelisable modelling language for mathematical programming, R. Ciegis, D. Henty, B. Kagstrom, J. Zilinskas (eds.), Parallel scientific computing and optimization: advances and applications. Springer optimization and its applications, vol 27, Springer, Berlin, 2009, pp 147–158.

  11. J. Gondzio, Interior point methods in machine learning, Optimization for Machine Learning, S. Sra, S. Nowozin and S. Wright (eds), MIT Press, 2010. (abstract, PDF).

  12. E. Smith, J. Gondzio and J.A.J. Hall, GPU acceleration of the matrix-free interior point method, R. Wyrzykowski, J. Dongarra, K. Karczewski and J. Wasniewski (eds.), Parallel Processing and Applied Mathematics PPAM 2011, Part I, Lecture Notes in Computer Science, 7203, Springer-Verlag, Berlin, 2012, pp 681-689.

Selected technical reports:

  1. J. Gondzio, Applying Schur Complements for Handling General Updates of a Large, Sparse, Unsymmetric Matrix, Technical Report ZTSW-2-G244/93 Systems Research Institute, Polish Academy of Sciences, Warsaw, Poland, September 1993, revised in April 1995. (PDF file).
  2. J. Gondzio, Preconditioned Conjugate Gradients in an Interior Point Method for Two-stage Stochastic Programming, Working Paper WP-94-130, International Institute for Applied Systems Analysis, Laxenburg, Austria, 1994. (PDF file).
  3. J. Gondzio and M. Makowski, HOPDM - Modular Solver for LP Problems, User's Guide to Version 2.12, Working Paper WP-95-50, International Institute for Applied Systems Analysis, Laxenburg, Austria, 1995. (PS file).
  4. J. Gondzio and O. du Merle, Analytic Center Cutting Plane Method - User's Guide for the Library, Technical Report 1995.33, Department of Management Studies, University of Geneva, Switzerland, December 1995.
  5. J. Gondzio and R. Sarkissian, Column Generation with a Primal-Dual Method, Logilab Technical Report 96.6, Department of Management Studies, University of Geneva, Switzerland, June 1996. (abstract, PDF).
  6. E. Fragniere, J. Gondzio and J.-P. Vial, A Planning Model with one Million Scenarios Solved on an Affordable Parallel Machine, Logilab Technical Report 98.11, Department of Management Studies, University of Geneva, Switzerland, June, 1998. (PDF file).
  7. A. Lisser, A. Ouorou, J.-Ph. Vial and J. Gondzio, Capacity planning under uncertain demand in telecommunication networks, Logilab Technical Report 99.13, Department of Management Studies, University of Geneva, Switzerland, October 1999.
  8. O. Epelly, J. Gondzio and J.-P. Vial, An Interior Point Solver for Smooth Convex Optimization with an Application to Environmental-Energy-Economic Models, Logilab Technical Report 2000.8, Department of Management Studies, University of Geneva, Switzerland, July 2000. (abstract, PDF).
  9. J. Gondzio and A. Grothey, Solving Distribution Planning Problems with the Interior Point Method, Technical Report MS-06-001, School of Mathematics, The University of Edinburgh, February 18, 2006, revised May 25, 2006. (abstract, PDF).
  10. K. Woodsend and J. Gondzio, Parallel Support Vector Machine Training with Nonlinear Kernels, Technical Report MS-07-007, School of Mathematics, The University of Edinburgh, November ?, 2007 (in preparation). (abstract, PDF).
  11. J. Gondzio and P. Zhlobich, Multilevel Quasiseparable Matrices in PDE-constrained Optimization, Technical Report ERGO-11-021, School of Mathematics, The University of Edinburgh, December 28, 2011. (abstract, PDF).
  12. I. Dassios, K. Fountoulakis and J. Gondzio, A Second-Order Method for Compressed Sensing Problems with Coherent and Redundant Dictionaries Technical Report ERGO-14-007, School of Mathematics, The University of Edinburgh, May 16, 2014. (abstract, PDF).
  13. R. Gower and J. Gondzio, Action Constrained Quasi-Newton Methods, Technical Report ERGO-14-020, School of Mathematics, The University of Edinburgh, December 27, 2014. (abstract, PDF).

Most recent reports submitted for publication:

  1. S. Bellavia, J. Gondzio and M. Porcelli, An Inexact Dual Logarithmic Barrier Method for Solving Sparse Semidefinite Programs, Technical Report ERGO-2016-004, School of Mathematics, The University of Edinburgh, July 29, 2016, revised March 31, 2017. (abstract, PDF).