Linear, Cone and Semidefinite Programming

Compact Disjunctive Approximations to Nonconvex Quadratically Constrained Programs

  • Hongbo Dong
  • Yunqi Luo
    • Categories (Mixed) Integer Nonlinear Programming, Global Optimization Theory, Second-Order Cone Programming

    Decades of advances in mixed-integer linear programming (MILP) and recent development in mixed-integer second-order-cone programming (MISOCP) have translated very mildly to progresses in global solving nonconvex mixed-integer quadratically constrained programs (MIQCP). In this paper we propose a new approach, namely Compact Disjunctive Approximation (CDA), to approximate nonconvex MIQCP to arbitrary precision by convex MIQCPs, which … Read more

    A branch and price algorithm for the resource constrained home health care vehicle routing problem

  • Neda Tanoumand
  • Tonguç Ünlüyurt
    • Categories Integer Programming, Linear Programming Tags , , ,

    We consider the vehicle routing problem with resource constraints motivated by a home health care application. We propose a branch and price algorithm to solve the problem. In our problem, we consider different types of patients that require a nurse or a health aid or both. The patients can be serviced by the appropriate vehicles … Read more

    A survey of semidefinite programming approaches to the generalized problem of moments and their error analysis

  • Etienne de Klerk
  • Monique Laurent
    • Categories Constrained Nonlinear Optimization, Global Optimization, Semi-definite Programming

    The generalized problem of moments is a conic linear optimization problem over the convex cone of positive Borel measures with given support. It has a large variety of applications, including global optimization of polynomials and rational functions, options pricing in finance, constructing quadrature schemes for numerical integration, and distributionally robust optimization. A usual solution approach, … Read more

    Exploiting Partial Correlations in Distributionally Robust Optimization

  • Karthyek Murthy
  • Karthik Natarajan
  • Divya Padmanabhan
    • Categories Polyhedra, Robust Optimization, Semi-definite Programming Tags , , ,

    In this paper, we identify partial correlation information structures that allow for simpler reformulations in evaluating the maximum expected value of mixed integer linear programs with random objective coefficients. To this end, assuming only the knowledge of the mean and the covariance matrix entries restricted to block-diagonal patterns, we develop a reduced semidefinite programming formulation, … Read more

    Exploiting Low-Rank Structure in Semidefinite Programming by Approximate Operator Splitting

  • Joaquim Dias Garcia
  • Mario Souto
  • Alvaro Viega
    • Categories Convex Optimization, Optimization Software and Modeling Systems, Semi-definite Programming Tags , , , , ,

    In contrast with many other convex optimization classes, state-of-the-art semidefinite programming solvers are yet unable to efficiently solve large scale instances. This work aims to reduce this scalability gap by proposing a novel proximal algorithm for solving general semidefinite programming problems. The proposed methodology, based on the primal-dual hybrid gradient method, allows the presence of … Read more

    Non-convex min-max fractional quadratic problems under quadratic constraints: copositive relaxations

  • Paula Alexandra Amaral
  • Immanuel M. Bomze
    • Categories Linear, Cone and Semidefinite Programming, Quadratic Programming Tags , , , ,

    In this paper we address a min-max problem of fractional quadratic (not necessarily convex) over linear functions on a feasible set described by linear and (not necessarily convex) quadratic functions. We propose a conic reformulation on the cone of completely positive matrices. By relaxation, a doubly non negative conic formulation is used to provide lower … Read more

    Tight-and-cheap conic relaxation for the optimal reactive power dispatch problem

  • Miguel F. Anjos
  • Christian Bingane
  • Sébastien Le Digabel
    • Categories Linear, Cone and Semidefinite Programming Tags , , , ,

    The optimal reactive power dispatch (ORPD) problem is an alternating current optimal power flow (ACOPF) problem where discrete control devices for regulating the reactive power, such as shunt elements and tap changers, are considered. The ORPD problem is modelled as a mixed-integer nonlinear optimization problem and its complexity is increased compared to the ACOPF problem, … Read more

    An oracle-based projection and rescaling algorithm for linear semi-infinite feasibility problems and its application to SDP and SOCP

  • Tomonari Kitahara
  • Bruno F. Lourenço
  • Masakazu Muramatsu
  • Takashi Tsuchiya
  • Takayuki Okuno
    • Categories Linear, Cone and Semidefinite Programming, Semi-infinite Programming Tags , , ,

    We point out that Chubanov’s oracle-based algorithm for linear programming [5] can be applied almost as it is to linear semi-infinite programming (LSIP). In this note, we describe the details and prove the polynomial complexity of the algorithm based on the real computation model proposed by Blum, Shub and Smale (the BSS model) which is … Read more

    Implementation of an Interior Point Method with Basis Preconditioning

  • Jacek Gondzio
  • Lukas Schork
    • Categories Linear Programming Tags , , ,

    The implementation of a linear programming interior point solver is described that is based on iterative linear algebra. The linear systems are preconditioned by a basis matrix, which is updated from one interior point iteration to the next to bound the entries in a certain tableau matrix. The update scheme is based on simplex-type pivot … Read more

    A Branch-and-Cut Algorithm for Solving Mixed-integer Semidefinite Optimization Problems

  • Ken Kobayashi
  • Yuichi Takano
    • Categories (Mixed) Integer Nonlinear Programming, Global Optimization, Semi-definite Programming Tags , , ,

    This paper is concerned with a cutting-plane algorithm for solving mixed-integer semidefinite optimization (MISDO) problems. In this algorithm, the positive semidefinite constraint is relaxed, and the resultant mixed-integer linear optimization problem is repeatedly solved with valid inequalities for the relaxed constraint. We prove convergence properties of the algorithm. Moreover, to speed up the computation, we … Read more