Motivation
Direct ILP formulation for MinimumMatrixCover. Companion issue for #931.
Source
MinimumMatrixCover
Target
ILP
Reference
Standard QBOP linearization for quadratic binary optimization.
Reduction Algorithm
Input: n×n nonneg matrix A.
- Binary variables x_i ∈ {0, 1} for i = 1, ..., n (mapped to f(i) = 2x_i - 1).
- Substitute f(i)f(j) = (2x_i-1)(2x_j-1) = 4x_ix_j - 2x_i - 2x_j + 1.
- Linearize x_ix_j with standard McCormick: introduce y_{ij} = x_i x_j, add y_{ij} ≤ x_i, y_{ij} ≤ x_j, y_{ij} ≥ x_i + x_j - 1.
- Objective: minimize the linearized quadratic form.
Size Overhead
| Code metric |
Formula |
num_variables |
n + n*(n-1)/2 |
num_constraints |
3n(n-1)/2 |
Validation Method
Closed-loop test.
Example
Source: 2×2 matrix A = [[0,1],[1,0]].
Optimal: f=(+1,-1) or (-1,+1), value = -2. Min(-2).
Motivation
Direct ILP formulation for MinimumMatrixCover. Companion issue for #931.
Source
MinimumMatrixCoverTarget
ILPReference
Standard QBOP linearization for quadratic binary optimization.
Reduction Algorithm
Input: n×n nonneg matrix A.
Size Overhead
num_variablesnum_constraintsValidation Method
Closed-loop test.
Example
Source: 2×2 matrix A = [[0,1],[1,0]].
Optimal: f=(+1,-1) or (-1,+1), value = -2. Min(-2).