Suppose we wish to invest $14,000. We have identified four investment opportunities. Investment 1 requires an investment of $5,000 and has a present value (a time-discounted value) of $8,000; investment 2 requires $7,000 and has a value of $11,000; investment 3 requires $4,000 and has a value of $6,000; and investment 4 requires $3,000 and has a value of $4,000. Into which investments should we place our money so as to maximize our total present value?
As in linear programming, our first step is to decide on our
variables. This can be much more difficult in integer programming
because there are very clever ways to use integrality restrictions.
In this case, we will use a 0-1 variable 
for each investment.
If is 1 then we will make investment j. If it is 0, we will
not make the investment. This leads to the 0-1 programming problem:
Now, a straightforward ``bang for buck'' suggests that investment 1 is
the best choice. In fact, ignoring integrality constraints, the
optimal linear programming solution is 
, 
, 
, 
for a value of $22,000. Unfortunately, this solution
is not integral. Rounding 
down to 0 gives a feasible solution
with a value of $19,000. There is a better integer solution,
however, of 
, 
for a value of $21,000.
This example shows that rounding does not necessarily give an optimal
value.
There are a number of additional constraints we might want to add. For instance, consider the following constraints:
All of these, and many more logical restrictions, can be enforced using 0-1 variables. In these cases, the constraints are:
.
