Constraint Satisfaction and Optimization

Latest papers

• ReSolve: Reusing Candidate Reasoning through Selective Generative Moderation

  Bangji Yang, Jiajun Fan, Hongba Ma, Xi Zhu, Weizhi Zhang, Minghao Guo, Ye Li, Hamid Palangi, Jiaxuan You · 2 October 2026

  Sampling multiple solutions spends computation on intermediate deductions and unfinished arguments as well as final answers. We introduce ReSolve, a training-free inference procedure that reuses this candidate reasoning through selective generative moderation. An answer-distribution controller invok…

• OR for AI That Does OR: Routing LLMs up the Escalator inside the OSCAR Framework

  Jinzhi Bu, Haixin Tang, Huanan Zhang · 2 October 2026

  Large language models can translate business descriptions into optimization models, but executable code may misrepresent constraints or objectives. A solver can then return an optimal solution to the wrong problem. Even when the solution satisfies the intended operating rules, a better plan may exis…

• SemOPT: Fixing Semantic Errors in LLM-based Optimization Modeling via Reward-Guided Search

  Zetong Zhou, Wentao Zhang, Jingyuan Wang, Yifan Yang, Zizhuo Wang, Shixi Hu · 1 October 2026

  Operations research supports decision-making in domains such as energy, economics, and healthcare. Solving operations research problems typically begins with optimization modeling, which translates a natural-language problem description into executable solver code. LLMs offer a promising way to auto…

• TACIT: Optimization Models that Learn from Their Mistakes

  Maxime Bouscary, Marco Molinaro, Sirui Li, Saurabh Amin, Ishai Menache, Konstantina Mellou · 1 October 2026

  Real-world optimization problems are difficult to model accurately because many objectives and constraints reside in domain experts' tacit knowledge, making them hard to formalize. As a result, optimization models often contain miscalibrated objectives, missing constraints, or omitted decision varia…

• Autoresearch in Mixed-Integer Linear and Nonlinear Programming

  Yuwei Gu, Yaoxin Wu, Tong Guo, Wen Song, Zhiguang Cao · 1 October 2026

  Despite recent progress in autoresearch, applying it to practical operations research problems, typically formulated as NP-hard mixed-integer linear or nonlinear programs (MILPs or MINLPs), remains challenging because effective research requires systematically managing competing ideas and long-horiz…

• Implementing Cumulative Functions with Generalized Cumulative Constraints

  Pierre Schaus, Charles Thomas, Roger Kameugne · 30 September 2026

  Modeling scheduling problems with conditional time intervals and cumulative functions has become a common approach when using modern commercial constraint programming solvers. This paradigm enables the modeling of a wide range of scheduling problems, including those involving producers and consumers…

• Teaching LLMs to Generate Challenging MILP Instances via Solver Feedback

  Jitin Singla, Parikshit Pareek, Pratik Jawanpuria, Parag Singla · 30 September 2026

  Generating optimization instances that are both feasible and computationally challenging is crucial for benchmarking solvers and training learning-based optimization algorithms. Existing non-LLM generators rely on seed instances or parameter tuning, resulting in high test-time computational cost, wh…

• Do World Models Learn Global Understanding?

  Alexander Detkov, Matt Thomson · 29 September 2026

  AI systems often feel brittle and fragmented. A large language model (LLM) may correctly explain a concept but fail to apply it, or follow safety instructions in one context but not another. This behavior suggests a general failure to lift local information to a global understanding. To gain fundame…

• Reasoning on the Simplex: Geometric Fixed-Point Models

  Talgat Daulbaev, Ilya Glazkov, Maxim Rakhuba, Ivan Oseledets · 29 September 2026

  Looped reasoners spend test-time compute by iterating a weight-tied map, but a small residual does not mean the state is a fixed point when that map lives in unconstrained latent space. We propose Geometric Fixed-Point Reasoning (GFPR), in which the iterated state is the prediction itself: a field o…

• Constraints Are Graphs, Not Chains: Exact Decoding for Diffusion Language Models

  Jianchang Su, Wei Zhang · 29 September 2026

  Diffusion language models (dLLMs) predict masked positions in arbitrary order, but their exact constrained decoders still encode constraints as sequential languages, whose state must track every unresolved dependency between positions. For relational constraints this encoding grows exponentially: fo…

• Beyond Prompt or Skill? Attribution-Guided Optimization of Modular LLM Programs

  Haoran Shou, Haoyue Liu, Yu Huo, Kun Zeng, Xiaoying Tang · 29 September 2026

  Large language models can solve increasingly diverse reasoning tasks, yet their performance remains highly sensitive to task prompts, intermediate instructions, and the way reusable problem-solving knowledge is incorporated. Existing optimization methods usually focus on only one part of this design…

• Investigating Human--AI Discrepancies via Multiple-Solution Problems

  Zihao Wang, Francesco Insulla, Andrea Montanari · 29 September 2026

  Frontier artificial intelligence (AI) models are benchmarked on whether they reach a correct answer. Yet many problems admit several correct answers and repeated attempts, by different people or by the same model resampled, trace out a distribution over them. In this work, we ask whether human and m…

