Month: October 2016

Solving Linear Programs with Complementarity Constraints using Branch-and-Cut

  • John E. Mitchell
  • Jong-Shi Pang
  • Bin Yu
    • Categories Branch and Cut Algorithms, Complementarity and Variational Inequalities Tags , ,

    A linear program with linear complementarity constraints (LPCC) requires the minimization of a linear objective over a set of linear constraints together with additional linear complementarity constraints. This class has emerged as a modeling paradigm for a broad collection of problems, including bilevel programs, Stackelberg games, inverse quadratic programs, and problems involving equilibrium constraints. The … Read more

    Joint rectangular geometric chance constrained programs

  • Zhiping Chen
  • Abdel Lisser
  • Jia Liu
  • Chuan Xu
    • Categories Stochastic Programming Tags , , ,

    This paper discusses joint rectangular geometric chance constrained programs. When the stochastic parameters are elliptically distributed and pairwise independent, we present a reformulation of the joint rectangular geometric chance constrained programs. As the reformulation is not convex, we propose new convex approximations based on variable transformation together with piecewise linear approximation method. Our results show … Read more

    Quadratic regularization with cubic descent for unconstrained optimization

  • Ernesto G. Birgin
  • José Mario Martínez
    • Categories Unconstrained Optimization Tags , , , ,

    Cubic-regularization and trust-region methods with worst case first-order complexity $O(\varepsilon^{-3/2})$ and worst-case second-order complexity $O(\varepsilon^{-3})$ have been developed in the last few years. In this paper it is proved that the same complexities are achieved by means of a quadratic regularization method with a cubic sufficient-descent condition instead of the more usual predicted-reduction based descent. … Read more

    Combining Penalty-based and Gauss-Seidel Methods for solving Stochastic Mixed-Integer Problems

  • Eberhard Andrew
  • Brian Dandurand
  • Fabricio Oliveira
  • Jeffrey Christiansen
    • Categories Stochastic Programming Tags , , , ,

    In this paper, we propose a novel decomposition approach for mixed-integer stochastic programming (SMIP) problems that is inspired by the combination of penalty-based Lagrangian and block Gauss-Seidel methods (PBGS). In this sense, PBGS is developed such that the inherent decomposable structure that SMIPs present can be exploited in a computationally efficient manner. The performance of … Read more

    Tighter MIP Models for Barge Container Ship Routing

  • Laurent Alfandari
  • Fabio Furini
  • Ivana Ljubić
  • Tatjana Davidovic
  • Vladislav Maras
  • Sébastien Martin
    • Categories Applications - OR and Management Sciences Tags , , , ,

    This paper addresses the problem of optimal planning of a line for a barge container shipping company. Given estimated weekly splittable demands between pairs of ports and bounds for the turnaround time, our goal is to determine the subset of ports to be called and the amount of containers to be shipped between each pair … Read more

    Novel formulations for general and security Stackelberg games

  • Carlos Casorrán
  • Bernard Fortz
  • Martine Labbé
  • Fernando Ordóñez
    • Categories (Mixed) Integer Linear Programming, Combinatorial Optimization, Polyhedra Tags , , ,

    In this paper we analyze general Stackelberg games (SGs) and Stackelberg security games (SSGs). SGs are hierarchical adversarial games where players select actions or strategies to optimize their payoffs in a sequential manner. SSGs are a type of SGs that arise in security applications, where the strategies of the player that acts first consist in … Read more

    On the local convergence analysis of the Gradient Sampling method

  • Elias Salomão Helou
  • Sandra Augusta Santos
  • Lucas E. A. Simões
    • Categories Convex and Nonsmooth Optimization, Nonlinear Optimization

    The Gradient Sampling method is a recently developed tool for solving unconstrained nonsmooth optimization problems. Using just first order information about the objective function, it generalizes the steepest descent method, one of the most classical methods to minimize a smooth function. This manuscript aims at determining under which circumstances one can expect the same local … Read more

    A Spatial Branch-and-Cut Method for Nonconvex QCQP with Bounded Complex Variables

  • Alper Atamturk
  • Shmuel Oren
  • Chen Chen
    • Categories (Mixed) Integer Nonlinear Programming

    We develop a spatial branch-and-cut approach for nonconvex Quadratically Constrained Quadratic Programs with bounded complex variables (CQCQP). Linear valid inequalities are added at each node of the search tree to strengthen semidefinite programming relaxations of CQCQP. These valid inequalities are derived from the convex hull description of a nonconvex set of $2 \times 2$ positive … Read more

    Error bounds for nonlinear semidefinite optimization

  • Hiroshi Yamashita
    • Categories Nonlinear Optimization Tags ,

    In this paper, error bounds for nonlinear semidefinite optimization problem is considered. We assume the second order sufficient condition, the strict complementarity condition and the MFCQ condition at the KKT point. The nondegeneracy condition is not assumed in this paper. Therefore the Jacobian operator of the equality part of the KKT conditions is not assumed … Read more

    Branch-and-bound for biobjective mixed-integer linear programming

  • Nathan Adelgren
  • Akshay Gupte
    • Categories (Mixed) Integer Linear Programming, Branch and Cut Algorithms, Multi-Criteria Optimization Tags , , , ,

    We present a generic branch-and-bound algorithm for finding all the Pareto solutions of a biobjective mixed-integer linear program. The main contributions are new algorithms for obtaining dual bounds at a node, checking node fathoming, presolve, and duality gap measurement. Our branch-and-bound is predominantly a decision space search method because the branching is performed on the … Read more