Month: August 2014

An SDP approach for multiperiod mixed 0–1 linear programming models with stochastic dominance constraints for risk management

  • Laureano F. Escudero
  • Dolores Romero Morales
  • Juan F. Monge
    • Categories (Mixed) Integer Linear Programming, Stochastic Programming, Supply Chain Management

    In this paper we consider multiperiod mixed 0–1 linear programming models under uncertainty. We propose a risk averse strategy using stochastic dominance constraints (SDC) induced by mixed-integer linear recourse as the risk measure. The SDC strategy extends the existing literature to the multistage case and includes both first-order and second-order constraints. We propose a stochastic … Read more

    Local Search for Hop-constrained Directed Steiner Tree Problem with Application to UAV-based Multi-target Surveillance

  • Oleg Burdakov
  • Patrick Doherty
  • Jonas Kvarnström
    • Categories Applications - OR and Management Sciences, Multi-Criteria Optimization, Network Optimization Tags , , , ,

    We consider the directed Steiner tree problem (DSTP) with a constraint on the total number of arcs (hops) in the tree. This problem is known to be NP-hard, and therefore, only heuristics can be applied in the case of its large-scale instances. For the hop-constrained DSTP, we propose local search strategies aimed at improving any … Read more

    On fast trust region methods for quadratic models with linear constraints

  • M.J.D. Powell
    • Categories Constrained Nonlinear Optimization, Quadratic Programming

    Quadratic models Q_k(.) of the objective function F(.) are used by many successful iterative algorithms for minimization, where k is the iteration number. Given the vector of variables x_k, a new vector x_{k+1} may be calculated that satisfies Q_k(x_{k+1}) < Q_k(x_k), in the hope that it provides the reduction F(x_{k+1}) < F(x_k). Trust region methods ... Read more

    On a new class of matrix support functionals with applications

  • James V. Burke
  • Tim Hoheisel
    • Categories Convex and Nonsmooth Optimization, Quadratic Programming, Semi-definite Programming Tags , , , , , ,

    A new class of matrix support functionals is presented which establish a connection between optimal value functions for quadratic optimization problems, the matrix-fractional function, the pseudo matrix-fractional function, and the nuclear norm. The support function is based on the graph of the product of a matrix with its transpose. Closed form expressions for the support … Read more

    An Exact Extended Formulation for the Unrelated Parallel Machine Total Weighted Completion Time Problem

  • Kerem Bülbül
  • Halil Sen
    • Categories (Mixed) Integer Linear Programming, Cutting Plane Approaches, Scheduling

    The plethora of research on NP-hard parallel machine scheduling problems is focused on heuristics due to the theoretically and practically challenging nature of these problems. Only a handful of exact approaches are available in the literature, and most of these suffer from scalability issues. Moreover, the majority of the papers on the subject are restricted … Read more

    Matrix monotonicity and self-concordance:how to handle quantum entropy in optimization problems

  • Leonid Faybusovich
  • Takashi Tsuchiya
    • Categories Convex Optimization, Linear, Cone and Semidefinite Programming Tags , ,

    Let $g$ be a continuously differentiable function whose derivative is matrix monotone on positive semi-axis. Such a function induces a function $\phi (x)=tr(g(x))$ on the cone of squares of an arbitrary Euclidean Jordan algebra. We show that $\phi (x) -\ln \det(x)$ is a self-concordant function on the interior of the cone. We also show that … Read more

    How the augmented Lagrangian algorithm can deal with an infeasible convex quadratic optimization problem

  • Alice Chiche
  • Jean Charles Gilbert
    • Categories Convex and Nonsmooth Optimization, Quadratic Programming Tags , , , , , , , , ,

    This paper analyses the behavior of the augmented Lagrangian algorithm when it deals with an infeasible convex quadratic optimization problem. It is shown that the algorithm finds a point that, on the one hand, satisfies the constraints shifted by the smallest possible shift that makes them feasible and, on the other hand, minimizes the objective … Read more

    Multilevel Optimization Modeling for Risk-Averse Stochastic Programming

  • Jonathan Eckstein
  • Jingnan Fan
  • Deniz Eskandani
    • Categories Stochastic Programming Tags , , ,

    Coherent risk measures have become a popular tool for incorporating risk aversion into stochastic optimization models. For dynamic models in which uncertainty is resolved at more than one stage, however, using coherent risk measures within a standard single-level optimization framework becomes problematic. To avoid severe time-consistency difficulties, the current state of the art is to … Read more

    On the exact separation of rank inequalities for the maximum stable set problem

  • Stefano Coniglio
  • Stefano Gualandi
    • Categories (Mixed) Integer Linear Programming, Cutting Plane Approaches, Polyhedra Tags , , , , ,

    When addressing the maximum stable set problem on a graph G = (V,E), rank inequalities prescribe that, for any subgraph G[U] induced by U ⊆ V , at most as many vertices as the stability number of G[U] can be part of a stable set of G. These inequalities are very general, as many of … Read more