Tootfinder

On the Strength of Linear Relaxations in Ordered Optimization
V\'ictor Blanco, Diego Laborda, Miguel Mart\'inez-Ant\'on
https://arxiv.org/abs/2510.09166 https://

On the Strength of Linear Relaxations in Ordered Optimization
We study the conditions under which the convex relaxation of a mixed-integer linear programming formulation for ordered optimization problems, where sorting is part of the decision process, yields integral optimal solutions. Thereby solving the problem exactly in polynomial time. Our analysis identifies structural properties of the input data that influence the integrality of the relaxation. We show that incorporating ordered components introduces additional layers of combinatorial complexity t…

Quantum Alternating Direction Method of Multipliers for Semidefinite Programming
Hantao Nie, Dong An, Zaiwen Wen
https://arxiv.org/abs/2510.10056 https://a…

Quantum Alternating Direction Method of Multipliers for Semidefinite Programming
Semidefinite programming (SDP) is a fundamental convex optimization problem with wide-ranging applications. However, solving large-scale instances remains computationally challenging due to the high cost of solving linear systems and performing eigenvalue decompositions. In this paper, we present a quantum alternating direction method of multipliers (QADMM) for SDPs, building on recent advances in quantum computing. An inexact ADMM framework is developed, which tolerates errors in the iterates …

An $O(n\log n)$ Algorithm for Single-Item Capacitated Lot Sizing with a One-Breakpoint All-Units Discount and Non-Increasing Prices
Kleitos Papadopoulos
https://arxiv.org/abs/2510.11368

An $O(n\log n)$ Algorithm for Single-Item Capacitated Lot Sizing with a One-Breakpoint All-Units Discount and Non-Increasing Prices
This paper addresses the single-item capacitated lot sizing problem with a 1-breakpoint all-units quantity discount in a monotonic setting where the purchase prices are non-increasing over the planning horizon. For this case, we establish several novel properties of the optimal solution and develop a hybrid dynamic programming approach that maintains a compact representation of the solution space by storing only essential information about the states and using linear equations for intermediate …

Locally Linear Convergence for Nonsmooth Convex Optimization via Coupled Smoothing and Momentum
Reza Rahimi Baghbadorani, Sergio Grammatico, Peyman Mohajerin Esfahani
https://arxiv.org/abs/2511.10239 https://arxiv.org/pdf/2511.10239 https://arxiv.org/html/2511.10239
arXiv:2511.10239v1 Announce Type: new
Abstract: We propose an adaptive accelerated smoothing technique for a nonsmooth convex optimization problem where the smoothing update rule is coupled with the momentum parameter. We also extend the setting to the case where the objective function is the sum of two nonsmooth functions. With regard to convergence rate, we provide the global (optimal) sublinear convergence guarantees of O(1/k), which is known to be provably optimal for the studied class of functions, along with a local linear rate if the nonsmooth term fulfills a so-call locally strong convexity condition. We validate the performance of our algorithm on several problem classes, including regression with the l1-norm (the Lasso problem), sparse semidefinite programming (the MaxCut problem), Nuclear norm minimization with application in model free fault diagnosis, and l_1-regularized model predictive control to showcase the benefits of the coupling. An interesting observation is that although our global convergence result guarantees O(1/k) convergence, we consistently observe a practical transient convergence rate of O(1/k^2), followed by asymptotic linear convergence as anticipated by the theoretical result. This two-phase behavior can also be explained in view of the proposed smoothing rule.
toXiv_bot_toot

Reverse Supply Chain Network Design of a Polyurethane Waste Upcycling System
Dalga Merve \"Ozkan, Sergio Lucia, Sebastian Engell
https://arxiv.org/abs/2510.08097 https://…

Reverse Supply Chain Network Design of a Polyurethane Waste Upcycling System
This paper presents a general mathematical programming framework for the design and optimization of supply chain infrastructures for the upcycling of plastic waste. For this purpose, a multi-product, multi-echelon, multi-period mixed-integer linear programming (MILP) model has been formulated. The objective is to minimize the cost of the entire circular supply chain starting from the collection of post-consumer plastic waste to the production of virgin-equivalent high value polymers, satisfying…

