Constraint Satisfaction and Optimization

Últimos artículos

• 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 de octubre de 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 de octubre de 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 de octubre de 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 de septiembre de 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 de septiembre de 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 de septiembre de 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 de septiembre de 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 de septiembre de 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 de septiembre de 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 de septiembre de 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 de septiembre de 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 de septiembre de 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 de septiembre de 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 de septiembre de 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 de septiembre de 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 de septiembre de 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 de septiembre de 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 de septiembre de 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 de septiembre de 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 de septiembre de 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 de septiembre de 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 de septiembre de 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 de septiembre de 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…

• Learning Symbolic Constraint Representations from Examples: A Neuro-Symbolic Approach

  Nassim Belmecheri, Arnaud Gotlieb, Nadjib Lazaar, Helge Spieker · 14 de septiembre de 2026

  Learning user-defined concepts as constraint networks has been extensively studied in the constraint acquisition (CA) literature. However, existing approaches typically rely on intensive interactions with a human oracle, making the learning process costly in terms of time and number of queries. In t…

• HyCO: A Hybrid Neural Solver for Combinatorial Optimization

  Yuheng Li, Di Yang, Haipeng Chen, Yanhai Xiong · 9 de septiembre de 2026

  Sequential reinforcement learning (RL) solvers and global diffusion model (DM) solvers for neural combinatorial optimization exhibit complementary failure modes under an optimization-regret view. The former enjoys small marginal regret in the early construction stage, but suffers from horizon-wise c…