Integer Linear Programming

This is a hard problem.

Zero-One Equations

Given an $n\text{ x }m$ matrix A where $[A{]}_{ij}=0\text{ or }1$. Find an $m\text{ x }1$ vector of x of 0’s and 1’s such that $Ax=[1]$, where $[1]=\left[\begin{array}{c}1\\ 1\\ \dots \\ 1\end{array}\right]$.

This is of arbitrary size. This is a case of integer linear programming where:
$\max c^{T}x$ such that $Ax\le b$. Here, $x$ is a vector of non-negative integers. This is also a hard problem. This kind of looks like SAT.

An example is Knapsack.

Note

If you want to turn an optimization problem into a search problem you usually introduce a budget.

The decision version of ILP then is:
Given a goal $g$, find $x$ such that $c^{T}x\ge g$, $Ax\le b$, $x$ is a vector of non-negative integers.