Optimization Software and Modeling Systems

ArcLP: A Matlab implementation of an O(√nL) arc-search infeasible interior-point algorithm for linear programming

Categories Linear Programming, Optimization Software and Modeling Systems Tags , ,

This paper presents a Matlab implementation of an arc-search infeasible interior point algorithm for linear programming (LP), which has a proven polynomial bound of O(√nL), the best among all interior-point algorithms for LP. Software architecture and major functions are discussed. Its ease of use is described by a simple example. Crucial strategies are summarized. Quality … Read more

Two Spectral Gaps: Decentralized Optimization over Intersections of Local Convex Sets

Categories Convex Optimization, Nonsmooth Optimization, Parallel Algorithms Tags , , , , ,

We study decentralized minimization of an average of strongly convex, smooth local objectives over an intersection of agent-private closed convex sets, where each agent knows only its own objective and its own set and agents communicate over a gossip network. We show that the complexity is controlled by a single geometric scalar, which we call … Read more

DD-suite: A cross-platform package to build Decision Diagrams for optimization purposes

Categories Dynamic Programming, Optimization Software and Modeling Systems, Optimization Software Design Principles Tags , , , ,

Decision diagrams (DDs) have become a powerful tool for discrete optimization, supporting a wide range of algorithms that span cut-generation procedures, decomposition methods, and specialized branch-and-bound searches. Despite this growth, their adoption remains limited, partly because most existing DD code is tailored to a specific algorithm or application and is therefore hard to reuse. We … Read more

A Domain-Specific Harness for End-to-End Automation of Optimization Research

Categories Convex Optimization, Nonlinear Optimization, Optimization Software and Modeling Systems Tags , , ,

We present AutoOPT, a domain-specific harness for end-to-end automation of optimization research. AutoOPT organizes the discovery of optimal first-order methods into four stages: numerical design through the BnB-PEP methodology; symbolic discovery of the analytic description and a convergence proof through frontier large language models (LLMs); formal verification in the Lean 4 proof assistant; and human … Read more

SDDmiP.jl: A Software Package with a Provably Convergent Benders Algorithm for Multi-Stage Stochastic Mixed-Integer Programming

Categories Optimization Software and Modeling Systems, Stochastic Programming Tags , , , , , ,

We present an open-source software package that implements a provably convergent Benders-type decomposition algorithm for multistage stochastic integer programs. In addition to standard cut families, such as Benders, strengthened Benders, and Lagrangian cuts, the algorithm incorporates rectified linear unit (ReLU) cuts, which provide convergence guarantees for general mixed-integer state variables. However, the dual problems used … Read more

pyoptexplain: A Python Library for Post-Optimality Analysis and Explanation of Optimization Models

Categories Optimization Software and Modeling Systems, Optimization Software Design Principles Tags , ,

Optimization models are built in a variety of modeling languages and solved by a variety of solvers, but once a solution exists, the information needed to understand it is fragmented: each solver exposes a partial, differently named set of native diagnostics, and the modeling language has already canonicalized the formulation the user wrote. We present … Read more

Random-Key Optimization for 2D Irregular Packing with Reusable Area Evaluation

Categories Applications - OR and Management Sciences, Meta Heuristics, Parallel Algorithms, Production and Logistics Tags , ,

The diverse constraints of industrial applications lead to variants of 2D irregular packing problems that require tailored solution methods. This paper addresses a real-world industrial challenge by proposing a new problem definition, the Maximum Reusable Contiguous Area Problem (MRCAP), and a novel metric, the Maximum Contiguous Area, developed to measure and maximize the contiguous unused … Read more

Parallel versions of the mesh adaptive direct search algorithm

Categories Nonlinear Optimization, Optimization Software and Modeling Systems, Parallel Algorithms Tags , , ,

This work surveys the different parallel variants of the mesh adaptive direct search (MADS) algorithm for constrained blackbox optimization. These problems can inherently imply high computational costs due to the possible large number of variables and multi-modality of the search space. In addition, the potential time-intensive nature and time heterogeneity of the blackboxes defining the … Read more

PyROS: The Pyomo Robust Optimization Solver

Categories Nonlinear Optimization, Optimization Software and Modeling Systems, Robust Optimization Tags , , , ,

We present PyROS, a Python-based meta-solver that automates a generalized cutting-set algorithm for the solution of nonconvex two-stage robust optimization (RO) problems with uncertain equality constraints. Freely available through the open-source optimization software package Pyomo, PyROS is designed to operate on a user-provided deterministic model and uncertainty set, such that a solution to the RO … Read more

Nested Benders Decomposition for Large-Scale Multi-Follower Bilevel Optimization

Categories Bilevel Optimization, Parallel Algorithms, Transportation Tags , , , ,

We propose a scalable nested Benders decomposition (BD) framework for single-leader, multi-follower bilevel optimization problems. The proposed framework is applicable to bilevel optimization problems in which each follower solves a linear program and is particularly well suited for instances involving a large number of followers. By identifying the upper-level decisions as complicating variables, the method … Read more