AutoMLGen: Navigating Fine-Grained Optimization for Coding Agents
Shangheng Du, Xiangchao Yan, Dengyang Jiang, Jiakang Yuan, Yusong Hu, Xin Li, Liang He, Bo Zhang, Lei Bai
https://arxiv.org/abs/2510.08511

AutoMLGen: Navigating Fine-Grained Optimization for Coding Agents
Large language models (LLMs) have shown impressive performance in general programming tasks. However, in Machine Learning Engineering (MLE) scenarios such as AutoML and Kaggle competitions, achieving high performance depends heavily on expert intervention and repeated adjustments rather than simply generating correct code. When applied directly to these tasks, LLMs often lack fine-grained domain priors, and existing MLE approaches that use linear or tree-structured searches limit knowledge tran…

A Linear Programming Approach to Estimate the Core in Cooperative Games
J Camacho, JC Gon\c{c}alves-Dosantos, J S\'anchez-Soriano
https://arxiv.org/abs/2510.01766 https://…

A Linear Programming Approach to Estimate the Core in Cooperative Games
This paper proposes a novel algorithm to approximate the core of transferable utility (TU) cooperative games via linear programming. Given the computational hardness of determining the full core, our approach provides a tractable approximation by sampling extreme points through randomized linear problems (LPs). We analyze its convergence and computational complexity, and validate its effectiveness through extensive simulations on various game models. Our results show that the method is scalable…

Replaced article(s) found for cs.PL. https://arxiv.org/list/cs.PL/new
[1/1]:
- Weak-Linear Types
Hector Gramaglia
https://arxiv.org/abs/2402…

Verification of Sequential Convex Programming for Parametric Non-convex Optimization
Rajiv Sambharya, Nikolai Matni, George Pappas
https://arxiv.org/abs/2511.10622 https://arxiv.org/pdf/2511.10622 https://arxiv.org/html/2511.10622
arXiv:2511.10622v1 Announce Type: new
Abstract: We introduce a verification framework to exactly verify the worst-case performance of sequential convex programming (SCP) algorithms for parametric non-convex optimization. The verification problem is formulated as an optimization problem that maximizes a performance metric (e.g., the suboptimality after a given number of iterations) over parameters constrained to be in a parameter set and iterate sequences consistent with the SCP update rules. Our framework is general, extending the notion of SCP to include both conventional variants such as trust-region, convex-concave, and prox-linear methods, and algorithms that combine convex subproblems with rounding steps, as in relaxing and rounding schemes. Unlike existing analyses that may only provide local guarantees under limited conditions, our framework delivers global worst-case guarantees--quantifying how well an SCP algorithm performs across all problem instances in the specified family. Applications in control, signal processing, and operations research demonstrate that our framework provides, for the first time, global worst-case guarantees for SCP algorithms in the parametric setting.
toXiv_bot_toot

Geoffrion's theorem beyond finiteness and rationality
Santanu S. Dey, Fr\'ed\'eric Meunier, Diego Moran Ramirez
https://arxiv.org/abs/2510.10966 https://

Geoffrion's theorem beyond finiteness and rationality
Geoffrion's theorem is a fundamental result from mathematical programming assessing the quality of Lagrangian relaxation, a standard technique to get bounds for integer programs. An often implicit condition is that the set of feasible solutions is finite or described by rational linear constraints. However, we show through concrete examples that the conclusion of Geoffrion's theorem does not necessarily hold when this condition is dropped. We then provide sufficient conditions ensuring the vali…

PRISM-Physics: Causal DAG-Based Process Evaluation for Physics Reasoning
Wanjia Zhao, Qinwei Ma, Jingzhe Shi, Shirley Wu, Jiaqi Han, Yijia Xiao, Si-Yuan Chen, Xiao Luo, Ludwig Schmidt, James Zou
https://arxiv.org/abs/2510.03185

