# Can this Integer Linear Programming problem be solved in polynomial time?

I have $$n$$ binary variables, and $$m$$ constraints. Each constraint can be stated as: "exactly $$b$$ of the variables in $$S$$ are equal to 1", for some positive integer $$b$$ and subset of the variables $$S$$. I want to know two things:

1. Can I assign a value to each variable so that every constraint is satisfied?

2. If so, how can I minimize the number of variables that equal 1?

To express this as an Integer Linear Programming (ILP) problem, we can make each variable an element of the vector $$\mathbf{x} \in \{0,1\}^n$$, and write the constraints as $$A\mathbf{x}=\mathbf{b}$$, where $$A \in \{0,1\}^{m \times n}$$ and $$\mathbf{b} \in (\mathbb{Z}^{+})^m$$. The "objective function" is $$\mathbf{c}^\mathrm{T}\mathbf{x}$$, where $$\mathbf{c}$$ is an $$n$$-element vector of 1s. So, the original questions are the same as:

1. Does there exist $$\mathbf{x}$$ such that $$A\mathbf{x}=\mathbf{b}$$?
2. Find $$\mathbf{x}$$ to minimize $$\mathbf{c}^\mathrm{T}\mathbf{x}$$ subject to $$A\mathbf{x}=\mathbf{b}$$.

For general ILP with binary variables, question #1 is NP-complete, and #2 is NP-hard, so there isn't a polynomial-time solution. However, in my problem, $$A$$'s entries are all 0 or 1, which makes me believe there should be a polynomial-time solution.

Is there a polynomial-time algorithm to solve this kind of ILP problem?

The closest I've gotten to an answer is to translate the problem into Minimum-Cost Maximum Flow, as follows.

We create a network $$N = (V, E)$$, whose nodes include a source node $$s$$, sink node $$t$$, and a node for each variable and constraint in the original problem: \begin{align} V = \: &\{s, t\} \\ &\cup \{x_i \;|\; i\in\{1,2,...,n\}\} \\ &\cup \{y_j \;|\; j\in\{1,2,...,m\}\} \end{align} $$E$$ has an edge from $$s$$ to each variable, from each variable to the constraints which include it, and from each constraint to $$t$$: \begin{align} E = \: &\{(s, x_i) \;|\; i\in\{1,2,...,n\}\} \\ &\cup \{(x_i, y_j) \;|\; A_{ji} = 1\} \\ &\cup \{(y_j, t) \;|\; j\in\{1,2,...,m\}\} \end{align} The capacity of each edge is: \begin{align} c(s, x_i) &= \sum_{j=1}^{m} A_{ji} \\ c(x_i, y_j) &= 1 \\ c(y_j, t) &= b_j \\ \end{align} Finally, the cost of each edge is: \begin{align} a(s, x_i) &= 1/c(s, x_i) \\ a(x_i, y_j) &= 0 \\ a(y_j, t) &= 0 \\ \end{align}

Conceptually, saturating an $$x_i$$ node means setting the corresponding variable to 1, and saturating a $$y_i$$ node means satisfying the corresponding constraint. Any flow $$f$$ can be translated back into an assignment of binary values for $$\mathbf{x}$$ by setting $$x_i=1$$ when $$f(s, x_i) = c(s, x_i)$$ and $$x_i=0$$ when $$f(s, x_i) = 0$$, unless we have $$0 < f(s, x_i) < c(s, x_i)$$ for some $$x_i$$, in which case there isn't a meaningful translation.

Then, the original questions are equivalent to the following:

1. Does there exist a maximum flow $$f$$ whose value is $$\sum_{j=1}^{m} b_j$$, which also satisfies $$f(s, x_i) = 0 \,\lor\, f(s, x_i) = c(s, x_i) \;\forall\; i\in\{1,2,...,n\}$$?

2. If so, which of these flows has the lowest cost, $$\sum_{(u, v)\in E}a(u,v)f(u,v)$$?

Question #1, ignoring the condition on $$f(s, x_i)$$, is the decision Maximum Flow problem, which I can solve using the Ford-Fulkerson algorithm in $$O(mn)$$ time. Question #2 is the Minimum-Cost Flow problem, which I understand also has polynomial-time algorithms.

The problem is I can't just use the FF algorithm directly! If it gives me a flow which doesn't satisfy the condition on $$f(s, x_i)$$, then I can't translate the flow back into an assignment for $$\mathbf{x}$$.

So my follow-up question is, am I at least on the right track? Can I modify a Max Flow algorithm to only return flows which satisfy the condition on $$f(s, x_i)$$, while still running in polynomial time?

No, the problem is NP-complete, by reduction from Exact Cover, so there is not likely to be any polynomial-time algorithm (unless P=NP). Suppose you have an instance of Exact Cover, i.e., a collection $$\mathcal{S}$$ of sets. Introduce one binary variable $$x_S$$ per set $$S \in \mathcal{S}$$. For each element $$e$$ that appears in any set, consider the sets $$S \in \mathcal{S}$$ such that $$e \in S$$; we obtain a constraint that exactly 1 out of the corresponding binary variables are set to 1. In other words, the constraint is
$$\sum_S x_S = 1,$$
where the sum is over all sets $$S \in \mathcal{S}$$ such that $$e \in S$$. There exists an exact cover iff the resulting constraint system is satisfiable. Therefore, any polynomial-time algorithm to solve your type of constraints would immediately yield a polynomial-time algorithm to solve Exact Cover. But Exact Cover is already known to be NP-complete.