Month: October 2001

USING SEDUMI 1.02, A MATLAB TOOLBOX FOR OPTIMIZATION OVER SYMMETRIC CONES (Updated for Version 1.05)

  • Jos F. Sturm
    • Categories Linear, Cone and Semidefinite Programming, Optimization Software and Modeling Systems Tags , , , , ,

    SeDuMi 1.05 is an add-on for MATLAB, which lets you solve optimization problems with linear, quadratic and semidefiniteness constraints. It is possible to have complex valued data and variables in SeDuMi. Moreover, large scale optimization problems are solved efficiently, by exploiting sparsity. This paper describes how to work with this toolbox. CitationOptimization Methods and Software … Read more

    New formulation and resolution method for the p-Center problem

  • Sourour Elloumi
  • Martine Labbé
  • Yves Pochet
    • Categories 0-1 Programming, Combinatorial Optimization, Facility Planning and Design Tags , , ,

    The $p$-Center problem consists in locating $p$ facilities among a set of $M$ possible locations and assigning $N$ clients to them in order to minimize the maximum distance between a client and the facility to which he is allocated. We present a new integer linear programming formulation for this Min-Max problem with a polynomial number … Read more

    A globally convergent filter method for nonlinear programming

  • Clóvis Caesar Gonzaga
  • Elizabeth Wegner Karas
  • Marcia Vanti
    • Categories Constrained Nonlinear Optimization Tags , ,

    In this paper we present a filter algorithm for nonlinear programming and prove its global convergence to stationary points. Each iteration is composed of a restoration phase, which reduces a measure of infeasibility, and an optimality phase, which reduces the objective function in a tangential approximation of the feasible set. These two phases are totally … Read more

    A Cutting Plane Algorithm for Large Scale Semidefinite Relaxations

  • Christoph Helmberg
    • Categories Cutting Plane Approaches, Nonsmooth Optimization, Semi-definite Programming Tags , , , , , ,

    The recent spectral bundle method allows to compute, within reasonable time, approximate dual solutions of large scale semidefinite quadratic 0-1 programming relaxations. We show that it also generates a sequence of primal approximations that converge to a primal optimal solution. Separating with respect to these approximations gives rise to a cutting plane algorithm that converges … Read more

    On Numerical Solution of the Maximum Volume Ellipsoid Problem

  • Liyan Gao
  • Yin Zhang
    • Categories Convex Optimization Tags ,

    In this paper we study practical solution methods for finding the maximum-volume ellipsoid inscribing a given full-dimensional polytope in $\Re^n$ defined by a finite set of linear inequalities. Our goal is to design a general-purpose algorithmic framework that is reliable and efficient in practice. To evaluate the merit of a practical algorithm, we consider two … Read more

    A Mixed Integer Disjunctive Model for Transmission Network Expansion

  • Laura Bahiense
  • Sérgio Granville
  • Gerson C. Oliveira
  • Mario Pereira
    • Categories (Mixed) Integer Linear Programming, Applications - OR and Management Sciences, Network Optimization Tags , ,

    The classical non-linear mixed integer formulation of the transmission network expansion problem cannot guarantee finding the optimal solution due to its non-convex nature. We propose an alternative mixed integer linear disjunctive formulation, which has better conditioning properties than the standard disjunctive model. The mixed integer program is solved by a commercial Branch and Bound code, … Read more

    Object-Oriented Software for Quadratic Programming

  • Michael Gertz
  • Stephen Wright
    • Categories Optimization Software Design Principles, Quadratic Programming Tags , ,

    We describe the object-oriented software package OOQP for solving convex quadratic programming problems (QP). The primal-dual interior point algorithms supplied by OOQP are implemented in a way that is largely independent of the problem structure. Users may exploit problem structure by supplying linear algebra, problem data, and variable classes that are customized to their particular … Read more

    The Steinberg Wiring Problem

  • Kurt M. Anstreicher
  • Nathan Brixius
    • Categories 0-1 Programming, Production and Logistics Tags ,

    In 1961 Leon Steinberg formulated a “backboard wiring” problem that has resisted solution for 40 years. Steinberg’s wiring problem is to determine the locations of 34 computer components on a 4 by 9 grid so as to minimize the total length of the wiring required to interconnect them. The problem is an example of a … Read more

    Unifying optimal partition approach to sensitivity analysis in conic optimization

  • E. Alper Yildirim
    • Categories Linear, Cone and Semidefinite Programming Tags , ,

    We study convex conic optimization problems in which the right-hand side and the cost vectors vary linearly as a function of a scalar parameter. We present a unifying geometric framework that subsumes the concept of the optimal partition in linear programming (LP) and semidefinite programming (SDP) and extends it to conic optimization. Similar to the … Read more

    Semidefinite relaxations for Max-Cut

  • Monique Laurent
    • Categories Combinatorial Optimization, Integer Programming, Linear, Cone and Semidefinite Programming Tags , , ,

    We compare several semidefinite relaxations for the cut polytope obtained by applying the lift and project methods of Lov\’asz and Schrijver and of Lasserre. We show that the tightest relaxation is obtained when aplying the Lasserre construction to the node formulation of the max-cut problem. This relaxation $Q_t(G)$ can be defined as the projection on … Read more