October 2023 – Optimization Online

Hardness of pricing routes for two-stage stochastic vehicle routing problems with scenarios

Published: 2023/10/31

Combinatorial Optimization, Integer Programming, Stochastic Programming computational complexity, stochastic program, vehicle routing

The vehicle routing problem with stochastic demands (VRPSD) generalizes the classic vehicle routing problem by considering customer demands as random variables. Similarly to other vehicle routing variants, state-of-the-art algorithms for the VRPSD are often based on set-partitioning formulations, which require efficient routines for the associated pricing problems. However, all these set-partitioning-based approaches have strong assumptions … Read more

Strategy Investments in Matrix Games

Published: 2023/10/31

Raul Garcia

Seyedmohammadhossein Hosseinian

Mallesh Pai

Andrew J. Schaefer

(Mixed) Integer Linear Programming, Game Theory matrix games, mixed-integer linear programming, strategy investments

We propose an extension of matrix games where the row player may select rows and remove columns, subject to a budget constraint. We present an exact mixed-integer linear programming (MILP) formulation for the problem, provide analytical results concerning its solution, and discuss applications in the security domain. Our computational experiments show heuristic approaches on average … Read more

A variable neighborhood search for the green vehicle routing problem with two-dimensional loading constraints and split delivery

Published: 2023/10/31

Kamyla Ferreira

Thiago Alves de Queiroz

Pedro Munari

Franklina M. B. Toledo

Meta Heuristics, Production and Logistics, Transportation Greenhouse gas emissions, split-delivery, Two-dimensional loading constraints, variable neighborhood search, vehicle routing problem

 We address the Green Vehicle Routing Problem with Two-Dimensional Loading Constraints and Split Delivery (G2L-SDVRP), which extends the split delivery vehicle routing problem to include customer demands represented by two-dimensional, rectangular items. We aim to minimize carbon dioxide (CO$_2$) emissions instead of travel distance, a critical issue in contemporary logistics activities. The CO$_2$ emission … Read more

Robust Continuous-Time Service Network Design under Travel Time Uncertainty

Published: 2023/10/30

Shengnan Shu

Zhou Xu

Jin Qi

Applications - OR and Management Sciences, Network Optimization, Robust Optimization column-and-constraint generation, continuous time, exact algorithm, robust optimization, robust-satisficing, service network design, travel time uncertainty

The continuous-time service network design problem (CTSNDP) has wide applications in the field of transportation, but it is complicated by travel time uncertainty resulting from unpredictable traffic conditions. Incorporating uncertain travel times poses a significant challenge, as time-indexed mixed-integer linear programming (MILP) formulations commonly used to solve the CTSNDP with deterministic travel times become impractical. … Read more

Safeguarded augmented Lagrangian algorithms with scaled stopping criterion for the subproblems

Published: 2023/10/27

Ernesto G. Birgin

Gabriel Haeser

José Mario Martínez

Nonlinear Optimization augmented lagrangian method, Convergence, nonlinear optimization, scaled stopping criteria

At each iteration of the Safeguarded Augmented Lagrangian algorithm Algencan, a bound-constrained subproblem consisting of the minimization of the Powell-Hestenes-Rockafellar augmented Lagrangian function is considered, for which a minimizer with tolerance tending to zero is sought. More precisely, a point that satisfies a subproblem first-order necessary optimality condition with tolerance tending to zero is required. … Read more

Fixed point continuation algorithm with extrapolation for Schatten p-quasi-norm regularized matrix optimization problems

Published: 2023/10/27, Updated: 2023/10/28

Peng Dingtao

Nonsmooth Optimization, Unconstrained Optimization $R$-linear convergence rate, fixed point continuation algorithm with extrapolation, global whole sequence convergence, Low-rank matrix recovery problem, Schatten p-quasi-norm

In this paper, we consider a general low-rank matrix optimization problem which is modeled by a general Schatten p-quasi-norm (${\rm 0<p<1}$) regularized matrix optimization. For this nonconvex nonsmooth and non-Lipschitz matrix optimization problem, based on the matrix p-thresholding operator, we first propose a fixed point continuation algorithm with extrapolation (FPCAe) for solving it. Secondly, we … Read more

Exact and Heuristic Solution Approaches for Busy Time Minimization in Temporal Bin Packing

Published: 2023/10/27

John Martinovic

Nico Strasdat

(Mixed) Integer Linear Programming, Network Optimization Busy Time Minimization, cutting and packing, Flow Formulation, scheduling, Temporal Bin Packing

Given a set of jobs (or items), each of which being characterized by its resource demand and its lifespan, and a sufficiently large number of identical servers (or bins), the busy time minimization problem (BTMP) requires to find a feasible schedule (i.e., a jobs-to-servers assignment) having minimum overall power-on time. Although being linked to the … Read more

Learning Optimal Classification Trees Robust to Distribution Shifts

Published: 2023/10/26

(Mixed) Integer Linear Programming, Robust Optimization decision trees, distribution shift, mixed-integer programming, robust machine learning, robust optimization

We consider the problem of learning classification trees that are robust to distribution shifts between training and testing/deployment data. This problem arises frequently in high stakes settings such as public health and social work where data is often collected using self-reported surveys which are highly sensitive to e.g., the framing of the questions, the time … Read more