Out-of-the-Box Global Optimization for Packing Problems: New Models and Improved Solutions

  • Timo Berthold
  • Dominik Kamp
  • Gioni Mexi
  • Sebastian Pokutta
  • Imre Pólik
    • Categories Global Optimization, Nonlinear Optimization

    Recent LLM-driven discoveries have renewed interest in geometric packing problems. In this paper, we study several classes of such packing problems through the lens of modern global nonlinear optimization. Starting from comparatively direct nonlinear formulations, we consider packing circles in squares and fixed-perimeter rectangles, packing circles into minimum-area ellipses, packing regular polygons into regular polygons, … Read more

    A computational comparison of handling distance constraints in MINLP

  • Christopher Hojny
  • Leo Liberti
    • Categories (Mixed) Integer Nonlinear Programming Tags , , ,

    Minimum distance constraints (minDCs) appear in many geometric optimization problems. They pose major challenges for mixed-integer nonlinear programming (MINLP) due to their reverse-convexity. We develop new algorithms for tightening variable bounds in general MINLPs with minDCs. Because many such problems exhibit substantial symmetry, we further introduce a practical approach for handling rotation symmetries via separation … Read more

    Maximum Cuts and Fractional Cut Covers: A Computational Study of a Randomized Semidefinite Programming Approach

  • Nathan Benedetto Proença
  • Marcel K. de Carli Silva
  • Levent Tunçel
    • Categories Approximation Algorithms, Optimization Software and Modeling Systems, Semi-definite Programming

    We present experimental work on a primal-dual framework simultaneously approximating maximum cut and weighted fractional cut-covering instances. In this primal-dual framework, we solve a semidefinite programming (SDP) relaxation to either the maximum cut problem or to the weighted fractional cut-covering problem, and then independently sample a collection of cuts via the random-hyperplane technique. We then … Read more

    Finite-Sample Optimality and Constraint Satisfaction: Learning-Based Optimal Control in Dynamic Dispatch Networks

  • Moustafa Rashidy
    • Categories Data Science Theory, Production and Logistics, Transportation Tags , ,

    Dynamic dispatch networks in logistics and transportation require real-time, constraint-aware decision-making under stochastic demand. This paper bridges mathematical optimization, optimal control theory, and reinforcement learning by establishing non-asymptotic theoretical guarantees for learning-based optimal control in constrained stochastic dispatch systems. We formulate the problem as a constrained Markov decision process, enforce feasibility via a projection-based policy … Read more

    Second-Order Optimality Conditions for Bilevel Optimization Problems Using Parabolic Directional Derivatives

  • Bhuvnesh Khatana
    • Categories Complementarity and Variational Inequalities, Convex and Nonsmooth Optimization, Convex Optimization

    This paper studies the second-order properties of a class of inequality-constrained bilevel programming problems. First-order optimality conditions for the existence of solutions to bilevel optimization problems are derived using the first-order directional derivative of the optimal solution function of the lower-level problem in the seminal paper by Dempe (1992). In this work, we prove that … Read more

    Convergence of the Frank-Wolfe Algorithm for Monotone Variational Inequalities

  • Matthew Hough
    • Categories Complementarity and Variational Inequalities, Convex and Nonsmooth Optimization, Convex Optimization Tags , , ,

    We consider the Frank-Wolfe algorithm for solving variational inequalities over compact, convex sets under a monotone \(C^1\) operator and vanishing, nonsummable step sizes. We introduce a continuous-time interpolation of the discrete iteration and use tools from dynamical systems theory to analyze its asymptotic behavior. This allows us to derive convergence results for the original discrete … Read more

    Finding Short Paths on Simple Polytopes

  • Alexander Black
  • Raphael Steiner
    • Categories Combinatorial Optimization, Linear Programming, Polyhedra Tags , , , , ,

    We prove that computing a shortest monotone path to the optimum of a linear program over a simple polytope is NP-hard, thus resolving a 2022 open question of De Loera, Kafer, and Sanit\`{a}. As a consequence, finding a shortest sequence of pivots to an optimal basis with the simplex method is NP-hard. In fact, we … Read more

    Negative Momentum for Convex-Concave Optimization

  • Henry Shugart
  • Shuyi Wang
  • Jason M. Altschuler
    • Categories Convex Optimization

    This paper revisits momentum in the context of min-max optimization. Momentum is a celebrated mechanism for accelerating gradient dynamics in settings like convex minimization, but its direct use in min-max optimization makes gradient dynamics diverge. Surprisingly, Gidel et al. 2019 showed that negative momentum can help fix convergence. However, despite these promising initial results and … Read more

    A Nesterov-Accelerated Primal-Dual Splitting Algorithm for Convex Nonsmooth Optimization

  • Laurent Condat
  • Peter Richtarik
    • Categories Convex and Nonsmooth Optimization

    We investigate the integration of Nesterov-type acceleration into primal-dual methods for structured convex optimization. While proximal splitting algorithms efficiently handle composite problems of the form min_x f(x) + g(x) + h(Kx), accelerating their convergence with respect to the smooth term f is notoriously challenging due to the rotational dynamics in the primal-dual space. In this … Read more

    Benders Cut Filtering for Affine Potential-Based Flow Problems with Robustness Scenarios and Topology Switching

  • Tim Donkiewicz
  • Oliver Gaul
    • Categories (Mixed) Integer Linear Programming, Cutting Plane Approaches, Energy Tags , , , ,

    Many large-scale optimization problems decompose into a master problem and scenario subproblems, a structure that can be exploited by Benders decomposition. In Benders decomposition, each iteration may generate many cuts from scenario subproblems, and adding all of them as constraints then causes the master problem to grow rapidly. These are constraints that may need to … Read more