Year: 2012

A Douglas-Rachford type primal-dual method for solving inclusions with mixtures of composite and parallel-sum type monotone operators

  • Radu Ioan Bot
  • Christopher Hendrich
    • Categories Convex Optimization Tags , , ,

    In this paper we propose two different primal-dual splitting algorithms for solving inclusions involving mixtures of composite and parallel-sum type monotone operators which rely on an inexact Douglas-Rachford splitting method, however applied in different underlying Hilbert spaces. Most importantly, the algorithms allow to process the bounded linear operators and the set-valued operators occurring in the … Read more

    Solving the integrated airline recovery problem using column-and-row generation

  • Stephen J. Maher
    • Categories (Mixed) Integer Linear Programming, Airline Optimization Tags , ,

    Airline recovery presents very large and difficult problems requiring high quality solutions within very short time limits. To improve computational performance, the complete airline recovery problem is generally formulated as a series of sequential stages. While the sequential approach greatly simplifies the complete recovery problem, there is no guarantee of global optimality or solution quality. … Read more

    MSS: MATLAB software for L-BFGS trust-region subproblems for large-scale optimization

  • Jennifer B. Erway
  • Roummel F. Marcia
    • Categories Nonlinear Optimization Tags , , ,

    A MATLAB implementation of the More’-Sorensen sequential (MSS) method is presented. The MSS method computes the minimizer of a quadratic function defined by a limited-memory BFGS matrix subject to a two-norm trust-region constraint. This solver is an adaptation of the More’-Sorensen direct method into an L-BFGS setting for large-scale optimization. The MSS method makes use … Read more

    On bounding the bandwidth of graphs with symmetry

  • Renata Sotirov
  • Edwin van Dam
    • Categories Semi-definite Programming Tags , , , , ,

    We derive a new lower bound for the bandwidth of a graph that is based on a new lower bound for the minimum cut problem. Our new semide finite programming relaxation of the minimum cut problem is obtained by strengthening the well-known semide nite programming relaxation for the quadratic assignment problem by fixing two vertices in the … Read more

    Mixed-Integer Nonlinear Optimization

  • Pietro Belotti
  • Christian Kirches
  • Sven Leyffer
  • Jeff Linderoth
  • James R. Luedtke
  • Ashutosh Mahajan
    • Categories (Mixed) Integer Nonlinear Programming Tags , , ,

    Many optimal decision problems in scientific, engineering, and public sector applications involve both discrete decisions and nonlinear system dynamics that affect the quality of the final design or plan. These decision problems lead to mixed-integer nonlinear programming (MINLP) problems that combine the combinatorial difficulty of optimizing over discrete variable sets with the challenges of handling … Read more

    A Primal-Dual Regularized Interior-Point Method for Semidefinite Programming

  • Ahad Dehghani
  • Jean-Louis Goffin
  • Dominique Orban
    • Categories Semi-definite Programming Tags , , , , ,

    Interior-point methods in semidefinite programming (SDP) require the solution of a sequence of linear systems which are used to derive the search directions. Safeguards are typically required in order to handle rank-deficient Jacobians and free variables. We generalize the primal-dual regularization of \cite{friedlander-orban-2012} to SDP and show that it is possible to recover an optimal … Read more

    Validation of Nominations in Gas Network Optimization: Models, Methods, and Solutions

  • Armin Fügenschuh
  • Björn Geißler
  • Thorsten Koch
  • Antonio Morsi
  • Marc E. Pfetsch
  • Jessica Rövekamp
  • Lars Schewe
  • Martin Schmidt
  • Nina Geissler
  • Ralf Gollmer
  • Benjamin Hiller
  • Jesco Humpola
  • Thomas Lehmann
  • Alexander Martin
  • Ruediger Schultz
  • Robert Schwarz
  • Jonas Schweiger
  • Claudia Stangl
  • Marc C. Steinbach
  • Stefan Vigerske
  • Bernhard M. Willert
    • Categories (Mixed) Integer Nonlinear Programming, Applications - Science and Engineering, Systems governed by Differential Equations Optimization Tags , ,

    In this article we investigate methods to solve a fundamental task in gas transportation, namely the validation of nomination problem: Given a gas transmission network consisting of passive pipelines and active, controllable elements and given an amount of gas at every entry and exit point of the network, find operational settings for all active elements … Read more

    A symmetric reduction of the NT direction

  • Chantal Hergenroeder
  • Florian Jarre
    • Categories Semi-definite Programming

    A stable symmetrization of the linear systems arising in interior-point methods for solving linear programs is introduced. A comparison of the condition numbers of the resulting interior-point linear systems with other commonly used approaches indicates that the new approach may be best suitable for an iterative solution. It is shown that there is a natural … Read more

    Robustness Analysis of HottTopixx, a Linear Programming Model for Factoring Nonnegative Matrices

  • Nicolas Gillis
    • Categories Data-Mining, Linear Programming Tags , , , ,

    Although nonnegative matrix factorization (NMF) is NP-hard in general, it has been shown very recently that it is tractable under the assumption that the input nonnegative data matrix is separable (that is, there exists a cone spanned by a small subset of the columns containing all columns). Since then, several algorithms have been designed to … Read more

    Parallel Implementation of Successive Sparse SDP Relaxations for Large-scale Euclidean Distance Geometry Problems

  • Sunyoung Kim
  • Masakazu Kojima
  • Makoto Yamashita
    • Categories Semi-definite Programming Tags , , ,

    The Euclidean distance geometry problem (EDGP) includes locating sensors in a sensor network and constructing a molecular configuration using given distances in the two or three-dimensional Euclidean space. When the locations of some nodes, called anchors, are given, the problem can be dealt with many existing methods. An anchor-free problem in the three-dimensional space, however, … Read more