HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Is 0-1 integer linear programming NP-hard when $c^T$ is the all-ones vector?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
lineartheallprogramminghardwhenonesintegervector

Problem

Karp's 21 NP-complete problems show that 0-1 integer linear programming is NP-hard. That is, an integer linear program with binary variables.

If we set the $c^T$ vector of the objective $\text {maximize } c^Tx$ to all one (unweighted, i.e., $c^T=(1,1,\dots,1)$) is the problem still NP-hard?

Solution

We can encode satisfiability of a SAT instance as the feasibility of a 0-1 integer linear program. For feasibility, the objective function doesn't matter, so you can impose whatever constraint you wish on it.

For an example of how to express boolean or, boolean and, and boolean negation in a 0-1 integer linear program, see Express boolean logic operations in zero-one integer linear programming (ILP). This is all that's needed to express a SAT instance as a 0-1 integer linear program.

Context

StackExchange Computer Science Q#19378, answer score: 5

Revisions (0)

No revisions yet.