• From Shortcut Learning to Discrete Neural Insertion Sort

  Konstantinos Mylonas, Thrasyvoulos Spyropoulos · 28 September 2026

  Neural algorithmic reasoning aims to train neural networks to follow known algorithms and generalize beyond the input sizes seen during training. However, correct final outputs and intermediate supervision do not necessarily show that a model follows the intended execution. We study this problem usi…

• SPO: Discovering Adaptive Large Neighborhood Search Operators via Stackelberg Program Optimization

  Xinyi Ke, Kai Li, Junliang Xing, Yifan Zhang, Jian Cheng · 28 September 2026

  Large neighborhood search (LNS) relies critically on destroy and repair operators, whose effectiveness depends on both adaptation to the evolving LNS state and interaction between the two roles. We introduce Stackelberg Program Optimization (SPO), an LLM-based framework for discovering adaptive exec…

• Spread and Scale: What Determines Whether Test-Time Budget Allocation Pays

  Jinhyung Bae · 24 September 2026

  Neural combinatorial optimization solvers generate many candidate solutions per instance and report the best one found, using the same sample budget for every instance regardless of difficulty. A companion study showed that reallocating a fixed budget toward harder instances can improve solution qua…

• Graph-Based Inference for Feedback-Driven Word Deduction: A Scalable Framework for the Jotto Problem

  Dakshi Arora, Prakhar Kumar Srivastava, Ranjib Banerjee · 23 September 2026

  A feedback-based word deduction framework based on the Jotto problem is proposed, and the problem space is represented as a weighted graph where all valid words correspond to nodes, and the edge weight is defined by the number of common letters between the two words. Finally, the gameplay is defined…

• Self-Supervised Combinatorial Optimization with Constraints via Frank-Wolfe

  Akbar Rafiey, Yifei Xu, Nikolaos Karalias · 23 September 2026

  Self-supervised learning for combinatorial optimization has emerged as a promising paradigm for solving discrete optimization problems with neural networks, but a central challenge remains: handling hard combinatorial constraints within continuous, gradient-based training. Continuously extending com…

• An Exact Junction-Tree Extended Formulation for Optimal Classification Trees

  Jiancheng TU, WenqiFan · 22 September 2026

  We develop an exact linear programming (LP) formulation for bounded-depth classification trees with binary features, using a junction-tree representation. The formulation is integral and supports recursive subtree optimization. Exact reductions make the model smaller while preserving the optimal val…

• AntiGrounding: Executable Robot Trajectories as Visual Prompts for VLM-Guided Manipulation

  Wenbo Li, Yiteng Chen, Wenhao Li, Qingyao Wu · 18 September 2026

  Natural-language manipulation instructions specify the task goal but leave the underlying robot trajectory unspecified. We present AntiGrounding, a visual action-selection framework built around a dual geometric-visual trajectory interface. After feasibility filtering, each retained short trajectory…

• Solving Minimum Span Antibandwidth and Cyclic Antibandwidth Labeling Problems

  Hieu Truong Xuan, Khanh To Van · 18 September 2026

  The Antibandwidth and Cyclic Antibandwidth problems are NP-hard graph labeling problems that aim to maximize the minimum (cyclic) distance between labels assigned to adjacent vertices. Extensive research on these problems has resulted in a variety of mathematical formulations and computational appro…

• One Color Preprocessing Improves DSATUR

  Adam Nouira, Lucas Isenmann · 17 September 2026

  The Graph Coloring Problem (GCP) is NP-hard and DSATUR stands as one of the fastest heuristics for it despite producing colorings that typically use more colors than state-of-the-art coloring algorithms. We propose SSLD (Semidefinite Spectral Learning with DSATUR), which improves DSATUR by preproces…

• Signed p-adic Residual Encodings of Finite-Domain All-Different Systems with a Sudoku Case Study

  Greg Baker · 16 September 2026

  We study signed, weighted affine $p$-adic residual objectives as native encodings of finite-domain constraints. For primes that separate the finite alphabet, sufficiently weighted positive unary rows pin each coefficient to its allowed set, while negative rows reward unequal endpoints or clause sati…

• Estimating Uncertain Spatial Relationships in Robotics

  Randall Smith, Matthew Self, Peter Cheeseman · 16 September 2026

  In this paper, we describe a representation for spatial information, called the stochastic map, and associated procedures for building it, reading information from it, and revising it incrementally as new information is obtained. The map contains the estimates of relationships among objects in the m…

• A property-registry contract for retrieve-or-refuse thermal-mechanical lattice search

  Shaoliang Yang, Henry Chu, Zu Yashengjiang, Jun Wang · 15 September 2026

  Early thermal-mechanical lattice requirements are knowledge-intensive and often jointly unsatisfiable: an engineer asks for a cell that is light, stiff, laterally conducting and cheap, and no cell in the library satisfies it. A design system should say so, and say which requirement to loosen and by …

• SAILOR: Solver-Assisted Interactive LLM-based Optimization Recovery

  Shaghayegh Sadeghi, Stephen L. Smith, David C. Del Rey Fern'andez · 15 September 2026

  Natural-language descriptions of optimization problems may be incomplete or vague about numerical information that a solver requires, including costs, capacities, demands, bounds, and penalties. A language model can translate the description into code, but when a required value is absent it must eit…