Bi-Parameterized Two-Stage Stochastic Min-Max and Min-Min Mixed Integer Programs

  • Sumin Kang
  • Manish Bansal
    • Categories Integer Programming, Network Optimization, Stochastic Programming Tags , , , ,

    We introduce two-stage stochastic min-max and min-min integer programs with bi-parameterized recourse (BTSPs), where the first-stage decisions affect both the objective function and the feasible region of the second-stage problem. To solve these programs efficiently, we introduce Lagrangian-integrated L-shaped (\(L^2\)) methods, which guarantee exact solutions when the first-stage decisions are pure binary. For mixed-binary first-stage … Read more

    High-Probability Polynomial-Time Complexity of Restarted PDHG for Linear Programming

  • Zikai Xiong
    • Categories Linear Programming Tags , , ,

    The restarted primal-dual hybrid gradient method (rPDHG) is a first-order method that has recently received significant attention for its computational effectiveness in solving linear program (LP) problems. Despite its impressive practical performance, the theoretical iteration bounds for rPDHG can be exponentially poor. To shrink this gap between theory and practice, we show that rPDHG achieves … Read more

    Proximity results in convex mixed-integer programming

  • Burak Kocuk
  • Diego Moran Ramirez
    • Categories (Mixed) Integer Linear Programming, (Mixed) Integer Nonlinear Programming, Cone Programming Tags , , , ,

    We study proximity (resp. integrality gap), that is, the distance (resp. difference) between the optimal solutions (resp. optimal values) of convex integer programs (IP) and the optimal solutions (resp. optimal values) of their continuous relaxations. We show that these values can be upper bounded in terms of the recession cone of the feasible region of … Read more

    Insights into the computational complexity of the single-source capacitated facility location problem with customer preferences

  • Christina Büsing
  • Timo Gersing
  • Sophia Wrede
    • Categories Combinatorial Optimization Tags , , ,

    Single-source capacitated facility location problems (SSCFLPs) are well known in the operations research literature. A set of facilities is opened and each customer is assigned to exactly one open facility so that the capacity at each facility is respected. This customer assignment, however, deprives customers from choosing facilities according to their individual preferences. If customers … Read more

    Two-Stage Distributionally Robust Optimization: Intuitive Understanding and Algorithm Development from the Primal Perspective

  • Zhengsong Lu
  • Bo Zeng
    • Categories Robust Optimization, Semi-infinite Programming Tags , ,

    In this paper, we study the two-stage distributionally robust optimization (DRO) problem from the primal perspective. Unlike existing approaches, this perspective allows us to build a deeper and more intuitive understanding on DRO, to leverage classical and well established solution methods and to develop a general and fast decomposition algorithm (and its variants), and to … Read more

    The Edge-based Contiguous p-median Problem with Connections to Logistics Districting

  • Zeyad Kassem
  • Adolfo Escobedo
    • Categories Applications - OR and Management Sciences, Branch and Cut Algorithms, Cutting Plane Approaches Tags , , , ,

    This paper introduces the edge-based contiguous p-median (ECpM) problem to partition the roads in a network into a given number of compact and contiguous territories. Two binary programming models are introduced, both of which incorporate a network distance. The first model requires an exponential number of cut set-based constraints to model contiguity; it is paired … Read more

    Solving Multi-Follower Mixed-Integer Bilevel Problems with Binary Linking Variables

  • Vladimir Stadnichuk
  • Arie M.C.A. Koster
    • Categories (Mixed) Integer Linear Programming, Cutting Plane Approaches, Network Optimization Tags , , , ,

    We study multi-follower bilevel optimization problems with binary linking variables where the second level consists of many independent integer-constrained subproblems. This problem class not only generalizes many classical interdiction problems but also arises naturally in many network design problems where the second-level subproblems involve complex routing decisions of the actors involved. We propose a novel … Read more

    Multiple Kernel Learning-Aided Column-and-Constraint Generation Method

  • Biao Han
    • Categories Applications - OR and Management Sciences, Optimization in Data Science, Robust Optimization Tags , , , ,

    Two-stage robust optimization (two-stage RO), due to its ability to balance robustness and flexibility, has been widely used in various fields for decision-making under uncertainty. This paper proposes a multiple kernel learning (MKL)-aided column-and-constraint generation (CCG) method to address this issue in the context of data-driven decision optimization, and releases a corresponding registered Julia package, … Read more

    Primal-dual proximal bundle and conditional gradient methods for convex problems

  • Jiaming Liang
    • Categories Convex and Nonsmooth Optimization, Convex Optimization, Nonsmooth Optimization Tags , , , , ,

    This paper studies the primal-dual convergence and iteration-complexity of proximal bundle methods for solving nonsmooth problems with convex structures. More specifically, we develop a family of primal-dual proximal bundle methods for solving convex nonsmooth composite optimization problems and establish the iteration-complexity in terms of a primal-dual gap. We also propose a class of proximal bundle … Read more

    New Nonlinear Conjugate Gradient Methods with Guaranteed Descent for Multi-Objective Optimization

  • Manuel Berkemeier
    • Categories Multi-Criteria Optimization, Nonlinear Optimization, Unconstrained Optimization Tags , , , ,

    In this article, we present several examples of special nonlinear conjugate gradient directions for nonlinear (non-convex) multi-objective optimization. These directions provide a descent direction for the objectives, independent of the line-search. This way, we can provide an algorithm with simple, Armijo-like backtracking and prove convergence to first-order critical points. In contrast to other popular conjugate … Read more