Binary Integer Program¶

Definition¶

A binary integer program (BIP) is a linear optimization model in which all decision variables are binary. For variables $y_1,\ldots,y_n$, the domain is $y\in\{0,1\}^n$ before imposing the remaining constraints.

Interpretation¶

A binary integer program models a collection of yes-or-no decisions linked by linear constraints: which projects to fund, at which sites to build, which options to accept. Even a moderate number of such choices creates very many combinations.

With two variables the only candidates are the four corners of the unit square. The constraint $y_1+y_2\le1$ removes $(1,1)$, so at most one of the two alternatives can be chosen, and the feasible set consists of the three dots alone. The shaded triangle contains the points that would be allowed if $y_1$ and $y_2$ could take any value between 0 and 1; its other points carry no meaning as decisions.

With $n$ variables there are $2^n$ assignments before the constraints are applied: $2^{10}=1024$$1024$, but $2^{30}$ is already more than a billion, so listing them all is not a practical solution method. Exact methods such as branch-and-bound are built to avoid this.

A binary integer program is the special case of integer linear programming in which every variable is a binary variable. Sums of binary variables count the selected alternatives, so constraints such as $\displaystyle \sum_jy_j\le k$ or $\displaystyle \sum_jy_j\ge1$ express "at most $k$" and "at least one", as in the project selection and ambulance location models.

A common slip is to allow $0\le y_j\le1$ and read the answer as a decision. The point $(\tfrac{1}{2},\tfrac{1}{2})$ satisfies $y_1+y_2\le1$ but does not say whether either alternative is chosen.

Key Results¶

• There are $2^n$ binary assignments before functional constraints eliminate infeasible combinations.
• Its LP relaxation replaces each binary restriction by $0\le y_j\le1$$1$.
• The objective can count selected alternatives or weight them by costs or returns.

Examples¶

• Project selection maximizes the return from projects under yearly budgets.
• Ambulance location minimizes the number of selected station sites.

Prerequisites¶

• Binary Variable
• Integer Linear Programming

Related Concepts¶

• Project Selection Model
• Ambulance Location Model
• Branch-and-Bound

Sources¶

• OR Modelling · Week 2

Aliases: BIP, 0-1 integer program, binary integer programming, binary program, 0-1 program, pure binary program Symbols: element of, sum

Last updated: 20 October 2026 03:02