The Voice of the Flow: A Graph-Based Approach for Step-Wise Explanations of Constraint Satisfaction Problems

DGA$_2$D: Directed Graph-Guided Automated Algorithm Design with Large Language Models

A Directed Graph-Guided Automated Algorithm Design framework, termed DGA$_2$D, which structures the open-ended program space as a directed graph, where each node represents a functional operator that can be instantiated using one of multiple candidate code implementations, while directed walks constitute complete algorithmic pipelines.

Towards Step-Wise Explanations of Large Search Trees (Short Paper)

From LLM Suggestions to Lean Proofs: Verified Redundant Constraints for MiniZinc

This work presents a pipeline that combines LLM-based constraint generation with empirical evaluation and formal verification, and handles MiniZinc’s partial semantics by requiring the base model to be safe and separately proving that the proposed constraint is well-defined for all instances and solutions of the base model.

Exploiting Structure in the Boolean Weighted Constraint Satisfaction Problem: A Constraint Composite Graph-Based Approach

What is"structure,"and how can we exploit it in combinatorial optimization? Reasoning tasks such as system design, state estimation, and prediction can be cast as combinatorial optimization problems (COPs), traditionally attacked by dedicated algorithms that fail outside their narrow subclass, while communities working on equivalent problems reinvent each other's techniques. The weighted constraint satisfaction problem (WCSP) is a general framework that subsumes COPs from many communities and represents complex physical and non-physical systems, from spin glasses to social networks. Is such generality a curse? Our answer is to exploit"structure": a general-purpose WCSP algorithm should automatically imitate the specialized algorithm for whatever subclass its input belongs to. A WCSP has macro (graphical) structure, which variables interact, and micro (numerical) structure, how they interact. Separate schools of thought exploit one or the other, never both. The constraint composite graph (CCG), introduced in 2008, unifies them: it is an undirected graph over a WCSP instance's variables plus auxiliary ones, on which minimum weighted vertex cover (MWVC) solves the original instance. It is efficiently constructible, but largely unexploited. This dissertation answers three questions affirmatively. The CCG has theoretical advantages beyond identifying tractable classes (new properties proved here); it is practically useful (efficient implementation and experiments); and it extends promisingly to non-Boolean variables (new encodings). We use the CCG to (a) kernelize a WCSP instance, fixing optimal values of some variables by maxflow before search begins, (b) improve min-sum message passing, (c) exploit integer linear programming solvers, and (d) solve COPs on quantum annealers. Solving general COPs faster classically also yields better baselines for the debated quantum advantage.

WhyUnsat: A Practical Explanation Tool

Here it is explained how and why the WhyUnsat approach is now also directly applicable, at no implementation cost, to IPASIR-UP-based constraint programming by Lazy Clause Generation (LCG) as well as to SAT Modulo Theories (SMT).

PathRAG: A Graph-Based Reasoning Approach for Enhancing Retrieval in Software User Manuals

In modern software systems, large-scale technical manuals and complex user workflows impose a significant cognitive barrier for end-users, particularly children and the elderly. While integrated automated assistants have emerged as a promising service paradigm to abstract these system complexities, traditional Retrieval-Augmented Generation (RAG) and existing GraphRAG architectures heavily focus on relational knowledge, failing to capture the strict conditional execution paths and procedural control-flows necessary for accurate system orchestration. To bridge this gap, we propose PathRAG, a lightweight, service-oriented graph reasoning framework designed to enable adaptive, condition-aware guide services over structured software procedures. Rather than processing manuals as flat textual chunks, PathRAG models software tasks as an explicit Conditional Directed Graph, enabling a single-pass graph traversal service that efficiently navigates non-linear software states. Experiments show that PathRAG achieves high accuracy in graph construction (F1 up to 0.956 for nodes and 0.936 for edges) and strong performance in path reasoning (Average Path F1 of 0.82 on simple and 0.63 on complex cases). Notably, the low average path distance (1.53) suggests that most errors correspond to minor deviations from the ground-truth sequence. Despite promising results, limitations include a small dataset, domain specificity, and reliance on rule-based parsing, which may affect generalization to noisy or multi-document scenarios.