PRISM-Physics: Causal DAG-Based Process Evaluation for Physics Reasoning
Benchmarks for competition-style reasoning have advanced evaluation in mathematics and programming, yet physics remains comparatively explored. Most existing physics benchmarks evaluate only final answers, which fail to capture reasoning processes, while recent stepwise methods rely on heuristic LLM-as-judge scoring or restrictive linear assumptions, limiting reliability and diagnostic validity. We introduce PRISM-Physics, a process-level evaluation framework and benchmark for complex physics r…

Replaced article(s) found for math.OC. https://arxiv.org/list/math.OC/new
[1/1]:
- A robust BFGS algorithm for unconstrained nonlinear optimization problems
Yaguang Yang
https://arxiv.org/abs/1212.5929
- Quantum computing and the stable set problem
Alja\v{z} Krpan, Janez Povh, Dunja Pucher
https://arxiv.org/abs/2405.12845 https://mastoxiv.page/@arXiv_mathOC_bot/112483516437815686
- Mean Field Game with Reflected Jump Diffusion Dynamics: A Linear Programming Approach
Zongxia Liang, Xiang Yu, Keyu Zhang
https://arxiv.org/abs/2508.20388 https://mastoxiv.page/@arXiv_mathOC_bot/115111048711698998
- Differential Dynamic Programming for the Optimal Control Problem with an Ellipsoidal Target Set a...
Sungjun Eom, Gyunghoon Park
https://arxiv.org/abs/2509.07546 https://mastoxiv.page/@arXiv_mathOC_bot/115179281556444440
- On the Moreau envelope properties of weakly convex functions
Marien Renaud, Arthur Leclaire, Nicolas Papadakis
https://arxiv.org/abs/2509.13960 https://mastoxiv.page/@arXiv_mathOC_bot/115224514482363803
- Automated algorithm design via Nevanlinna-Pick interpolation
Ibrahim K. Ozaslan, Tryphon T. Georgiou, Mihailo R. Jovanovic
https://arxiv.org/abs/2509.21416 https://mastoxiv.page/@arXiv_mathOC_bot/115286533597711930
- Optimal Control of a Bioeconomic Crop-Energy System with Energy Reinvestment
Othman Cherkaoui Dekkaki
https://arxiv.org/abs/2510.11381 https://mastoxiv.page/@arXiv_mathOC_bot/115372322896073250
- Point Convergence Analysis of the Accelerated Gradient Method for Multiobjective Optimization: Co...
Yingdong Yin
https://arxiv.org/abs/2510.26382 https://mastoxiv.page/@arXiv_mathOC_bot/115468018035252078
- History-Aware Adaptive High-Order Tensor Regularization
Chang He, Bo Jiang, Yuntian Jiang, Chuwen Zhang, Shuzhong Zhang
https://arxiv.org/abs/2511.05788
- Equivalence of entropy solutions and gradient flows for pressureless 1D Euler systems
Jos\'e Antonio Carrillo, Sondre Tesdal Galtung
https://arxiv.org/abs/2312.04932 https://mastoxiv.page/@arXiv_mathAP_bot/111560077272113052
- Kernel Modelling of Fading Memory Systems
Yongkang Huo, Thomas Chaffey, Rodolphe Sepulchre
https://arxiv.org/abs/2403.11945 https://mastoxiv.page/@arXiv_eessSY_bot/112121123836064435
- The Maximum Theoretical Ground Speed of the Wheeled Vehicle
Altay Zhakatayev, Mukatai Nemerebayev
https://arxiv.org/abs/2502.15341 https://mastoxiv.page/@arXiv_physicsclassph_bot/114057765769441123
- Hessian stability and convergence rates for entropic and Sinkhorn potentials via semiconcavity
Giacomo Greco, Luca Tamanini
https://arxiv.org/abs/2504.11133 https://mastoxiv.page/@arXiv_mathPR_bot/114346453424694503
- Optimizing the ground state energy of the three-dimensional magnetic Dirichlet Laplacian with con...
Matthias Baur
https://arxiv.org/abs/2504.21597 https://mastoxiv.page/@arXiv_mathph_bot/114431404740241516
- A localized consensus-based sampling algorithm
Arne Bouillon, Alexander Bodard, Panagiotis Patrinos, Dirk Nuyens, Giovanni Samaey
https://arxiv.org/abs/2505.24861 https://mastoxiv.page/@arXiv_mathNA_bot/114612580684567066
- A Novel Sliced Fused Gromov-Wasserstein Distance
Moritz Piening, Robert Beinert
https://arxiv.org/abs/2508.02364 https://mastoxiv.page/@arXiv_csLG_bot/114976243138728278
- Minimal Regret Walras Equilibria for Combinatorial Markets via Duality, Integrality, and Sensitiv...
Alo\"is Duguet, Tobias Harks, Martin Schmidt, Julian Schwarz
https://arxiv.org/abs/2511.09021 https://mastoxiv.page/@arXiv_csGT_bot/115541243299714775
toXiv_bot_toot

