[Rule] ILP/i32 to ILP/bool

[isPANN]

Source

ILP (Integer Linear Programming, i32 variant — non-negative integer variables)

Target

ILP (Integer Linear Programming, bool variant — binary variables)

Motivation

• ILP/i32 is a dead-end node with 0 outgoing reductions and 6 incoming reductions
• This connects ILP/i32 to ILP/bool, which has paths to QUBO — making all problems that reduce to ILP/i32 transitively solvable
• Standard binary expansion technique from integer programming textbooks

Reference

Wolsey, L.A. (1998). Integer Programming. Wiley. Chapter 1 — binary expansion as a standard reformulation technique.

Reduction Algorithm

Given an ILP/i32 instance with n non-negative integer variables x₁, ..., xₙ (each in range 0..2³¹−1), m constraints, objective, and optimization sense:

1. Introduce binary variables. For each integer variable xᵢ, create 31 binary variables yᵢ,₀, ..., yᵢ,₃₀ such that xᵢ = Σⱼ₌₀³⁰ 2ʲ · yᵢ,ⱼ. Total binary variables: 31·n.
2. Transform constraints. For each original constraint Σₖ aₖ · xₖ {≤, ≥, =} b, substitute xₖ = Σⱼ 2ʲ · yₖ,ⱼ to produce a linear constraint over the binary variables. Each original term aₖ · xₖ becomes 31 terms: aₖ · 2⁰ · yₖ,₀, aₖ · 2¹ · yₖ,₁, ..., aₖ · 2³⁰ · yₖ,₃₀.
3. Transform objective. For each term cₖ · xₖ in the objective, substitute to get cₖ · 2⁰ · yₖ,₀ + cₖ · 2¹ · yₖ,₁ + ... + cₖ · 2³⁰ · yₖ,₃₀.
4. Preserve sense. The optimization direction (maximize/minimize) is unchanged.

Solution extraction: Given a binary solution (yᵢ,ⱼ), recover each integer variable as xᵢ = Σⱼ₌₀³⁰ 2ʲ · yᵢ,ⱼ.

Correctness: The binary expansion is a bijection between integer values 0..2³¹−1 and 31-bit binary strings. Every feasible integer assignment has a unique binary encoding satisfying all transformed constraints, and vice versa. Objective values are preserved exactly. No additional upper-bound constraints are needed because 2³¹−1 is exactly representable by 31 bits (2³¹−1 = Σⱼ₌₀³⁰ 2ʲ).

Size Overhead

Target metric	Formula
num_vars	31 * num_vars
num_constraints	num_constraints

Validation Method

Closed-loop test: construct an ILP/i32 instance, reduce to ILP/bool, solve ILP/bool with brute force, extract solution back to ILP/i32, and verify optimality matches brute-force search over the original ILP/i32.

Example

Source (ILP/i32): Minimize −5x₀ − 6x₁, subject to x₀ + x₁ ≤ 5 and 4x₀ + 7x₁ ≤ 28. Optimal: (x₀, x₁) = (3, 2), objective = −27.

Construction:

• 62 binary variables: y₀,₀...y₀,₃₀ and y₁,₀...y₁,₃₀
• x₀ = Σⱼ 2ʲ·y₀,ⱼ, x₁ = Σⱼ 2ʲ·y₁,ⱼ
• Constraint 1: Σⱼ 2ʲ·y₀,ⱼ + Σⱼ 2ʲ·y₁,ⱼ ≤ 5
• Constraint 2: Σⱼ 4·2ʲ·y₀,ⱼ + Σⱼ 7·2ʲ·y₁,ⱼ ≤ 28
• Objective: minimize Σⱼ (−5)·2ʲ·y₀,ⱼ + Σⱼ (−6)·2ʲ·y₁,ⱼ

Target solution: y₀ = (1,1,0,...,0) → x₀ = 1+2 = 3; y₁ = (0,1,0,...,0) → x₁ = 2. Objective = −27.

BibTeX

@book{Wolsey1998,
  author    = {Wolsey, Laurence A.},
  title     = {Integer Programming},
  publisher = {Wiley},
  year      = {1998},
  isbn      = {978-0-471-28366-9}
}