CLI Tool

The pred command-line tool lets you explore the reduction graph, create problem instances, solve problems, and perform reductions — all from your terminal.

Installation

Install from crates.io:

cargo install problemreductions-cli

Or build from source:

git clone https://github.com/CodingThrust/problem-reductions
cd problem-reductions
cargo build -p problemreductions-cli --release   # builds target/release/pred
cargo install --path problemreductions-cli       # optional: installs `pred` to ~/.cargo/bin

Verify the installation:

pred --version

For a workspace-local run without installing globally, use:

cargo run -p problemreductions-cli --bin pred -- --version

ILP Backend

The default ILP backend is HiGHS. To use a different backend:

cargo install problemreductions-cli --features coin-cbc
cargo install problemreductions-cli --features scip
cargo install problemreductions-cli --no-default-features --features clarabel

Available backends: highs (default), coin-cbc, clarabel, scip, lpsolve, microlp.

Quick Start

# Create a Maximum Independent Set problem
pred create MIS --graph 0-1,1-2,2-3 -o problem.json

# Create a weighted instance (variant auto-upgrades to i32)
pred create MIS --graph 0-1,1-2,2-3 --weights 3,1,2,1 -o weighted.json

# Create a Steiner Tree instance
pred create SteinerTree --graph 0-1,0-3,1-2,1-3,2-3,2-4,3-4 --edge-weights 2,5,2,1,5,6,1 --terminals 0,2,4 -o steiner.json

# Create a Length-Bounded Disjoint Paths instance
pred create LengthBoundedDisjointPaths --graph 0-1,1-6,0-2,2-3,3-6,0-4,4-5,5-6 --source 0 --sink 6 --num-paths-required 2 --bound 3 -o lbdp.json

# Create a Consecutive Block Minimization instance (alias: CBM)
pred create CBM --matrix '[[true,false,true],[false,true,true]]' --bound-k 2 -o cbm.json

# CBM currently needs the brute-force solver
pred solve cbm.json --solver brute-force

# Or start from a canonical model example
pred create --example MIS/SimpleGraph/i32 -o example.json

# Or from a canonical rule example
pred create --example MVC/SimpleGraph/i32 --to MIS/SimpleGraph/i32 -o example.json

# Inspect what's inside a problem file
pred inspect problem.json

# Inspect the new path problem
pred inspect lbdp.json

# Solve it (auto-reduces to ILP)
pred solve problem.json

# Or solve with brute-force
pred solve problem.json --solver brute-force

# LengthBoundedDisjointPaths currently needs brute-force
pred solve lbdp.json --solver brute-force

# Evaluate a specific configuration (shows Valid(N) or Invalid)
pred evaluate problem.json --config 1,0,1,0

# Reduce to another problem type and solve via brute-force
pred reduce problem.json --to QUBO -o reduced.json
pred solve reduced.json --solver brute-force

# Pipe commands together (use - to read from stdin)
pred create MIS --graph 0-1,1-2,2-3 | pred solve -
pred create MIS --graph 0-1,1-2,2-3 | pred reduce - --to QUBO | pred solve -

Note: When you provide --weights with non-unit values (e.g., 3,1,2,1), the variant is automatically upgraded from the default unit-weight (One) to i32. You can also specify the weighted variant explicitly: pred create MIS/SimpleGraph/i32 --graph 0-1 --weights 3,1.

Global Flags

Flag	Description
`-o, --output <FILE>`	Save JSON output to a file
`--json`	Output JSON to stdout instead of human-readable text
`-q, --quiet`	Suppress informational messages on stderr

Commands

`pred list` — List all problem types

Lists all registered problem types with their short aliases.

$ pred list
Registered problems: 17 types, 48 reductions, 25 variant nodes

  Problem                Aliases     Variants  Reduces to
  ─────────────────────  ──────────  ────────  ──────────
  CircuitSAT                                1           1
  Factoring                                 1           2
  ILP                                       1           1
  KColoring                                 2           3
  KSatisfiability        3SAT, KSAT         3           7
  MaxCut                                    1           1
  MaximumClique                             1           1
  MaximumIndependentSet  MIS                4          10
  MaximumMatching                           1           2
  MaximumSetPacking                         2           4
  MinimumDominatingSet                      1           1
  MinimumSetCovering                        1           1
  MinimumVertexCover     MVC                1           4
  QUBO                                      1           1
  Satisfiability         SAT                1           5
  SpinGlass                                 2           3
  TravelingSalesman      TSP                1           1

Use `pred show <problem>` to see variants, reductions, and fields.

`pred show` — Inspect a problem

Show variants, fields, size fields, and reductions for a problem type. show operates at the type level — it displays all variants of a problem, not a specific node. Slash suffixes (e.g., MIS/UnitDiskGraph) are rejected; use pred to or pred from for variant-level exploration. Use short aliases like MIS for MaximumIndependentSet.

