Month: February 2019

Risk Aversion to Parameter Uncertainty in Markov Decision Processes with an Application to Slow-Onset Disaster Relief

  • Simge Küçükyavuz
  • Merve Merakli
    • Categories Integer Programming, Stochastic Programming, Supply Chain Management Tags , , , , ,

    In classical Markov Decision Processes (MDPs), action costs and transition probabilities are assumed to be known, although an accurate estimation of these parameters is often not possible in practice. This study addresses MDPs under cost and transition probability uncertainty and aims to provide a mathematical framework to obtain policies minimizing the risk of high long-term … Read more

    A polynomial algorithm for minimizing travel time in time-dependent networks with waits

  • Jérémy Omer
  • Michael Poss
    • Categories Network Optimization

    We consider a time-dependent shortest path problem with possible waiting at each node and a global bound $W$ on the total waiting time. The goal is to minimize only the time travelled along the edges of the path, not including the waiting time. We prove that the problem can be solved in polynomial time when … Read more

    A Computational Comparison of Optimization Methods for the Golomb Ruler Problem

  • Burak Kocuk
  • Willem-Jan van Hoeve
    • Categories Integer Programming Tags , ,

    The Golomb ruler problem is defined as follows: Given a positive integer n, locate n marks on a ruler such that the distance between any two distinct pair of marks are different from each other and the total length of the ruler is minimized. The Golomb ruler problem has applications in information theory, astronomy and … Read more

    Pathfollowing for Parametric Mathematical Programs with Complementarity Constraints

  • Johannes Jäschke
  • Vyacheslav Kungurtsev
    • Categories Constrained Nonlinear Optimization

    In this paper we study procedures for pathfollowing parametric mathematical pro- grams with complementarity constraints. We present two procedures, one based on the penalty approach to solving standalone MPCCs, and one based on tracing active set bifurcations aris- ing from doubly-active complementarity constraints. We demonstrate the performance of these approaches on a variety of examples … Read more

    Time-Dependent Shortest Path Problems with Penalties and Limits on Waiting

  • Natashia Boland
  • George L. Nemhauser
  • Martin Savelsbergh
  • Edward He
    • Categories Network Optimization, Transportation Tags , , ,

    Waiting at the right location at the right time can be critically important in certain variants of time-dependent shortest path problems. We investigate the computational complexity of time-dependent shortest path problems in which there is either a penalty on waiting or a limit on the total time spent waiting at a given subset of the … Read more

    Dynamic Discretization Discovery Algorithms for Time-Dependent Shortest Path Problems

  • Natashia Boland
  • George L. Nemhauser
  • Martin Savelsbergh
  • Edward He
    • Categories Network Optimization, Transportation Tags , , , , ,

    Finding a shortest path in a network is an iconic optimization problem. We focus on settings in which the travel time on an arc in the network depends on the time at which traversal of the arc begins. In such settings, reaching the sink as early as possible is not the only objective of interest. … Read more

    Optimizing the Recovery of Disrupted Multi-Echelon Assembly Supply Chain Networks

  • John E. Mitchell
  • Huy Nguyen
  • Thomas C. Sharkey
  • William A. Wallace
    • Categories Applications - OR and Management Sciences Tags , ,

    We consider optimization problems related to the scheduling of multi-echelon assembly supply chain (MEASC) networks that have applications in the recovery from large-scale disruptive events. Each manufacturer within this network assembles a component from a series of sub-components received from other manufacturers. We develop scheduling decision rules that are applied locally at each manufacturer and … Read more

    A two-level distributed algorithm for nonconvex constrained optimization

  • Xu Andy Sun
  • Kaizhao Sun
    • Categories Network Optimization, Nonlinear Optimization, Parallel Algorithms Tags , ,

    This paper aims to develop distributed algorithms for nonconvex optimization problems with complicated constraints associated with a network. The network can be a physical one, such as an electric power network, where the constraints are nonlinear power flow equations, or an abstract one that represents constraint couplings between decision variables of different agents. Despite the … Read more

    A branch and cut algorithm for the time-dependent profitable tour problem with resource constraints

  • Gonzalo Lera-Romero
  • Juan José Miranda-Bront
    • Categories Branch and Cut Algorithms, Transportation

    In this paper we study the time-dependent profitable tour problem with resource con-straints (TDPTPRC), a generalization of the profitable tour problem (PTP) which includes variable travel times to account for road congestion. In this problem, the set of customers to be served is not given and must be determined based on the profit collected when … Read more

    Recovery of a mixture of Gaussians by sum-of-norms clustering

  • Tao Jiang
  • Stephen A. Vavasis
  • Chen Wen Zhai
    • Categories Second-Order Cone Programming, Statistics

    Sum-of-norms clustering is a method for assigning $n$ points in $\R^d$ to $K$ clusters, $1\le K\le n$, using convex optimization. Recently, Panahi et al.\ proved that sum-of-norms clustering is guaranteed to recover a mixture of Gaussians under the restriction that the number of samples is not too large. The purpose of this note is to … Read more