Tractable Reformulations of Distributionally Robust Two-stage Stochastic Programs with $\infty- Distance

  • Weijun Xie
    • Categories Stochastic Programming Tags , , , ,

    This paper studies a two-stage distributionally robust stochastic linear program under the type-∞ Wasserstein ball by providing sufficient conditions under which the program can be efficiently computed via a tractable convex program. By exploring the properties of binary variables, the developed reformulation techniques are extended to those with mixed binary random parameters. The main tractable … Read more

    Branch-and-Cut-and-Price for Multi-Agent Pathfinding

  • Daniel Harabor
  • Edward Lam
  • Pierre Le Bodic
  • Peter J. Stuckey
    • Categories 0-1 Programming, Branch and Cut Algorithms, Transportation Tags , , , ,

    There are currently two broad strategies for optimal Multi-agent Pathfinding (MAPF): (1) search-based methods, which model and solve MAPF directly, and (2) compilation-based solvers, which reduce MAPF to instances of well-known combinatorial problems, and thus, can benefit from advances in solver techniques. In this work, we present an optimal algorithm, BCP, that hybridizes both approaches … Read more

    On the asymptotic convergence and acceleration of gradient methods

  • Yu-Hong Dai
  • Yakui Huang
  • Xin-Wei Liu
  • Hongchao Zhang
    • Categories Convex Optimization, Quadratic Programming, Unconstrained Optimization Tags , , , , , ,

    We consider the asymptotic behavior of a family of gradient methods, which include the steepest descent and minimal gradient methods as special instances. It is proved that each method in the family will asymptotically zigzag between two directions. Asymptotic convergence results of the objective value, gradient norm, and stepsize are presented as well. To accelerate … Read more

    Computing Estimators of Dantzig Selector type via Column and Constraint Generation

  • Rahul Mazumder
  • Stephen Wright
  • Andrew Zheng
    • Categories Linear Programming, Statistics Tags , ,

    We consider a class of linear-programming based estimators in reconstructing a sparse signal from linear measurements. Specific formulations of the reconstruction problem considered here include Dantzig selector, basis pursuit (for the case in which the measurements contain no errors), and the fused Dantzig selector (for the case in which the underlying signal is piecewise constant). … Read more

    Complementary problems with polynomial data

  • Canh Hung Nguyen
  • Tiên-So'n Pham
    • Categories Complementarity and Variational Inequalities Tags , , , , ,

    Given polynomial maps $f, g \colon \mathbb{R}^n \to \mathbb{R}^n,$ we consider the {\em polynomial complementary problem} of finding a vector $x \in \mathbb{R}^n$ such that \begin{equation*} f(x) \ \ge \ 0, \quad g(x) \ \ge \ 0, \quad \textrm{ and } \quad \langle f(x), g(x) \rangle \ = \ 0. \end{equation*} In this paper, we … Read more

    Order Acceptance in Same-Day Delivery

  • Alan L. Erera
  • Mathias A. Klapp
  • Alejandro Toriello
    • Categories Supply Chain Management Tags ,

    We study order acceptance dynamics in same-day delivery systems by formulating the Dynamic Dispatch Waves Problem with Immediate Acceptance, which models integrated request management and order distribution for dynamically arriving requests. When a delivery request arrives, a decision is made immediately to accept (offer service) or reject (with a penalty). Accepted requests are not available … Read more

    Relations Between Abs-Normal NLPs and MPCCs Part 2: Weak Constraint Qualifications

  • Lisa Hegerhorst-Schultchen
  • Christian Kirches
  • Marc C. Steinbach
    • Categories Nonsmooth Optimization Tags , , , ,

    This work continues an ongoing effort to compare non-smooth optimization problems in abs-normal form to Mathematical Programs with Complementarity Constraints (MPCCs). We study general Nonlinear Programs with equality and inequality constraints in abs-normal form, so-called Abs-Normal NLPs, and their relation to equivalent MPCC reformulations. We introduce the concepts of Abadie’s and Guignard’s kink qualification and … Read more

    Gaining traction – On the convergence of an inner approximation scheme for probability maximization

  • Csaba I. Fábián
    • Categories Convex Optimization, Stochastic Programming Tags ,

    We analyze an inner approximation scheme for probability maximization. The approach was proposed in Fabian, Csizmas, Drenyovszki, Van Ackooij, Vajnai, Kovacs, Szantai (2018) Probability maximization by inner approximation, Acta Polytechnica Hungarica 15:105-125, as an analogue of a classic dual approach in the handling of probabilistic constraints. Even a basic implementation of the maximization scheme proved … Read more

    A Survey of Recent Scalability Improvements for Semidefinite Programming with Applications in Machine Learning, Control, and Robotics

  • Amir Ali Ahmadi
  • Georgina Hall
  • Anirudha Majumdar
    • Categories Basic Sciences Applications, Control Applications, Semi-definite Programming Tags , , , ,

    Historically, scalability has been a major challenge to the successful application of semidefinite programming in fields such as machine learning, control, and robotics. In this paper, we survey recent approaches for addressing this challenge including (i) approaches for exploiting structure (e.g., sparsity and symmetry) in a problem, (ii) approaches that produce low-rank approximate solutions to … Read more

    Computational Enhancement in the Application of the Branch and Bound Method for Linear Integer Programs and Related Models

  • Ali Al-Hasani
  • Andrew C. Eberhard
  • Masar Al-Rabeeah
  • Santosh Kumar
  • Elias Munapo
    • Categories Applications - OR and Management Sciences, Multi-Criteria Optimization Tags , , , , ,

    In this paper, a reformulation that was proposed for a knapsack problem has been extended to single and bi-objective linear integer programs. A further reformulation by adding an upper bound constraint for a knapsack problem is also proposed and extended to the bi-objective case. These reformulations significantly reduce the number of branch and bound iterations … Read more