Month: July 2014

Nonanticipative duality, relaxations, and formulations for chance-constrained stochastic programs

  • Shabbir Ahmed
  • James R. Luedtke
  • Yongjia Song
  • Weijun Xie
    • Categories Stochastic Programming Tags , ,

    We propose two new Lagrangian dual problems for chance-constrained stochastic programs based on relaxing nonanticipativity constraints. We compare the strength of the proposed dual bounds and demonstrate that they are superior to the bound obtained from the continuous relaxation of a standard mixed-integer programming (MIP) formulation. For a given dual solution, the associated Lagrangian relaxation … Read more

    Mixed-integer Quadratic Programming is in NP

  • Alberto Del Pia
  • Santanu S. Dey
  • Marco Molinaro
    • Categories Integer Programming Tags , ,

    Mixed-integer quadratic programming (MIQP) is the problem of optimizing a quadratic function over points in a polyhedral set where some of the components are restricted to be integral. In this paper, we prove that the decision version of mixed-integer quadratic programming is in NP, thereby showing that it is NP-complete. This is established by showing … Read more

    A scalable bounding method for multi-stage stochastic integer programs

  • Osman Y. Ozaltin
  • Burhaneddin Sandikçi
    • Categories Integer Programming, Parallel Algorithms, Stochastic Programming Tags , , , ,

    Many dynamic decision problems involving uncertainty can be appropriately modeled as multi-stage stochastic programs. However, most practical instances are so large and/or complex that it is impossible to solve them on a single computer, especially due to memory limitations. Extending the work of Sandikci et al. (2013) on two-stage stochastic mixed-integer-programs (SMIPs), this paper develops … Read more

    Globally Convergent Evolution Strategies for Constrained Optimization.

  • Youssef Diouane
  • Serge Gratton
  • Luis Nunes Vicente
    • Categories Constrained Nonlinear Optimization Tags , , , , , , ,

    In this work we propose, analyze, and test algorithms for linearly constrained optimization when no use of derivatives of the objective function is made. The proposed methodology is built upon the globally convergent evolution strategies previously introduced by the authors for unconstrained optimization. Two approaches are encompassed to handle the constraints. In a first approach, … Read more

    Branch-and-bound for bi-objective integer programming

  • Sophie N. Parragh
  • Fabien Tricoire
    • Categories Combinatorial Optimization, Integer Programming, Multi-Criteria Optimization Tags , , , ,

    In Pareto bi-objective integer optimization the optimal result corresponds to a set of non- dominated solutions. We propose a generic bi-objective branch-and-bound algorithm that uses a problem-independent branching rule exploiting available integer solutions, and cutting plane generation taking advantage of integer objective values. The developed algorithm is applied to the bi-objective team orienteering problem with … Read more

    Analysis of mixed integer programming formulations for single machine scheduling problems with sequence dependent setup times and release dates

  • Carlos R. V. Carvalho
  • Mauricio Cardoso de Souza
  • Thiago Henrique Nogueira
  • Martín Gómez Ravetti
    • Categories Scheduling Tags , , ,

    In this article, six different mixed integer programming (MIP) formulations are proposed and analyzed. These formulations are based on the knowledge of four different paradigms for single machine scheduling problems (SMSP) with sequence dependent setup times and release dates. Each formulation reflects a specific concept on how the variables and parameters are defined, requiring particular … Read more

    HIGHER-ORDER METRIC SUBREGULARITY AND ITS APPLICATIONS

  • Boris S. Mordukhovich
  • Wei Ouyang
    • Categories Nonlinear Optimization Tags , , ,

    This paper is devoted to the study of metric subregularity and strong subregularity of any positive order $q$ for set-valued mappings in finite and infinite dimensions. While these notions have been studied and applied earlier for $q=1$ and—to a much lesser extent—for $q\in(0,1)$, no results are available for the case $q>1$. We derive characterizations of … Read more

    Justification of Constrained Game Equilibrium Models

  • Igor V. Konnov
    • Categories Basic Sciences Applications, Complementarity and Variational Inequalities, Game Theory

    We consider an extension of a noncooperative game where players have joint binding constraints. In this model, the constrained equilibrium can not be implemented within the same noncooperative framework and requires some other additional regulation procedures. We consider several approaches to resolution of this problem. In particular, a share allocation method is presented and substantiated. … Read more

    The Quadratic Assignment Problem is Easy for Robinsonian Matrices

  • Monique Laurent
  • Matteo Seminaroti
    • Categories Combinatorial Optimization

    We present a new polynomially solvable case of the Quadratic Assignment Problem in Koopmans-Beckman form QAP(A,B), by showing that the identity permutation is optimal when A and B are respectively a Robinson similarity and dissimilarity matrix and one of A or B is a Toeplitz matrix. A Robinson (dis)similarity matrix is a symmetric matrix whose … Read more

    Circuit and bond polytopes on series-parallel graphs

  • S. Borne
  • Pierre Fouilhoux
  • R. Grappe
  • Mathieu Lacroix
  • Pierre Pesneau
    • Categories Polyhedra Tags , , ,

    In this paper, we describe the circuit polytope on series-parallel graphs. We first show the existence of a compact extended formulation. Though not being explicit, its construction process helps us to inductively provide the description in the original space. As a consequence, using the link between bonds and circuits in planar graphs, we also describe … Read more