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

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

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

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

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

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

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

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

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

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

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

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

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