An Efficient Adaptive Large Neighborhood Search Algorithm for the Flying Sidekick Traveling Salesman Problem

Categories Combinatorial Optimization, Meta Heuristics Tags , ,

This paper investigates the Flying Sidekick Traveling Salesman Problem (FSTSP), and proposes an efficient Adaptive Large Neighborhood Search (ALNS) algorithm. Our proposed framework operates directly on a complete solution representation, eliminating the reconstruction step required by indirect encodings and making temporal information immediately accessible during the search process. A stage-based mechanism is introduced to efficiently … Read more

Robust Optimization Under Sparse Uncertainty

Categories Robust Optimization Tags , , , ,

Classical robust optimization relies on convex and bounded uncertainty sets, an assumption that is inadequate for sparse uncertainty, where only a small, unknown subset of parameters deviates from its nominal value. This sparsity makes the uncertainty set nonconvex and turns separation into a combinatorial problem, so standard duality-based reformulations do not apply. We study two … Read more

The fixed-point bundle method over product-of-simplex domains arising from game equilibria

Categories Complementarity and Variational Inequalities, Game Theory Tags , , , ,

This paper extends the fixed-point bundle framework for finite-dimensional variational inequalities (VIs) from the simplex domain to the product-of-simplex domain, which is directly applicable to solving Nash equilibria. The fixed-point bundle for VIs on the product-of-simplex domain reveals a composite fiber bundle structure. The key innovation is to construct an equivalent VI on the simplex … Read more

Integer quadratic programming in fixed dimension is polynomial-time solvable

Categories (Mixed) Integer Nonlinear Programming, Cutting Plane Approaches, Quadratic Programming Tags , ,

We give a deterministic polynomial-time algorithm for integer quadratic programming in every fixed dimension: it minimizes an arbitrary rational quadratic exactly over the integer points of a rational polyhedron, or certifies infeasibility or integer unboundedness. The core is a sign test that decides whether \(d^{\mathsf{T}}Qd\ge 0\) for every integer point \(d\) of a bounded symmetric … Read more

Two-Stage Stochastic Optimization for Capacitated Facility Location Under Demand Uncertainty

Categories (Mixed) Integer Linear Programming, Facility Planning and Design, Stochastic Programming Tags , , , , ,

Facility location decisions are typically made before demand is fully known, yet most applied studies solve a single deterministic model using expected or nominal demand. This paper formulates and solves a capacitated facility location problem using a real academic benchmark instance, then extends it to a two-stage stochastic program in which facility-opening decisions are made … Read more

Unshackling Column Generation for Linearized Unconstrained Binary Quadratic Programs

Categories Integer Programming, Linear Programming, Nonlinear Optimization Tags , , ,

When linearizing binary quadratic programs, the most usual way is to replace bilinear products with additional variables constrained to take on consistent values in any feasible solution. In this setting, column generation is a principally desirable solution technique, for instance because the number of such additional linearization variables may be large while many of them … Read more

An exact algorithm for the probabilistic TSP via a new tractable convex representation of recourse

Categories (Mixed) Integer Linear Programming, Convex Optimization, Stochastic Programming Tags , , , ,

We consider the probabilistic traveling salesman problem (PTSP) in which customer presences are Bernoulli random variables, and the objective is to determine an a priori tour minimizing the expected traveling cost of the a posteriori tour obtained by skipping absent customers after customer presence is revealed. The existing literature has established that, given an a … Read more

Twist Without Tangle: Flutter Suppression of Thin-Walled Wing-Engine Systems via Curvilinear Fiber Path Tailoring and Cross-Section Optimization

Categories Applications - Science and Engineering, Optimization of Simulated Systems, Optimization of Systems modeled by PDEs Tags , , ,

Flutter is traditionally delayed by modifying either a structure’s geometry or its stiffness distribution. Here, we show that allowing both to evolve simultaneously can unlock a fundamentally different route to aeroelastic stability. We concurrently optimize the cross-sectional geometry and fiber paths of a composite thin-walled wing–engine system to maximize flutter onset. The wing structure is … Read more

A Proximal Approach for Nonsmooth Composite-Constrained Optimization

Categories Constrained Nonlinear Optimization, Nonlinear Optimization, Nonsmooth Optimization, Stochastic Programming Tags , , ,

We propose a proximal-type algorithm for nonsmooth and nonconvex optimization problems with composite constraints. The constraint is defined by the composition of a locally upper-\(C^2\) outer function with a locally Lipschitz continuous inner mapping. The method is based on an improvement function that balances objective decrease and constraint satisfaction, and on a surrogate model obtained … Read more

Scenario Tradeoffs in Uncertain Multiobjective Optimization

Categories Multi-Criteria Optimization, Robust Optimization Tags , , ,

Realistic decision problems are inherently multiobjective and uncertain. To manage both of these complexities, robust multiobjective optimization strives to aid the decision maker in finding a decision which is Pareto efficient and is hedged against the worst-case scenario. In this paper, we present a robustness approach which is grounded in the decision maker’s preferences by … Read more