Analysis of approximate linear programming solution to Markov decision problem with log barrier function
Donghwan Lee, Hyukjun Yang, Bum Geun Park
https://arxiv.org/abs/2509.19800

Analysis of approximate linear programming solution to Markov decision problem with log barrier function
There are two primary approaches to solving Markov decision problems (MDPs): dynamic programming based on the Bellman equation and linear programming (LP). Dynamic programming methods are the most widely used and form the foundation of both classical and modern reinforcement learning (RL). By contrast, LP-based methods have been less commonly employed, although they have recently gained attention in contexts such as offline RL. The relative underuse of the LP-based methods stems from the fact t…

Provably Optimal Quantum Circuits with Mixed-Integer Programming
Harsha Nagarajan, Zsolt Szab\'o
https://arxiv.org/abs/2510.00649 https://arxiv.org/pdf…

Provably Optimal Quantum Circuits with Mixed-Integer Programming
We present a depth-aware optimization framework for quantum circuit compilation that unifies provable optimality with scalable heuristics. For exact synthesis of a target unitary, we formulate a mixed-integer linear program (MILP) that linearly handles global-phase equivalence and uses explicit parallel scheduling variables to certify depth-optimal solutions for small-to-medium circuits. Domain-specific valid constraints, including identity ordering, commuting-gate pruning, short-sequence redun…

The Branch-and-Bound Tree Closure
Marius Roland, Nagisa Sugishita, Alexandre Forel, Youssouf Emine, Ricardo Fukasawa, Thibaut Vidal
https://arxiv.org/abs/2510.11497 https://

The Branch-and-Bound Tree Closure
This paper investigates the a-posteriori analysis of Branch-and-Bound~(BB) trees to extract structural information about the feasible region of mixed-binary linear programs. We introduce three novel outer approximations of the feasible region, systematically constructed from a BB tree. These are: a tight formulation based on disjunctive programming, a branching-based formulation derived from the tree's branching logic, and a mixing-set formulation derived from the on-off properties inside the t…

Analysis of approximate linear programming solution to Markov decision problem with log barrier function
Donghwan Lee, Hyukjun Yang, Bum Geun Park
https://arxiv.org/abs/2509.19800

Analysis of approximate linear programming solution to Markov decision problem with log barrier function
There are two primary approaches to solving Markov decision problems (MDPs): dynamic programming based on the Bellman equation and linear programming (LP). Dynamic programming methods are the most widely used and form the foundation of both classical and modern reinforcement learning (RL). By contrast, LP-based methods have been less commonly employed, although they have recently gained attention in contexts such as offline RL. The relative underuse of the LP-based methods stems from the fact t…

A Linear Programming Framework for Optimal Event-Triggered LQG Control
Zahra Hashemi, Dipankar Maity
https://arxiv.org/abs/2509.10671 https://arxiv.org/pdf…

A Linear Programming Framework for Optimal Event-Triggered LQG Control
This letter explores intelligent scheduling of sensor-to-controller communication in networked control systems, particularly when data transmission incurs a cost. While the optimal controller in a standard linear quadratic Gaussian (LQG) setup can be computed analytically, determining the optimal times to transmit sensor data remains computationally and analytically challenging. We show that, through reformulation and the introduction of auxiliary binary variables, the scheduling problem can be…

Replaced article(s) found for cs.PL. https://arxiv.org/list/cs.PL/new
[1/1]:
- A Two-Level Linear Dependent Type Theory
Qiancheng Fu, Hongwei Xi
https://

Beyond Revenue and Welfare: Counterfactual Analysis of Spectrum Auctions with Application to Canada's 3800MHz Allocation
Sara Jalili Shani, Kris Joseph, Michael B. McNally, James R. Wright
https://arxiv.org/abs/2512.08106 https://arxiv.org/pdf/2512.08106 https://arxiv.org/html/2512.08106
arXiv:2512.08106v1 Announce Type: new
Abstract: Spectrum auctions are the primary mechanism through which governments allocate scarce radio frequencies, with outcomes that shape competition, coverage, and innovation in telecommunications markets. While traditional models of spectrum auctions often rely on strong equilibrium assumptions, we take a more parsimonious approach by modeling bidders as myopic and straightforward: in each round, firms simply demand the bundle that maximizes their utility given current prices. Despite its simplicity, this model proves effective in predicting the outcomes of Canada's 2023 auction of 3800 MHz spectrum licenses. Using detailed round-by-round bidding data, we estimate bidders' valuations through a linear programming framework and validate that our model reproduces key features of the observed allocation and price evolution. We then use these estimated valuations to simulate a counterfactual auction under an alternative mechanism that incentivizes deployment in rural and remote regions, aligning with one of the key objectives set out in the Canadian Telecommunications Act. The results show that the proposed mechanism substantially improves population coverage in underserved areas. These findings demonstrate that a behavioral model with minimal assumptions is sufficient to generate reliable counterfactual predictions, making it a practical tool for policymakers to evaluate how alternative auction designs may influence future outcomes. In particular, our study demonstrates a method for counterfactual mechanism design, providing a framework to evaluate how alternative auction rules could advance policy goals such as equitable deployment across Canada.
toXiv_bot_toot

Nonlinear Model Predictive Control with Single-Shooting Method for Autonomous Personal Mobility Vehicle
Rakha Rahmadani Pratama, Catur Hilman A. H. B. Baskoro, Joga Dharma Setiawan, Dyah Kusuma Dewi, P Paryanto, Mochammad Ariyanto, Roni Permana Saputra
https://arxiv.org/abs/2509.22694

Nonlinear Model Predictive Control with Single-Shooting Method for Autonomous Personal Mobility Vehicle
This paper introduces a proposed control method for autonomous personal mobility vehicles, specifically the Single-passenger Electric Autonomous Transporter (SEATER), using Nonlinear Model Predictive Control (NMPC). The proposed method leverages a single-shooting approach to solve the optimal control problem (OCP) via non-linear programming (NLP). The proposed NMPC is implemented to a non-holonomic vehicle with a differential drive system, using odometry data as localization feedback to guide t…

Range of optimal values in absolute value linear programming with interval data
Milan Hlad\'ik
https://arxiv.org/abs/2510.04604 https://arxiv.org/pdf/2…

Range of optimal values in absolute value linear programming with interval data
Absolute value linear programming problems is quite a new area of optimization problems, involving linear functions and absolute values in the description of the model. In this paper, we consider interval uncertainty of the input coefficients. Our goal is to determine the best and the worst case optimal values. For the former, we derive an explicit formula, reducing the problem to a certain optimization problem. However, the latter is more complicated, and we propose a lower and upper bound app…

Short circuit walks in fixed dimension
Alexander E. Black, Christian N\"obel, Raphael Steiner
https://arxiv.org/abs/2510.01916 https://arxiv.org/pdf/2…

Short circuit walks in fixed dimension
Circuit augmentation schemes are a family of combinatorial algorithms for linear programming that generalize the simplex method. To solve the linear program, they construct a so-called monotone circuit walk: They start at an initial vertex of the feasible region and traverse a discrete sequence of points on the boundary, while moving along certain allowed directions (circuits) and improving the objective function at each step until reaching an optimum. Since the existence of short circuit walks…

Maximum augmented Zagreb index on polyomino chains
Manuel Montes-y-Morales, Sayl\'e Sigarreta, Hugo Cruz-Su\'arez
https://arxiv.org/abs/2509.10669 https://

Maximum augmented Zagreb index on polyomino chains
In this paper, we present a dynamic programming approach for identifying extremal polyomino chains with respect to degree-based topological indices. This approach provides an explicit recurrence and constructive algorithm that enables both the computation of an extremal polyomino chain in linear time with respect to its number of squares, and the enumeration of all maximal configurations in linear time with respect to their amount. As a main application, we resolve a problem posed in 2016 by ch…

Efficient Compilation of Algorithms into Compact Linear Programs
Shermin Khosravi, David Bremner
https://arxiv.org/abs/2509.13006 https://arxiv.org/pdf/250…

Efficient Compilation of Algorithms into Compact Linear Programs
Linear Programming (LP) is widely applied in industry and is a key component of various other mathematical problem-solving techniques. Recent work introduced an LP compiler translating polynomial-time, polynomial-space algorithms into polynomial-size LPs using intuitive high-level programming languages, offering a promising alternative to manually specifying each set of constraints through Algebraic Modeling Languages (AMLs). However, the resulting LPs, while polynomial in size, are often extre…

Virtual Arc Consistency for Linear Constraints inCost Function Networks
Pierre Montalbano, Simon de Givry, George Katsirelos
https://arxiv.org/abs/2509.17706 https://

Virtual Arc Consistency for Linear Constraints inCost Function Networks
In Constraint Programming, solving discrete minimization problems with hard and soft constraints can be done either using (i) soft global constraints, (ii) a reformulation into a linear program, or (iii) a reformulation into local cost functions. Approach (i) benefits from a vast catalog of constraints. Each soft constraint propagator communicates with other soft constraints only through the variable domains, resulting in weak lower bounds. Conversely, the approach (ii) provides a global view w…

Inverse Mixed-Integer Programming: Learning Constraints then Objective Functions
Akira Kitaoka
https://arxiv.org/abs/2510.04455 https://arxiv.org/pdf/2510.…

Inverse Mixed-Integer Programming: Learning Constraints then Objective Functions
In mixed-integer linear programming, data-driven inverse optimization that learns the objective function and the constraints from observed data plays an important role in constructing appropriate mathematical models for various fields, including power systems and scheduling. However, to the best of our knowledge, there is no known method for learning both the objective functions and the constraints. In this paper, we propose a two-stage method for a class of problems where the objective functio…

Replaced article(s) found for cs.PL. https://arxiv.org/list/cs.PL/new
[1/1]:
- Ranking Functions for Linear-Constraint Loops
Amir M. Ben-Amram, Samir Genaim
https:…

An Exhaustive DPLL Approach to Model Counting over Integer Linear Constraints with Simplification Techniques
Mingwei Zhang, Zhenhao Gu, Liangda Fang, Cunjing Ge, Ziliang Chen, Zhao-Rong Lai, Quanlong Guan
https://arxiv.org/abs/2509.13880

An Exhaustive DPLL Approach to Model Counting over Integer Linear Constraints with Simplification Techniques
Linear constraints are one of the most fundamental constraints in fields such as computer science, operations research and optimization. Many applications reduce to the task of model counting over integer linear constraints (MCILC). In this paper, we design an exact approach to MCILC based on an exhaustive DPLL architecture. To improve the efficiency, we integrate several effective simplification techniques from mixed integer programming into the architecture. We compare our approach to state-o…

EigenSafe: A Spectral Framework for Learning-Based Stochastic Safety Filtering
Inkyu Jang, Jonghae Park, Chams E. Mballo, Sihyun Cho, Claire J. Tomlin, H. Jin Kim
https://arxiv.org/abs/2509.17750

EigenSafe: A Spectral Framework for Learning-Based Stochastic Safety Filtering
We present EigenSafe, an operator-theoretic framework for learning-enabled safety-critical control for stochastic systems. In many robotic systems where dynamics are best modeled as stochastic systems due to factors such as sensing noise and environmental disturbances, it is challenging for conventional methods such as Hamilton-Jacobi reachability and control barrier functions to provide a holistic measure of safety. We derive a linear operator governing the dynamic programming principle for sa…

Introducing Clause Cuts: Strong No-Good Cuts for MaxSAT Problems in Mixed Integer Linear Programming
Max Engelhardt, Milan Adhikari, Jonasz Staszek, Alexander Martin
https://arxiv.org/abs/2509.21687

Introducing Clause Cuts: Strong No-Good Cuts for MaxSAT Problems in Mixed Integer Linear Programming
In this paper we introduce Clause Cuts: linear inequalities obtained from clauses that are logically implied by a CNF formula, resembling strengthened no-good cuts. With these cuts, we tighten mixed-integer linear programming (MILP) formulations of random weighted partial MaxSAT problems, which have remained particularly challenging for core-guided complete MaxSAT solvers. Our approaches treat variables that attain integral values at the LP relaxation as partial assignments which are supplied t…

On the System Theoretic Offline Learning of Continuous-Time LQR with Exogenous Disturbances
Sayak Mukherjee, Ramij R. Hossain, Mahantesh Halappanavar
https://arxiv.org/abs/2509.16746

On the System Theoretic Offline Learning of Continuous-Time LQR with Exogenous Disturbances
We analyze offline designs of linear quadratic regulator (LQR) strategies with uncertain disturbances. First, we consider the scenario where the exogenous variable can be estimated in a controlled environment, and subsequently, consider a more practical and challenging scenario where it is unknown in a stochastic setting. Our approach builds on the fundamental learning-based framework of adaptive dynamic programming (ADP), combined with a Lyapunov-based analytical methodology to design the algo…

The Bin Packing Problem with Setups: Formulation, Structural Properties and Computational Insights
Roberto Baldacci, Fabio Ciccarelli, Stefano Conglio, Valerio Dose, Fabio Furini
https://arxiv.org/abs/2509.10075

The Bin Packing Problem with Setups: Formulation, Structural Properties and Computational Insights
We introduce and study a novel generalization of the classical Bin Packing Problem (BPP), called the Bin Packing Problem with Setups (BPPS). In this problem, which has many practical applications in production planning and logistics, the items are partitioned into classes and, whenever an item from a given class is packed into a bin, a setup weight and cost are incurred. We present a natural Integer Linear Programming (ILP) formulation for the BPPS and analyze the structural properties of its L…

Pareto-Optimal Linear Programming
Bart van Rossum, Twan Dollevoet
https://arxiv.org/abs/2509.18073 https://arxiv.org/pdf/2509.18073

Pareto-Optimal Linear Programming
Pareto-optimality plays a central role in evaluating the efficiency of solutions to allocation problems, such as house allocation, school choice, and kidney exchange. We introduce a general linear programming problem subject to Pareto-optimality conditions, which we call Max-Pareto. Using the novel result that Pareto-optimal bipartite matchings are fractionally Pareto-optimal, we prove that Max-Pareto is $\mathcal{NP}$-complete. We propose a bilinear programming formulation of Max-Pareto, and e…

The Non-Attainment Phenomenon in Robust SOCPs
Vinh Nguyen
https://arxiv.org/abs/2510.00318 https://arxiv.org/pdf/2510.00318

The Non-Attainment Phenomenon in Robust SOCPs
A fundamental theorem of linear programming states that a feasible linear program is solvable if and only if its objective function is copositive with respect to the recession cone of its feasible set. This paper demonstrates that this crucial guarantee does not extend to Second-Order Cone Programs (SOCPs), a workhorse model in robust and convex optimization. We construct and analyze a rigorous counterexample derived from a robust linear optimization problem with ellipsoidal uncertainty. The re…

Differential Privacy for Euclidean Jordan Algebra with Applications to Private Symmetric Cone Programming
Zhao Song, Jianfei Xue, Lichen Zhang
https://arxiv.org/abs/2509.16915 h…

Differential Privacy for Euclidean Jordan Algebra with Applications to Private Symmetric Cone Programming
In this paper, we study differentially private mechanisms for functions whose outputs lie in a Euclidean Jordan algebra. Euclidean Jordan algebras capture many important mathematical structures and form the foundation of linear programming, second-order cone programming, and semidefinite programming. Our main contribution is a generic Gaussian mechanism for such functions, with sensitivity measured in $\ell_2$, $\ell_1$, and $\ell_\infty$ norms. Notably, this framework includes the important ca…

