Preconditioned subgradient method for composite optimization: overparameterization and fast convergence

  • Liwei Jiang
    • Categories Nonlinear Optimization, Nonsmooth Optimization, Optimization in Data Science Tags , , , ,

    Composite optimization problems involve minimizing the composition of a smooth map with a convex function. Such objectives arise in numerous data science and signal processing applications, including phase retrieval, blind deconvolution, and collaborative filtering. The subgradient method achieves local linear convergence when the composite loss is well-conditioned. However, if the smooth map is, in a … Read more

    Machine Learning Algorithms for Assisting Solvers for Constraint Satisfaction Problems

  • Morteza Kimiaei
  • Vyacheslav Kungurtsev
    • Categories Applications - OR and Management Sciences, Combinatorial Optimization, Optimization in Data Science Tags , , , , , , , , , ,

    This survey proposes a unifying conceptual framework and taxonomy that systematically integrates Machine Learning (ML) and Reinforcement Learning (RL) with classical paradigms for Constraint Satisfaction and Boolean Satisfiability solving. Unlike prior reviews that focus on individual applications, we organize the literature around solver architecture, linking each major phase—constraint propagation, heuristic decision-making, conflict analysis, and meta-level … Read more

    Machine Learning Algorithms for Assisting Solvers for Decision Optimization Problems

  • Morteza Kimiaei
  • Vyacheslav Kungurtsev
    • Categories Applications - OR and Management Sciences, Integer Programming, Optimization in Data Science Tags , , , , , , , ,

    Combinatorial decision problems lie at the intersection of Operations Research (OR) and Artificial Intelligence (AI), encompassing structured optimization tasks such as submodular selection, dynamic programming, planning, and scheduling. These problems exhibit exponential growth in decision complexity, driven by interdependent choices coupled through logical, temporal, and resource constraints.  Classical optimization frameworks—including integer programming, submodular optimization, and … Read more

    Branch and price for nonlinear production-maintenance scheduling in complex machinery

  • João Dionísio
  • Ambros Gleixner
  • João Pedro Pedroso
  • Ksenia Bestuzheva
    • Categories (Mixed) Integer Nonlinear Programming, Production and Logistics, Scheduling Tags , , , ,

    This paper proposes a mixed-integer nonlinear programming approach for joint scheduling of long-term maintenance decisions and short-term production for groups of complex machines with multiple interacting components. We introduce an abstract model where the production and the condition of machines are described by convex functions, allowing the model to be employed for various application areas … Read more

    Integrated Planning of Drone-Based Disaster Relief: Facility Location, Inventory Prepositioning, and Fleet Operations under Uncertainty

  • Yuyang Ma
  • Karmel S. Shehadeh
  • Man Yiu Tsang
    • Categories Robust Optimization, Transportation

    We introduce a two-stage robust optimization (RO) framework for the integrated planning of a drone-based disaster relief operations problem (DDROP). Given sets of demand points, candidate locations for establishing drone-supported relief facilities, facility types, drone types, and relief items types, our first-stage problem solves the following problems simultaneously: (i) a location problem that determines the … Read more

    Stronger cuts for Benders’ decomposition for stochastic Unit Commitment Problems based on interval variables

  • Azema
  • Vincent Leclère
  • Wim van Ackooij
    • Categories (Mixed) Integer Linear Programming, Energy, Stochastic Programming Tags , ,

    The Stochastic Unit Commitment (SUC) problem models the scheduling of power generation units under uncertainty, typically using a two-stage stochastic program with integer first-stage and continuous second-stage variables. We propose a new Benders decomposition approach that leverages an extended formulation based on interval variables, enabling decomposition by both unit and time interval under mild technical … Read more

    Towards a geometric characterization of unbounded integer cubic optimization problems via thin rays

  • Alberto Del Pia
    • Categories (Mixed) Integer Nonlinear Programming

    We study geometric characterizations of unbounded integer polynomial optimization problems. While unboundedness along a ray fully characterizes unbounded integer linear and quadratic optimization problems, we show that this is not the case for cubic polynomials. To overcome this, we introduce thin rays, which are rays with an arbitrarily small neighborhood, and prove that they characterize … Read more

    Projection-width as a structural parameter for discrete separable optimization

  • Alberto Del Pia
    • Categories (Mixed) Integer Linear Programming, (Mixed) Integer Nonlinear Programming, 0-1 Programming

    While several classes of integer linear optimization problems are known to be solvable in polynomial time, far fewer tractability results exist for integer nonlinear optimization. In this work, we narrow this gap by identifying a broad class of discrete nonlinear optimization problems that admit polynomial-time algorithms. Central to our approach is the notion of projection-width, … Read more

    Branch-and-Cut for Computing Approximate Equilibria of Mixed-Integer Generalized Nash Games

  • Alois Duguet
  • Tobias Harks
  • Martin Schmidt
  • Julian Schwarz
    • Categories (Mixed) Integer Nonlinear Programming, Branch and Cut Algorithms, Game Theory Tags , , , ,

    Generalized Nash equilibrium problems with mixed-integer variables constitute an important class of games in which each player solves a mixed-integer optimization problem, where both the objective and the feasible set is parameterized by the rivals’ strategies. However, such games are known for failing to admit exact equilibria and also the assumption of all players being … Read more

    Lyapunov-based Analysis on First Order Method for Composite Strong-Weak Convex Functions

  • Milan Barik
  • Suvendu Ranjan Pattanaik
    • Categories Convex Optimization, Nonsmooth Optimization, Unconstrained Optimization Tags , , , , ,

    The Nesterov’s accelerated gradient (NAG) method generalizes the classical gradient descent algorithm by improving the convergence rate from $\mathcal{O}\left(\frac{1}{t}\right)$ to $\mathcal{O}\left(\frac{1}{t^2}\right)$ in convex optimization. This study examines the proximal gradient framework for additively separable composite functions with smooth and non-smooth components. We demonstrate that Nesterov’s accelerated proximal gradient (NAPG$_\alpha$) method attains a convergence rate of … Read more