Research: AI-enhanced problem solving via problem reductions

[GiggleLiu]

Motivation

Given an industrial optimization or decision problem, how can we best leverage LLMs to find efficient solutions?

Two Approaches

Approach 1: Direct LLM reasoning

Ask an LLM to directly analyze the problem, formulate it as a known computational problem, and develop or suggest an algorithm.

Workflow:

1. Describe the industrial problem to an LLM
2. LLM attempts to identify the underlying problem structure
3. LLM proposes an algorithm or heuristic

Limitations:

• LLMs may misidentify the problem type or miss reduction opportunities
• Solutions are only as good as the LLM's "intuition" — no formal guarantees
• Hard to systematically explore the solution space

Approach 2: LLM + Problem Reductions (proposed)

Combine LLM reasoning with a formal problem reduction framework (this library + the pred CLI tool) to systematically explore solution strategies.

Workflow:

1. Describe the industrial problem to an LLM
2. LLM formulates it as a known problem (e.g., MaximumIndependentSet)
3. LLM uses pred CLI to explore the reduction graph:
   • pred path --from <SourceProblem> --to <TargetProblem> — find reduction paths
   • pred reduce — apply reductions to transform problem instances
   • pred solve — solve the reduced instance with available solvers
4. If a known reduction path yields an efficient solver, done
5. If not, LLM explores creative approaches informed by the reduction landscape

Why this is better:

• Problem reductions are formally verified — each reduction preserves solution correctness
• The reduction graph provides a structured search space for the LLM to explore, rather than relying on open-ended reasoning
• The pred CLI gives the LLM a concrete tool to test reduction strategies programmatically
• Combines the creativity of LLMs (problem formulation, heuristic design) with the reliability of formal reductions (correctness guarantees, known complexity bounds)

Expected Outcome

Approach 2 should outperform Approach 1 in most cases because:

1. Reliability: Reductions are mathematically proven, eliminating a class of LLM errors
2. Systematic exploration: The reduction graph guides the search rather than relying on LLM recall
3. Composability: Multiple reductions can be chained, discovering non-obvious solution paths
4. Tool use: LLMs are increasingly effective at using CLI tools — pred provides a well-defined interface for exploring reductions

Research Questions

• How effectively can LLMs formulate industrial problems as known computational problems?
• Does access to the reduction graph meaningfully improve solution quality or discovery speed?
• What is the right interface between LLM reasoning and formal reduction tools?
• Can we build an agent loop (LLM + pred) that autonomously finds good solution strategies?

Related

• pred CLI tool: feat: add pred CLI tool for problem reductions #82
• Reduction graph and problem inventory in this library