An optimization problem in which the decision variables are binary.
Binary programming problem is a mathematical optimization or feasibility program in which some or all of the variables are restricted to be the binary integers zero and one.
Binary problems may be defined as the problem of maximizing or minimizing a linear function subject to both linear, integer, and binary constraints. The constraints may be equalities or inequalities.
Binary programs are problems that can be expressed in canonical form as
$$\max\quad c^\top x$$ $$\text{s.t.}\quad Ax\le b$$ $$x\ge0$$ $$x\in\{0,1\}$$
where $x$ represents the vector of variables (to be determined), $c$ and $b$ are vectors of (known) coefficients, $A$ is a (known) matrix of coefficients, $(⋅)^⊤$ is the matrix transpose, and $\{0,1\}$ is the set of whole binary integers zero and one.
The expression to be maximized or minimized is called the objective function ($c^⊤x$ in this case).
The inequalities $Ax \le b$ and $x \ge 0$ are the constraints which specify a convex polytope over which the objective function is to be optimized.
The inequality $x \ge 0$ is called non-negativity constraints and are often found in linear programming problems. The $x\in\{0,1\}$ constraint limits the to be determined vector variables $x$ to be the binary integers zero and one. The other inequality $Ax \le b$ is called the main constraints.
Integer programming is NP-hard. This is a special case, $0-1$ called integer linear programming, in which unknowns are binary, and only the restrictions must be satisfied, is one of Karp's $21$ NP-complete problems.
Reference:
