CS Paper Radar

Solution Methods for Infinite-Dimensional Generalized Disjunctive Programming

Daniel Nguyen, Joshua L. Pulsipher

eess.SY math.OC ·submitted 2026-08-27 20:51 UTC · v1

Abstract

Generalized disjunctive programming (GDP) expresses mixed discrete-continuous decisions through Boolean indicators and disjunctions, and can be systematically solved via a library of methods proposed in the literature. The recent InfiniteGDP abstraction lifts this modeling layer to continuous domains such as time, space, and uncertainty, but only the big-M and hull reformulations, the two endpoints of the relaxation spectrum, have been generalized to the infinite setting. This work closes this gap by generalizing four other GDP solution methods to infinite-dimensional optimization: the multiple big-M reformulation, P-split reformulation, cutting plane reformulation, and the logic-based outer approximation algorithm. It further proposes MBM-GP, a novel Gaussian-process variant of multiple big-M that learns the big-M function over the infinite domain from a small subset of the subproblem solves. Moreover, these approaches are implemented in the Julia package InfiniteDisjunctiveProgramming.jl. The methods are benchmarked on case studies arising in dynamic and stochastic optimization. The results demonstrate how the generalized solution methods can outperform big-M and hull, with MBM-GP retaining the tightness of multiple big-M at a fraction of its reformulation cost.

Closest papers

Nearest neighbours by meaning across the whole index.

Task-Aware Discretization of Differentiable Logic Gate Networks

cs.LG cs.LO ·2026-09-27 ·Thore Gerlach
similarity 0.55
Abstract

Differentiable logic gate networks (DLGNs) enable gradient-based training of highly efficient Boolean networks by relaxing discrete logic gates during training and discretizing them for inference. Standard approaches make this discretization decision locally, typically through argmax selection and confidence- or entropy-based convergence criteria. We show that local discretization can be task-suboptimal even for globally optimal relaxed solutions, with high gate confidence providing no general guarantee, and derive bounds relating task-aware gate selection to tractable interventions in the relaxed network. Motivated by these results, we study first-order downstream task information for progressive discretization and characterize when this local approximation is reliable. Experiments on convolutional DLGNs reveal a strong locality dependence: first-order scores become unreliable when directly optimized over nonlocal interventions, but accurately assess local argmax decisions for progressive freezing.

0.20

Constrained Graph Diffusion for Mixed Integer Optimization

cs.LG ·2026-08-13 ·Vincenzo Di Vito, Yusuf Guven, Babak Badnava, Deepjyoti Deka, Kaarthik Sundar +1 more
similarity 0.55
Abstract

This paper proposes a novel learning-based approach to approximately solve instances of mixed-integer optimization problems. These problems are computationally challenging, as they require jointly determining discrete and continuous decisions while satisfying complex combinatorial constraints. problem-agnostic and can accommodate a broad class of mixed-integer optimization problems through suitable projection operators. We introduce Constrained Graph Diffusion (CGD), a learning-based framework that approximately solves recurring instances of such problems by learning a conditional distribution over their discrete decisions. CGD uses a graph-based diffusion model and incorporates constraint information directly into the reverse diffusion process, steering intermediate predictions toward the feasible region throughout generation. By operating on continuous relaxations of the discrete variables, CGD defines a differentiable constrained generation pathway up to terminal discrete recovery. Once the discrete decision is recovered and fixed, a numerical optimizer solves the remaining continuous problem, avoiding online combinatorial search over the binary variables while retaining numerical optimization for continuous completion. We evaluate CGD on AC-OPF with branch switching and discrete portfolio optimization, demonstrating substantial improvements in feasibility and solution quality over learning-based baselines while achieving speedups of up to $543\times$ over state-of-the-art MIP solvers on large instances.

0.04

Decision-Focused Learning in MDPs: An Occupancy Measure Approach

cs.LG ·2026-10-06 ·Zihao Zhao, Ashwath K. Karunakaram, Ali Eshragh, Yuexing Li, Kai Wang
top venuecode/data similarity 0.53
Abstract · Accepted at NeurIPS 2026

In this work, we consider decision-focused learning (DFL) for a Markov decision process (MDP), where existing methods differentiate through the KKT conditions of the Bellman equation and require solving a linear system over all state-action pairs, limiting its scalability. We address this by reformulating the MDP as an occupancy measure-based linear program (LP), whose feasible region is induced by predicted dynamics, and we derive a closed-form gradient by identifying the active constraints in the feasible polyhedron via the pivoting algorithm. This occupancy measure-based LP layer raises two challenges: (1) LP's solution gradient is discontinuous when active constraints change, and (2) the LP backward cost still scales with the state size, which is costly for large or continuous state spaces. We address the challenges with an augmented Lagrangian surrogate and smooth the boundary jumps by random row sketching of the constraints, and a learnable soft state-aggregation layer and its function-approximation generalization that scales the LP to large finite and continuous-state MDPs. Across multiple tasks, our methods reach lower regret than KKT-based DFL and two-stage baselines with significantly lower computation cost. The source code for all experiments is available at https://github.com/A-Eshragh/State_Aggregation_Project.

0.45

Learning to Design Convex Relaxations for Nonconvex Optimization

cs.LG cs.MS ·2026-10-12 ·Jinrun Liu, Bai Yan, Tengfei Liu, Qunfeng Liu, Jian Yang +3 more
benchmarktheorycode/data similarity 0.53
Abstract

Convex relaxations make nonconvex optimization tractable by replacing hard nonconvex problems with convex surrogates that give valid bounds. Yet their design is still largely manual: a human expert must decide where to relax, which relaxation to use, and how much formulation growth is worth paying. We show that this design process can be learned. The method proposed in this paper, AutoConvexRelax, represents the symbolic formulation of a nonconvex problem as a tripartite graph linking variables, symbolic terms, and their objective or constraint positions. It then learns a policy that composes symbolic rewrites into problem-specific relaxation trajectories as the formulation evolves. We prove that finite action sequences generated by the learned policy preserve relaxation validity under explicit domain, occurrence-context, and representation-consistency conditions. We further establish computable error bounds for mixed relaxations and sufficient conditions for feasible recovery and global-optimality certification. As a first instantiation, we apply the method to nonconvex quadratic problems and fractional problems. On 241 benchmark quadratic instances, the learned policy strengthens McCormick lower bounds by 13.52%. Its mean lower bound is 3.70% below strengthened semidefinite relaxations on the normalized comparison metric, while it uses substantially smaller formulations. The learned policy retains this trade-off on fractional instances and reaches near-semidefinite bounds on beamforming and sensor-network localization instances. These results suggest that convex relaxation design can move from a fixed handcrafted choice to an automated learning process that adapts to problem structures. Code is available at https://github.com/auto4opt/AutoConvexRelax.

0.38

Approximate Dynamic Programming with Basis Function Learning

cs.LG ·2026-11-18 ·Mohammadreza Fathi, Chi-Guhn Lee
similarity 0.52
Abstract

This work presents a novel approach for approximating the value function in Markov decision processes (MDPs). Our approach is grounded in the approximate linear programming (ALP) framework, wherein basis functions (BFs) play an important role. Traditionally, BFs have been pre-defined, randomly generated, or restricted to specific structures, which both limits the accuracy that can be achieved and leaves no mechanism for improving a given approximation. We instead learn BFs from the model itself, by repeatedly applying the Bellman operator to the current value estimate. We introduce the Bellman operator basis function (BOBF) learning method, and prove that each learned BF improves the approximation by a quantifiable amount and that the method converges to the optimal value function. Its shrunken counterpart (SBOBF) retains this guarantee while capping the number of BFs, and therefore the computational effort per iteration. For large-scale problems, where the number of constraints is prohibitive, we develop hybrid variants (HBOBF and SHBOBF) that combine constraint sampling with BF learning, and we show that the improvement and finite-termination guarantees are preserved under explicitly stated conditions. Numerical experiments on (continuous) perishable inventory and queueing control problems demonstrate that our BF learning techniques significantly outperform existing methods in the literature.

0.12

Belief Space Planning for Risk Signal Temporal Logic via Mixed-Integer Convex Programming

cs.RO ·2026-10-12 ·Shaohang Han, Joris Verhagen, Kaier Liang, Jana Tumova
theory similarity 0.52
Abstract

Signal Temporal Logic (STL) specifies robot tasks with spatio-temporal requirements, and its robustness semantics allow planning by trajectory optimization. In practice, robots estimate their state from noisy measurements, and when the information gained from a measurement depends on the state, the robot can actively reduce its uncertainty by planning in the belief space. The resulting problem is, however, generally non-convex, for which gradient-based methods are neither complete nor globally optimal. In this paper, we consider Risk STL (RiSTL) planning in Gaussian belief space and show that an information-form parameterization of the belief, together with a convex relaxation of the belief dynamics, yields a mixed-integer convex program (MICP). We prove that the MICP is sound and complete, and that the relaxation preserves the globally optimal input trajectories. We validate the effectiveness of our method in numerical simulations.

0.21

Approximating the Chvátal--Gomory Closure of Capacity-Bounded Min-Closed Systems

cs.DS ·2026-09-28 ·Stefano Huber, Monaldo Mastrolilli
publishedtheory similarity 0.52
Abstract · 19 pages, a short version of this paper appears in the proceedings of ISAAC 2026

Optimizing over the {0, 1/2} rank-1 Chvàtal-Gomory (CG) closure of a binary integer linear program is NP-hard. While polynomial-time approximation schemes (PTAS) are established for monotone packing and covering formulations, extending these guarantees to mixed-sign variants remains an open challenge. In this paper, we study the approximability of the CG closure for k-slack bounded (capacity-bounded) min-closed systems, a generalized packing formulation with mixed-sign constraints that extends weighted Boolean Horn logic. In these systems, a constant upper bound $k \ge 1$ bounds the ratio between the negative penalty coefficient $q$ and the right-hand side capacity $b$ of every constraint, enforcing $q \le k \cdot b$. We prove that a constant-degree sum-of-squares relaxation yields a PTAS for maximizing linear objectives over the first CG closure generated by multipliers in $\{0\}\cup[\tfrac1f,1]$, for any constant integer $f \ge 2$. This closure is contained in the {0, 1/2} rank-1 CG closure.Optimizing over the {0, 1/2} rank-1 CG closure of a binary integer linear program is NP-hard. While PTASes are established for monotone packing and covering formulations, extending these guarantees to mixed-sign variants remains an open challenge. In this paper, we study the approximability of the CG closure for \emph{$k$-slack bounded (capacity-bounded) min-closed systems}, a generalized packing formulation with mixed-sign constraints that extends weighted Boolean Horn logic. In these systems, a constant upper bound $k \ge 1$ bounds the ratio between the negative penalty coefficient $q$ and the right-hand side capacity $b$ of every constraint, enforcing $q \le k \cdot b$. We prove that a constant-degree sum-of-squares relaxation yields a PTAS for maximizing linear objectives over the first CG closure generated by multipliers in $\{0\}\cup[\tfrac1f,1]$, for any constant integer $f \ge 2$.

0.61

Certified Scalable Enclosures for Uncertain Underdetermined Systems

eess.SY q-bio.QM ·2026-10-08 ·Rudra Prakash, Shaunak Sen
unusual similarity 0.51
Abstract · 18 pages, 1 figure (2 panels), 1 table

The central challenge in underdetermined models with bounded uncertainty, such as in nonlinear design and estimation, is certifying the solution sets. Conventional solution methodologies, such as those based on Newton's method or on sampling-based uncertainty quantification, are either not applicable due to the underdetermined nature or do not give guarantees that all solutions have been found, assuming they converge. We addressed this issue for a problem that arises in nonlinear design, where a target steady-state box is prescribed and the parameters have to be found. We developed a trapezoidal linearisation method that rigorously encloses all solutions and combined it with a tractable linear programming method to compute the component-wise bounds. We showed that the resulting families of linear programs can iteratively contract an initial parameter region. A subdivision of the target state and the initial parameter region can improve the contraction and provide tighter enclosures. The trapezoidal relaxation gives a family of linear programs that can also be used for finding solutions for interval linear systems via the Oettli-Prager characterisation. We demonstrate the generality of the method through different applications, including nonlinear design in biomolecular circuits, a sensitivity analysis method, and in a compressed sensing context, and discuss the trade-off between enclosure tightness and computational cost.

0.29