Q-Linear Convergence of the Proximal Augmented Lagrangian Method for Non-Convex Conic Programming
Ning Zhang, Yi Zhang
https://arxiv.org/abs/2509.11531 https://

Q-Linear Convergence of the Proximal Augmented Lagrangian Method for Non-Convex Conic Programming
This paper provides a local convergence analysis of the proximal augmented Lagrangian method (PALM) applied to a class of non-convex conic programming problems. Previous convergence results for PALM typically imposed assumptions such as constraint non-degeneracy, strict complementarity, second-order sufficiency conditions, or a combination of constraint nondegeneracy with strong second-order sufficiency conditions. In contrast, our work demonstrates a Q-linear convergence rate for an inexact ve…

Heuristic Bundle Upper Bound Based Polyhedral Bundle Method for Semidefinite Programming
Zilong Cui, Ran Gu
https://arxiv.org/abs/2510.12374 https://arxiv.…

Heuristic Bundle Upper Bound Based Polyhedral Bundle Method for Semidefinite Programming
Semidefinite programming (SDP) is a fundamental class of convex optimization problems with diverse applications in mathematics, engineering, machine learning, and related disciplines. This paper investigates the application of the polyhedral bundle method to standard SDPs. The basic idea of this method is to approximate semidefinite constraints using linear constraints, and thereby transform the SDP problem into a series of quadratic programming subproblems. However, the number of linear constr…

Global Optimization Algorithm for Mixed-Integer Nonlinear Programs with Trigonometric Functions
Christopher Montez, Sujeevraja Sanjeevi, Kaarthik Sundar
https://arxiv.org/abs/2509.26516

Global Optimization Algorithm for Mixed-Integer Nonlinear Programs with Trigonometric Functions
This article presents the first mixed-integer linear programming (MILP)-based iterative algorithm to solve factorable mixed-integer nonlinear programs (MINLPs) with bounded, differentiable periodic functions to global optimality with an emphasis on trigonometric functions. At each iteration, the algorithm solves a MILP relaxation of the original MINLP to obtain a bound on the optimal objective value. The relaxations are constructed using partitions of variables involved in each nonlinear term a…

A Multiobjective Mathematical Model for Optimal Irrigation Water Allocation
Nahid Sultana, M. M. Rizvi, G. M. Wali Ullah
https://arxiv.org/abs/2509.19629 https://

A Multiobjective Mathematical Model for Optimal Irrigation Water Allocation
Water resource management is vital for sustainable irrigation and food security under growing climatic and economic pressures. In this study, we develop two single-objective optimization models for irrigation planning, one that maximizes net benefit and the other that minimizes environmental flow deficiency, and benchmark them against previous works. We then extend the analysis to a multiobjective linear programming formulation solved through different approaches to evaluate trade-offs. Numeric…

Computing all Nash equilibria of low-rank bi-matrix games
Zachary Feinstein, Andreas L\"ohne, Birgit Rudloff
https://arxiv.org/abs/2509.11718 https://…

Computing all Nash equilibria of low-rank bi-matrix games
We study constrained bi-matrix games, with a particular focus on low-rank games. Our main contribution is a framework that reduces low-rank games to smaller, equivalent constrained games, along with a necessary and sufficient condition for when such reductions exist. Building on this framework, we present three approaches for computing the set of extremal Nash equilibria, based on vertex enumeration, polyhedral calculus, and vector linear programming. Numerical case studies demonstrate the effe…

Optimal Solutions to Deflect Earth Crossing Objects Using Laser
Vivek Verma, Shribharath B., Mangal Kothari
https://arxiv.org/abs/2509.12033 https://arxiv.…

Optimal Solutions to Deflect Earth Crossing Objects Using Laser
This paper solves and analyzes a trajectory optimization problem to deflect Earth-crossing objects (ECOs) employing continuous thrust obtained using a laser ablative system. The optimal control is determined for various initial ECO-Earth configurations to achieve the desired miss distance. The formulation incorporates the gravitational effect on the object due to the Earth using the patched-conic method. The constrained trajectory optimization problem is solved using Non-Linear Programming (NLP…