$ pred show MIS
MaximumIndependentSet
  Find maximum weight independent set in a graph

Variants (4):
  {graph=SimpleGraph, weight=i32}
  {graph=UnitDiskGraph, weight=i32}
  {graph=KingsSubgraph, weight=i32}
  {graph=TriangularSubgraph, weight=i32}

Fields (2):
  graph (G) -- The underlying graph G=(V,E)
  weights (Vec<W>) -- Vertex weights w: V -> R

Size fields (2):
  num_vertices
  num_edges

Reduces to (10):
  MaximumIndependentSet {graph=SimpleGraph, weight=i32} → MaximumSetPacking ...
  MaximumIndependentSet {graph=SimpleGraph, weight=i32} → MinimumVertexCover ...
  ...

Reduces from (9):
  MinimumVertexCover {graph=SimpleGraph, weight=i32} → MaximumIndependentSet ...
  Satisfiability (default) → MaximumIndependentSet {graph=SimpleGraph, weight=i32}
  ...

`pred to` — Explore outgoing neighbors

Explore which problems a given problem can reduce to within k hops. Each node in the tree shows its variant (graph type, weight type, etc.).

$ pred to MIS --hops 2
MaximumIndependentSet {graph=SimpleGraph, weight=i32} — 2-hop neighbors (outgoing)

MaximumIndependentSet {graph=SimpleGraph, weight=i32}
├── MaximumSetPacking {weight=i32}
│   ├── ILP (default)
│   ├── MaximumIndependentSet {graph=SimpleGraph, weight=i32}
│   └── QUBO {weight=f64}
├── MaximumIndependentSet {graph=KingsSubgraph, weight=i32}
│   └── MaximumIndependentSet {graph=SimpleGraph, weight=i32}
├── MaximumIndependentSet {graph=TriangularSubgraph, weight=i32}
│   └── MaximumIndependentSet {graph=SimpleGraph, weight=i32}
├── MinimumVertexCover {graph=SimpleGraph, weight=i32}
│   └── MaximumIndependentSet {graph=SimpleGraph, weight=i32}

5 reachable problems in 2 hops

`pred from` — Explore incoming neighbors

Explore which problems can reduce from (i.e., reduce into) the given problem:

$ pred from QUBO --hops 1
QUBO {weight=f64} — 1-hop neighbors (incoming)

QUBO {weight=f64}
├── MaximumIndependentSet {graph=SimpleGraph, weight=i32}
├── MinimumVertexCover {graph=SimpleGraph, weight=i32}
└── SpinGlass {graph=SimpleGraph, weight=f64}

3 reachable problems in 1 hops

`pred path` — Find a reduction path

Find the cheapest chain of reductions between two problems:

$ pred path MIS QUBO
Path (3 steps): MaximumIndependentSet/SimpleGraph/i32 → MaximumSetPacking/i32 → QUBO/f64

  Step 1: MaximumIndependentSet/SimpleGraph/i32 → MaximumSetPacking/i32
    num_sets = num_vertices
    universe_size = num_edges

  Step 2: MaximumSetPacking/i32 → MaximumSetPacking/f64
    num_sets = num_sets
    universe_size = universe_size

  Step 3: MaximumSetPacking/f64 → QUBO/f64
    num_vars = num_sets

  Overall:
    num_vars = num_vertices

Multi-step paths are discovered automatically:

$ pred path Factoring SpinGlass
Path (2 steps): Factoring → CircuitSAT → SpinGlass {graph: "SimpleGraph", weight: "i32"}

  Step 1: Factoring → CircuitSAT
    num_variables = num_bits_first * num_bits_second
    num_assignments = num_bits_first * num_bits_second

  Step 2: CircuitSAT → SpinGlass {graph: "SimpleGraph", weight: "i32"}
    num_spins = num_assignments
    num_interactions = num_assignments

Show all paths or save for later use with pred reduce --via:

pred path MIS QUBO --all                    # all paths (up to 20)
pred path MIS QUBO --all --max-paths 50     # increase limit
pred path MIS QUBO -o path.json             # save path for `pred reduce --via`
pred path MIS QUBO --all -o paths/          # save all paths to a folder

When using --all, the output is capped at --max-paths (default: 20). If more paths exist, the output indicates truncation.

Use --cost to change the optimization strategy:

pred path MIS QUBO --cost minimize-steps           # default
pred path MIS QUBO --cost minimize:num_variables   # minimize a size field

Use pred show <problem> to see which size fields are available.

`pred export-graph` — Export the reduction graph

Export the full reduction graph as JSON:

pred export-graph                           # print to stdout
pred export-graph -o reduction_graph.json   # save to file

`pred create` — Create a problem instance

Construct a problem instance from CLI arguments and save as JSON:

pred create --example MIS/SimpleGraph/i32 -o model.json
pred create --example MVC/SimpleGraph/i32 --to MIS/SimpleGraph/i32 -o problem.json
pred create --example MVC/SimpleGraph/i32 --to MIS/SimpleGraph/i32 --example-side target -o target.json
pred create MIS --graph 0-1,1-2,2-3 -o problem.json
pred create MIS --graph 0-1,1-2,2-3 --weights 2,1,3,1 -o problem.json
pred create SAT --num-vars 3 --clauses "1,2;-1,3" -o sat.json
pred create QUBO --matrix "1,0.5;0.5,2" -o qubo.json
pred create CBM --matrix '[[true,false,true],[false,true,true]]' --bound-k 2 -o cbm.json
pred create KColoring --k 3 --graph 0-1,1-2,2-0 -o kcol.json
pred create SpinGlass --graph 0-1,1-2 -o sg.json
pred create MaxCut --graph 0-1,1-2,2-0 -o maxcut.json
pred create SteinerTree --graph 0-1,0-3,1-2,1-3,2-3,2-4,3-4 --edge-weights 2,5,2,1,5,6,1 --terminals 0,2,4 -o steiner.json
pred create UndirectedTwoCommodityIntegralFlow --graph 0-2,1-2,2-3 --capacities 1,1,2 --source-1 0 --sink-1 3 --source-2 1 --sink-2 3 --requirement-1 1 --requirement-2 1 -o utcif.json
pred create LengthBoundedDisjointPaths --graph 0-1,1-6,0-2,2-3,3-6,0-4,4-5,5-6 --source 0 --sink 6 --num-paths-required 2 --bound 3 -o lbdp.json
pred create Factoring --target 15 --bits-m 4 --bits-n 4 -o factoring.json
pred create Factoring --target 21 --bits-m 3 --bits-n 3 -o factoring2.json
pred create X3C --universe 9 --sets "0,1,2;0,2,4;3,4,5;3,5,7;6,7,8;1,4,6;2,5,8" -o x3c.json
pred create MinimumTardinessSequencing --n 5 --deadlines 5,5,5,3,3 --precedence-pairs "0>3,1>3,1>4,2>4" -o mts.json

For LengthBoundedDisjointPaths, the CLI flag --bound maps to the JSON field max_length.

For ConsecutiveBlockMinimization, the --matrix flag expects a JSON 2D bool array such as '[[true,false,true],[false,true,true]]'. The example above shows the accepted shape, and solving CBM instances currently requires --solver brute-force.

Canonical examples are useful when you want a known-good instance from the paper/example database. For model examples, pred create --example <PROBLEM_SPEC> emits the canonical instance for that graph node. For rule examples, pred create --example <SOURCE_SPEC> --to <TARGET_SPEC> emits the source instance by default; use --example-side target to emit the reduction target instance instead.

Generate random instances for graph-based problems:

pred create MIS --random --num-vertices 10 --edge-prob 0.3
pred create MIS --random --num-vertices 100 --seed 42 -o big.json
pred create MaxCut --random --num-vertices 20 --edge-prob 0.5 -o maxcut.json

Without -o, the problem JSON is printed to stdout, which can be piped to other commands:

pred create MIS --graph 0-1,1-2,2-3 | pred solve -
pred create MIS --random --num-vertices 10 | pred inspect -

The output file uses a standard wrapper format:

{
  "type": "MaximumIndependentSet",
  "variant": {"graph": "SimpleGraph", "weight": "i32"},
  "data": { ... }
}

`pred evaluate` — Evaluate a configuration

Evaluate a configuration against a problem instance:

$ pred evaluate problem.json --config 1,0,1,0
Valid(2)

Stdin is supported with -:

pred create MIS --graph 0-1,1-2,2-3 | pred evaluate - --config 1,0,1,0

`pred inspect` — Inspect a problem file

Show a summary of what's inside a problem JSON or reduction bundle:

$ pred inspect problem.json
Type: MaximumIndependentSet {graph=SimpleGraph, weight=i32}
Size: 5 vertices, 5 edges

Works with reduction bundles and stdin:

pred inspect bundle.json
pred create MIS --graph 0-1,1-2 | pred inspect -

`pred reduce` — Reduce a problem

Reduce a problem to a target type. Outputs a reduction bundle containing source, target, and path:

pred reduce problem.json --to QUBO -o reduced.json

Use a specific reduction path (from pred path -o). The target is inferred from the path file, so --to is not needed:

pred reduce problem.json --via path.json -o reduced.json

Stdin is supported with -:

pred create MIS --graph 0-1,1-2,2-3 | pred reduce - --to QUBO

The bundle contains everything needed to map solutions back:

{
  "source": { "type": "MaximumIndependentSet", "variant": {...}, "data": {...} },
  "target": { "type": "QUBO", "variant": {...}, "data": {...} },
  "path": [
    {"name": "MaximumIndependentSet", "variant": {"graph": "SimpleGraph", "weight": "i32"}},
    {"name": "QUBO", "variant": {"weight": "f64"}}
  ]
}

`pred solve` — Solve a problem

Solve a problem instance using ILP (default) or brute-force:

pred solve problem.json                         # ILP solver (default)
pred solve problem.json --solver brute-force    # brute-force solver
pred solve problem.json --timeout 30            # abort after 30 seconds

Stdin is supported with -:

pred create MIS --graph 0-1,1-2,2-3 | pred solve -
pred create MIS --graph 0-1,1-2,2-3 | pred solve - --solver brute-force

When the problem is not ILP, the solver automatically reduces it to ILP, solves, and maps the solution back. The auto-reduction is shown in the output:

$ pred solve problem.json
Problem: MaximumIndependentSet (reduced to ILP)
Solver: ilp
Solution: [1, 0, 0, 1]
Evaluation: Valid(2)

Solve a reduction bundle (from pred reduce):

$ pred solve reduced.json --solver brute-force
Source: MaximumIndependentSet
Target: QUBO (solved with brute-force)
Target solution: [0, 1, 0, 1]
Target evaluation: Valid(-2.0)
Source solution: [0, 1, 0, 1]
Source evaluation: Valid(2)

Note: The ILP solver requires a reduction path from the target problem to ILP. LengthBoundedDisjointPaths does not currently have one, so use pred solve lbdp.json --solver brute-force. For other problems, use pred path <PROBLEM> ILP to check whether an ILP reduction path exists.

Shell Completions

Enable tab completion by adding one line to your shell config:

# bash (~/.bashrc)
eval "$(pred completions bash)"

# zsh (~/.zshrc)
eval "$(pred completions zsh)"

# fish (~/.config/fish/config.fish)
pred completions fish | source

If the shell argument is omitted, pred completions auto-detects your current shell.

JSON Output

All commands support -o to write JSON to a file and --json to print JSON to stdout:

pred list -o problems.json       # save to file
pred list --json                 # print JSON to stdout
pred show MIS --json             # works on any command
pred path MIS QUBO --json
pred solve problem.json --json

This is useful for scripting and piping:

pred list --json | jq '.problems[].name'
pred path MIS QUBO --json | jq '.path'

Problem Name Aliases

You can use short aliases instead of full problem names (shown in pred list):

Alias	Full Name
`MIS`	`MaximumIndependentSet`
`MVC`	`MinimumVertexCover`
`SAT`	`Satisfiability`
`3SAT` / `KSAT`	`KSatisfiability`
`TSP`	`TravelingSalesman`

You can also specify variants with a slash: MIS/UnitDiskGraph, SpinGlass/SimpleGraph.

When a bare name (no slash) is used in commands like path, to, from, create, or reduce, it resolves to the declared default variant for that problem type. For example, MIS resolves to MaximumIndependentSet/SimpleGraph/One.

If you mistype a problem name, pred will suggest the closest match:

$ pred show MaximumIndependentSe
Error: Unknown problem: MaximumIndependentSe

Did you mean: MaximumIndependentSet?

Run `pred list` to see all available problems.

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

CLI Tool

Installation

ILP Backend

Quick Start

Global Flags

Commands

`pred list` — List all problem types

`pred show` — Inspect a problem

`pred to` — Explore outgoing neighbors

`pred from` — Explore incoming neighbors

`pred path` — Find a reduction path

`pred export-graph` — Export the reduction graph

`pred create` — Create a problem instance

`pred evaluate` — Evaluate a configuration

`pred inspect` — Inspect a problem file

`pred reduce` — Reduce a problem

`pred solve` — Solve a problem

Shell Completions

JSON Output

Problem Name Aliases

FilesExpand file tree

cli.md

Latest commit

History

cli.md

File metadata and controls

CLI Tool

Installation

ILP Backend

Quick Start

Global Flags

Commands

pred list — List all problem types

pred show — Inspect a problem

pred to — Explore outgoing neighbors

pred from — Explore incoming neighbors

pred path — Find a reduction path

pred export-graph — Export the reduction graph

pred create — Create a problem instance

pred evaluate — Evaluate a configuration

pred inspect — Inspect a problem file

pred reduce — Reduce a problem

pred solve — Solve a problem

Shell Completions

JSON Output

Problem Name Aliases

`pred list` — List all problem types

`pred show` — Inspect a problem

`pred to` — Explore outgoing neighbors

`pred from` — Explore incoming neighbors

`pred path` — Find a reduction path

`pred export-graph` — Export the reduction graph

`pred create` — Create a problem instance

`pred evaluate` — Evaluate a configuration

`pred inspect` — Inspect a problem file

`pred reduce` — Reduce a problem

`pred solve` — Solve a problem