Feasibility problem

A feasibility problem asks whether any point satisfies a specified collection of optimization constraints, and seeks such a point when one exists. There need not be a preference among satisfying points. If the feasible set is $F$, the mathematical questions are whether $F$ is empty and, if not, how to produce a feasible point. A feasibility problem can be represented as mathematical optimization with a constant zero objective function.^[ref]

For an original linear example, considerThe pair $(1,0)$ is a directly checkable witness. Replacing the last bound by $x+y\le 0.5$ makes the constraints inconsistent: adding $-x\le -1$, $-y\le 0$ and $x+y\le 0.5$ gives $0\le -0.5$. This short contradiction certifies infeasibility without enumerating candidate points.

More generally, for a real linear system $Ax\le b$, a vector $\lambda \ge 0$ satisfyingis an infeasibility certificate: multiplying and adding the assumed inequalities would force $0\le {\lambda }^{T}b<0$. This is the certificate side of Farkas' lemma. A failed numerical search or a timeout is different from such a proof; it need not imply that the feasible set is empty.

The allowed variable set is part of the question. The equation $2x=1$ is feasible over the real numbers, with $x=1/2$, but infeasible when $x$ must be an integer. Thus replacing integer programming constraints by a real relaxation changes the feasibility problem.

Quasiconvex optimization supplies a useful connection: for each threshold $t$, test whether the original constraints and $f(x)\le t$ admit a feasible point. Such decisions can bracket the optimal value, while a retained witness gives an actual decision attaining the tested bound.^[ref] Numerical tolerances should be stated: a small constraint residual can support approximate feasibility without proving exact satisfaction.