Month: January 2025

Strengthening Dual Bounds for Multicommodity Capacitated Network Design with Unsplittable Flow Constraints

  • Lacy M. Greening
  • Santanu S. Dey
  • Alan L. Erera
    • Categories Integer Programming, Network Optimization, Production and Logistics Tags , , ,

    Multicommodity capacitated network design (MCND) models can be used to optimize the consolidation of shipments within e-commerce fulfillment networks. In practice, fulfillment networks require that shipments with the same origin and destination follow the same transfer path. This unsplittable flow requirement complicates the MCND problem, requiring integer programming (IP) formulations with binary variables replacing continuous … Read more

    Lagrangian Duality for Mixed-Integer Semidefinite Programming: Theory and Algorithms

  • Frank de Meijer
  • Renata Sotirov
    • Categories (Mixed) Integer Nonlinear Programming, Semi-definite Programming Tags , , ,

    This paper presents the Lagrangian duality theory for mixed-integer semidefinite programming (MISDP). We derive the Lagrangian dual problem and prove that the resulting Lagrangian dual bound dominates the bound obtained from the continuous relaxation of the MISDP problem. We present a hierarchy of Lagrangian dual bounds by exploiting the theory of integer positive semidefinite matrices … Read more

    Risk-Averse Antibiotics Time Machine Problem

  • Deniz Tuncer
  • Burak Kocuk
    • Categories (Mixed) Integer Linear Programming, Applications - Science and Engineering, Stochastic Programming Tags , , ,

    Antibiotic resistance, which is a serious healthcare issue, emerges due to uncontrolled and repeated antibiotic use that causes bacteria to mutate and develop resistance to antibiotics. The Antibiotics Time Machine Problem aims to come up with treatment plans that maximize the probability of reversing these mutations. Motivated by the severity of the problem, we develop … Read more

    A stochastic Lagrangian-based method for nonconvex optimization with nonlinear constraints

  • Dimitri Papadimitriou
    • Categories Constrained Nonlinear Optimization, Nonlinear Optimization

    The Augmented Lagrangian Method (ALM) is one of the most common approaches for solving linear and nonlinear constrained problems. However, for non-convex objectives, handling non-linear inequality constraints remains challenging. In this paper, we propose a stochastic ALM with Backtracking Line Search that performs on a subset (mini-batch) of randomly selected points for the solving of … Read more

    New Dynamic Discretization Discovery Strategies for Continuous-Time Service Network Design

  • Shengnan Shu
  • Zhou Xu
  • Roberto Baldacci
    • Categories Applications - OR and Management Sciences, Integer Programming, Network Optimization Tags , , ,

    Service Network Design Problems (SNDPs) are prevalent in the freight industry. While the classic SNDP is defined on a discretized planning horizon with integral time units, the Continuous-Time SNDP (CTSNDP) uses a continuous-time horizon to avoid discretization errors. Existing CTSNDP algorithms primarily rely on the Dynamic Discretization Discovery (DDD) framework, which iteratively refines discretization and … Read more

    A Single-Level Reformulation of Integer Bilevel Programs using Decision Diagrams

  • Sebastian Vasquez
  • Leonardo Lozano
  • Willem-Jan van Hoeve
    • Categories Combinatorial Optimization, Integer Programming Tags , ,

    Integer bilevel programs are notoriously difficult to solve due to the absence of strong and efficiently computable relaxations. In this work, we introduce a novel single-level reformulation of these programs by leveraging a network flow-based representation of the follower’s value function, utilizing decision diagrams and linear programming duality. This approach enables the development of scalable … Read more

    On Two Vectorization Schemes for Set-valued Optimization

  • Gabriele Eichfelder
  • Tobias Gerlach
  • Ernest Quintana
  • Stefan Rocktäschel
    • Categories Multi-Criteria Optimization Tags , , ,

    In this paper, we investigate two known solution approaches for set-valued optimization problems, both of which are based on so-called vectorization strategies. These strategies consist of deriving a parametric family of multi-objective optimization problems whose optimal solution sets approximate those of the original set-valued problem with arbitrary accuracy in a certain sense. Thus, these approaches … Read more

    The robust pickup and delivery problem with time windows

  • Alex Abreu
  • Maria Battarra
  • Luciano Costa
  • Pedro Munari
    • Categories Applications - OR and Management Sciences, Transportation Tags , , , ,

    This study addresses the robust pickup and delivery problem with time windows (RPDPTW), in which uncertainty in demands and travel times is modelled using robust optimisation. The RPDPTW involves determining the least-cost routes to serve transportation requests from origins to destinations, while respecting vehicle capacity and time window constraints under all anticipated realisations of uncertain … Read more

    Restarting nonlinear conjugate gradient methods

  • Morteza Kimiaei
  • Saman Babaie-Kafaki
  • Vyacheslav Kungurtsev
  • Mahsa.Yousefi
    • Categories Nonlinear Optimization Tags , , , ,

    In unconstrained optimization, due to the nonlinearity of the objective function or rounding errors in finite precision arithmetic, it can happen that NaN or infinite step sizes appear in the nonlinear conjugate gradient (NCG) method, or otherwise the step violates the sufficient descent condition (SDC). In this case the conjugate gradient (CG) direction must often … Read more

    A class of diagonal quasi-Newton penalty decomposition algorithms for sparse bound-constrained nonconvex optimization

  • Ahmad Mousavi
  • Morteza Kimiaei
  • Saman Babaie-Kafaki
  • Vyacheslav Kungurtsev
    • Categories Bound-constrained Optimization, Constrained Nonlinear Optimization, Quadratic Programming Tags , , ,

    This paper discusses an improved quasi-Newton penalty decomposition algorithm for the cardinality bound-constrained optimization problems whose simple bounds on the variables are assumed to be finite. Until an approximate stationary point is found, this algorithm approximates the solutions of a sequence of penalty subproblems by a two-block decomposition scheme. This scheme finds an approximate solution … Read more