Optimization Software and Modeling Systems

Applying oracles of on-demand accuracy in two-stage stochastic programming – a computational study

  • Csaba I. Fábián
  • Achim Koberstein
  • Leena Suhl
  • Christian Wolf
    • Categories Optimization Software Benchmark, Stochastic Programming Tags , , ,

    Traditionally, two variants of the L-shaped method based on Benders’ decomposition principle are used to solve two-stage stochastic programming problems: the single-cut and the multi-cut version. The concept of an oracle with on-demand accuracy was originally proposed in the context of bundle methods for unconstrained convex optimzation to provide approximate function data and subgradients. In … Read more

    An inexact block-decomposition method for extra large-scale conic semidefinite programming

  • Renato D.C. Monteiro
  • Camilo Ortiz
  • Benar Fux Svaiter
    • Categories Convex and Nonsmooth Optimization, Linear, Cone and Semidefinite Programming, Optimization Software and Modeling Systems Tags , , , , , , ,

    In this paper, we present an inexact block-decomposition (BD) first-order method for solving standard form conic semidefinite programming (SDP) which avoids computations of exact projections onto the manifold defined by the affine constraints and, as a result, is able to handle extra large SDP instances. The method is based on a two-block reformulation of the … Read more

    Memory-Aware Parallelized RLT3 for Solving Quadratic Assignment Problems

  • Monique Guignard
  • Peter M. Hahn
  • Amir Roth
  • Matthew Saltzman
    • Categories (Mixed) Integer Nonlinear Programming, Combinatorial Optimization, Parallel Algorithms Tags , ,

    We present a coarse-grain (outer-loop) parallel implementation of RLT1/2/3 (Level 1, 2, and 3 Reformulation and Linearization Technique—in that order) bound calculations for the QAP within a branch-and-bound procedure. For a search tree node of size S, each RLT3 and RLT2 bound calculation iteration is parallelized S ways, with each of S processors performing O(S5) … Read more

    Modeling with Metaconstraints and Semantic Typing of Variables

  • Andre Augusto Cire
  • John Hooker
  • Tallys H. Yunes
    • Categories Modeling Languages and Systems, Optimization Software Design Principles Tags , , ,

    Recent research in hybrid optimization shows that a combination of technologies that exploits their complementary strengths can significantly speed up computation. The use of high-level metaconstraints in the problem formulation can achieve a substantial share of these computational gains by better communicating problem structure to the solver. During the solution process, however, metaconstraints give rise … Read more

    Fast implementation for semidefinite programs with positive matrix completion

  • Kazuhide Nakata
  • Makoto Yamashita
    • Categories Parallel Algorithms, Semi-definite Programming Tags , , ,

    Solving semidefinite programs (SDP) in a short time is the key to managing various mathematical optimization problems in practical time. The matrix-completion primal-dual interior-point method (MC-PDIPM) extracts a structural sparsity of input SDP by factorizing the variable matrices, and it shrinks the computation time. In this paper, we propose a new factorization based on the … Read more

    PEBBL: An Object-Oriented Framework for Scalable Parallel Branch and Bound

  • Jonathan Eckstein
  • William E. Hart
  • Cynthia A. Phillips
    • Categories Integer Programming, Parallel Algorithms Tags , ,

    PEBBL is a C++ class library implementing the underlying operations needed to support a wide variety of branch-and-bound algorithms in a message-passing parallel computing environment. Deriving application-speci c classes from PEBBL, one may create parallel branch-and-bound applications through a process focused on the unique aspects of the application, while relying on PEBBL for generic aspects of … Read more

    Smooth minimization of nonsmooth functions with parallel coordinate descent methods

  • Olivier Fercoq
  • Peter Richtarik
    • Categories Convex Optimization, Parallel Algorithms Tags , , , ,

    We study the performance of a family of randomized parallel coordinate descent methods for minimizing the sum of a nonsmooth and separable convex functions. The problem class includes as a special case L1-regularized L1 regression and the minimization of the exponential loss (“AdaBoost problem”). We assume the input data defining the loss function is contained … Read more

    Large-scale optimization with the primal-dual column generation method

  • Jacek Gondzio
  • Pedro Munari
  • Pablo Gonzalez-Brevis
    • Categories Convex Optimization, Linear Programming, Optimization Software and Modeling Systems Tags , , , , , ,

    The primal-dual column generation method (PDCGM) is a general-purpose column generation technique that relies on the primal-dual interior point method to solve the restricted master problems. The use of this interior point method variant allows to obtain suboptimal and well-centered dual solutions which naturally stabilizes the column generation. A reduction in the number of calls … Read more

    Rational sums of hermitian squares of free noncommutative polynomials

  • Kristijan Cafuta
  • Igor Klep
  • Janez Povh
    • Categories Global Optimization, Linear, Cone and Semidefinite Programming, Optimization Software and Modeling Systems Tags , , , , , , , , , ,

    In this paper we consider polynomials in noncommuting variables that admit sum of hermitian squares and commutators decompositions. We recall algorithms for finding decompositions of this type that are based on semidefinite programming. The main part of the article investigates how to find such decomposition with rational coefficients if the original polynomial has rational coefficients. … Read more

    A scenario decomposition algorithm for 0-1 stochastic programs

  • Shabbir Ahmed
    • Categories Integer Programming, Parallel Algorithms, Stochastic Programming Tags , ,

    We propose a scenario decomposition algorithm for stochastic 0-1 programs. The algorithm recovers an optimal solution by iteratively exploring and cutting-off candidate solutions obtained from solving scenario subproblems. The scheme is applicable to quite general problem structures and can be implemented in a distributed framework. Illustrative computational results on standard two-stage stochastic integer programming and … Read more