A New Sequential Updating Scheme of the Lagrange Multiplier for Multi-Block Linearly Constrained Separable Convex Optimization with Relaxed Step Sizes

  • Yuan Shen
  • Xiayang Zhang
  • Yannian Zuo
    • Categories Convex Optimization Tags , , ,

    In various applications such as signal/image processing, data mining, statistical learning and etc., the multi-block linearly constrained separable convex optimization is frequently used, where the objective function is the sum of multiple individual convex functions, and the major constraints are linear. A classical method for solving such kind of optimization problem could be the alternating … 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

    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

    Scheduling Post-disaster Repairs in Electricity Distribution Networks with Uncertain Repair Times

  • Mareldi Ahumada-Paras
  • Payman Arabshahi
  • Arindam Das
  • Daniel Kirschen
  • Yushi Tan
    • Categories Approximation Algorithms, Energy, Scheduling Tags , , ,

    Natural disasters, such as hurricanes, large wind and ice storms, typically require the repair of a large number of components in electricity distribution networks. Since power cannot be restored before the completion of repairs, optimally scheduling the available crews to minimize the cumulative duration of the customer interruptions reduces the harm done to the affected … Read more

    Exact solution of the donor-limited nearest neighbor hot deck imputation problem

  • Jan Pablo Burgard
  • Sven de Vries
  • Ulf Friedrich
  • Dennis Kreber
    • Categories Graphs and Matroids, Network Optimization, Statistics Tags , , , ,

    Data quality in population surveys suffers from missing responses. We use combinatorial optimization to create a complete and coherent data set. The methods are based on the widespread nearest neighbor hot deck imputation method that replaces the missing values with observed values from a close unit, the so-called donor. As a repeated use of donors … 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

    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