Compromise Policy for Multi-stage Stochastic Linear Programming: Variance and Bias Reduction

This paper focuses on algorithms for multi-stage stochastic linear programming (MSLP). We propose an ensemble method named the “compromise policy”, which not only reduces the variance of the function approximation but also reduces the bias of the estimated optimal value. It provides a tight lower bound estimate with a confidence interval. By exploiting parallel computing, … Read more

The projective exact penalty method for general constrained optimization

A new projective exact penalty function method is proposed for the equivalent reduction of constrained optimization problems to nonsmooth unconstrained ones. In the method, the original objective function is extended to infeasible points by summing its value at the projection of an infeasible point on the feasible set with the distance to the projection. The … Read more

Dual Bounds from Decision Diagram-Based Route Relaxations: An Application to Truck-Drone Routing

For vehicle routing problems, strong dual bounds on the optimal value are needed to develop scalable exact algorithms, as well as to evaluate the performance of heuristics. In this work, we propose an iterative algorithm to compute dual bounds motivated by connections between decision diagrams (DDs) and dynamic programming (DP) models used for pricing in … Read more

Behind the Scenes of Gradient Descent: A Trajectory Analysis via Basis Function Decomposition

This work analyzes the solution trajectory of gradient-based algorithms via a novel basis function decomposition. We show that, although solution trajectories of gradient-based algorithms may vary depending on the learning task, they behave almost monotonically when projected onto an appropriate orthonormal function basis. Such projection gives rise to a basis function decomposition of the solution … Read more

A binary linear programming approach for supporting administrative territorial consolidation

The objective of this paper is to develop a scalable binary linear programming model for finding the optimal aggregation of communes into spatially contiguous administrative territorial units (ATUs) constrained on certain balancing criteria. The requirement for the ATUs to be contiguous represents the main computational bottleneck and, therefore, it prevents one from using such models … Read more