Tamás Terlaky

Efficient Use of Quantum Linear System Algorithms in Interior Point Methods for Linear Optimization

  • Mohammadhossein Mohammadisiahroudi
  • Ramin Fakhimi
  • Tamás Terlaky
    • Categories Linear Programming Tags , , ,

    Quantum computing has attracted significant interest in the optimization community because it potentially can solve classes of optimization problems faster than conventional supercomputers. Several researchers proposed quantum computing methods, especially Quantum Interior Point Methods (QIPMs), to solve convex optimization problems, such as Linear Optimization, Semidefinite Optimization, and Second-order Cone Optimization problems. Most of them have … Read more

    The first heuristic specifically for mixed-integer second-order cone optimization

  • Sertalp B. Çay
  • Imre Pólik
  • Tamás Terlaky
    • Categories Branch and Cut Algorithms, Integer Programming, Second-Order Cone Programming Tags , ,

    Mixed-integer second-order cone optimization (MISOCO) has become very popular in the last decade. Various aspects of solving these problems in Branch and Conic Cut (BCC) algorithms have been studied in the literature. This study aims to fill a gap and provide a novel way to find feasible solutions early in the BCC algorithm. Such solutions … Read more

    On Pathological Disjunctions and Redundant Disjunctive Conic Cuts

  • Julio C. Góez
  • Tamás Terlaky
  • Mohammad Shahabsafa
    • Categories Integer Programming, Second-Order Cone Programming Tags , ,

    The development of Disjunctive Conic Cuts (DCCs) for Mixed Integer Second Order Cone Optimization (MISOCO) problems has recently gained significant interest in the optimization community. In this paper, we explore the pathological disjunctions where disjunctive cuts do not tighten the description of the feasible set. We focus on the identification of cases when the generated … Read more

    The Inmate Assignment and Scheduling Problem and its Application in the PA Department of Correction

  • Kristofer B. Bucklen
  • Naga Venkata Chaitanya Gudapati
  • Tamás Terlaky
  • Louis J. Plebani
  • Mohammad Shahabsafa
  • Anshul Sharma
  • George R. Wilson
    • Categories (Mixed) Integer Linear Programming, Applications - OR and Management Sciences, Applications - Science and Engineering Tags , ,

    The inmate assignment project, in close collaboration with the Pennsylvania Department of Corrections (PADoC), took five years from start to successful implementation. In this project, we developed the Inmate Assignment Decision Support System (IADSS), where the primary goal is simultaneous and system-wide optimal assignment of inmates to correctional institutions (CIs). We develop a novel hier- … Read more

    Quadratic convergence to the optimal solution of second-order conic optimization without strict complementarity

  • Ali Mohammad-Nezhad
  • Tamás Terlaky
    • Categories Second-Order Cone Programming

    Under primal and dual nondegeneracy conditions, we establish the quadratic convergence of Newton’s method to the unique optimal solution of second-order conic optimization. Only very few approaches have been proposed to remedy the failure of strict complementarity, mostly based on nonsmooth analysis of the optimality conditions. Our local convergence result depends on the optimal partition … Read more

    A rounding procedure for semidefinite optimization

  • Ali Mohammad-Nezhad
  • Tamás Terlaky
    • Categories Semi-definite Programming Tags , , ,

    Recently, Mohammad-Nezhad and Terlaky studied the identification of the optimal partition for semidefinite optimization. An approximation of the optimal partition was obtained from a bounded sequence of solutions on, or in a neighborhood of the central path. Here, we use the approximation of the optimal partition in a rounding procedure to generate an approximate maximally … Read more

    Warm-start of interior point methods for second order cone optimization via rounding over optimal Jordan frames

  • Sertalp B. Çay
  • Imre Pólik
  • Tamás Terlaky
    • Categories Branch and Cut Algorithms, Second-Order Cone Programming Tags , , , ,

    Interior point methods (IPM) are the most popular approaches to solve Second Order Cone Optimization (SOCO) problems, due to their theoretical polynomial complexity and practical performance. In this paper, we present a warm-start method for primal-dual IPMs to reduce the number of IPM steps needed to solve SOCO problems that appear in a Branch and … Read more

    A Complete Characterization of Disjunctive Conic Cuts for Mixed Integer Second Order Cone Optimization

  • Pietro Belotti
  • Julio C. Góez
  • Imre Pólik
  • Ted K. Ralphs
  • Tamás Terlaky
    • Categories (Mixed) Integer Nonlinear Programming, Second-Order Cone Programming Tags , ,

    We study the convex hull of the intersection of a disjunctive set defined by parallel hyperplanes and the feasible set of a mixed integer second order cone optimization problem. We extend our prior work on disjunctive conic cuts, which has thus far been restricted to the case in which the intersection of the hyperplanes and … Read more

    On the identification of optimal partition for semidefinite optimization

  • Ali Mohammad-Nezhad
  • Tamás Terlaky
    • Categories Convex Optimization, Linear, Cone and Semidefinite Programming, Semi-definite Programming

    The concept of the optimal partition was originally introduced for linear optimization and linear complementarity problems and subsequently extended to semidefinite optimization. For linear optimization and sufficient linear complementarity problems, from a central solution sufficiently close to the optimal set, the optimal partition and a maximally complementary optimal solution can be identified in strongly polynomial … Read more

    Steplength thresholds for invariance preserving of discretization methods of dynamical systems on a polyhedron

  • Zoltán Horváth
  • Tamás Terlaky
  • Yunfei Song
    • Categories Convex and Nonsmooth Optimization, Convex Optimization Tags , , , ,

    Steplength thresholds for invariance preserving of three types of discretization methods on a polyhedron are considered. For Taylor approximation type discretization methods we prove that a valid steplength threshold can be obtained by finding the first positive zeros of a finite number of polynomial functions. Further, a simple and efficient algorithm is proposed to numerically … Read more