Definition
Integer Linear Programming Decision Problem
Instance: An integer matrix
, vectors , , and a threshold , all encoded in binary. Question: Does there exist
such that The inequality
holds row by row. This asks whether integer linear programming has a feasible integer solution reaching the objective threshold. Pure integer feasibility is the special case and .