Integer and binary programs extend linear programming by requiring some or all decision variables to take whole-number or 0–1 values. They are used for project selection, facility location, scheduling, assignment, and logical “yes/no” decisions. This page shows how to set up integer and binary models step-by-step, with numerical examples and simple diagrams.

1. Integer vs Binary Decision Variables

• Integer variable: can take values 0, 1, 2, 3, … (whole numbers).
• Binary variable: can take only 0 or 1 (off/on, no/yes).

In algebraic form:

\[ x_i \in \mathbb{Z}_{\ge 0} \quad \text{(integer)} \] \[ y_j \in \{0,1\} \quad \text{(binary)} \]

2. Basic Structure of an Integer/Binary Program

General form:

\[ \text{Maximize or Minimize } Z = \sum c_i x_i \] subject to \[ \sum a_{ij} x_i \le b_j,\quad \text{(or =, ≥)} \] \[ x_i \ge 0,\quad x_i \in \mathbb{Z} \text{ or } \{0,1\} \]

Decision variables  → integer or binary
Objective           → linear in the variables
Constraints         → linear equalities/inequalities
Integrality         → explicitly required

3. Example 1 – Project Selection (Pure Binary Program)

A firm can choose among 4 projects. Each project has a profit and a cost. Budget is limited to 10 units. Decide which projects to undertake.

Project   Profit   Cost
  1         8       7
  2         5       4
  3         6       3
  4         4       2
Budget = 10

3.1 Define binary variables

\(x_i = 1\) if project i is selected, 0 otherwise.

3.2 Objective function

\[ \text{Maximize } Z = 8x_1 + 5x_2 + 6x_3 + 4x_4 \]

3.3 Budget constraint

\[ 7x_1 + 4x_2 + 3x_3 + 2x_4 \le 10 \]

3.4 Binary restrictions

\[ x_1, x_2, x_3, x_4 \in \{0,1\} \]

3.5 Simple diagram

Budget line (10 units)
|
|   x1(7)   x2(4)   x3(3)   x4(2)
+----------------------------------> choices

The solver searches over all 0–1 combinations that respect the budget and picks the one with maximum profit.

4. Example 2 – Integer Production Planning

A factory produces two products in integer batches. Each batch uses machine time and labor.

Product   Profit   Machine hrs   Labor hrs
  1        50          6            3
  2        40          4            5

Machine capacity = 60 hrs
Labor capacity   = 50 hrs

4.1 Integer variables

\(x_1\) = number of batches of Product 1 (integer) \(x_2\) = number of batches of Product 2 (integer)

4.2 Objective

\[ \text{Maximize } Z = 50x_1 + 40x_2 \]

4.3 Constraints

Machine: \[ 6x_1 + 4x_2 \le 60 \] Labor: \[ 3x_1 + 5x_2 \le 50 \]

4.4 Integrality

\[ x_1, x_2 \in \mathbb{Z}_{\ge 0} \]

4.5 Feasible lattice diagram

x2
^
|   • feasible integer points
|  • • •
| • • •
+------------------> x1
   0  1  2  3  4  5  6 ...

The optimal solution is found among the integer lattice points that satisfy both constraints.

5. Example 3 – Linking Integer and Binary Variables

A supplier requires that if you order a product, you must order at least 5 units.

5.1 Variables

\(x\) = quantity ordered (integer) \(y\) = 1 if product is ordered, 0 otherwise (binary)

5.2 Linking constraints

Minimum order if chosen: \[ x \ge 5y \]

Upper bound (big-M): \[ x \le My \]

If \(y = 0\), then \(x \le 0\) → no order. If \(y = 1\), then \(5 \le x \le M\) → at least 5 units.

5.3 Integrality

\[ x \in \mathbb{Z}_{\ge 0}, \quad y \in \{0,1\} \]

6. Example 4 – Either/Or Constraints with Binary Variables

You must choose either constraint A or constraint B, but not both.

Constraint A: 2x + y ≤ 10
Constraint B: x + 3y ≤ 12

6.1 Binary variable

\(z = 1\) if Constraint A is active, 0 if Constraint B is active.

6.2 Big-M formulation

\[ 2x + y \le 10 + M(1 – z) \] \[ x + 3y \le 12 + Mz \]

If \(z = 1\): first constraint becomes tight (no M), second gets relaxed by M. If \(z = 0\): second constraint is tight, first is relaxed.

7. How to Set Up Integer & Binary Programs in Excel

1. Place decision variables in a clean, contiguous block (e.g., B4:E4 or B4:B7).
2. Ensure cells are numbers (no formulas) so Solver can change them.
3. Build the objective cell using SUMPRODUCT with coefficients and variables.
4. Build constraint LHS cells as formulas referencing the decision variables.
5. In Solver:
   • Set objective cell to Max or Min.
   • Set variable cells to the decision variable range.
   • Add constraints for each LHS ≤, =, or ≥ RHS.
   • Add integer or binary constraints on the appropriate ranges.
   • Use Simplex LP (for linear models) with integer/binary options enabled.

8. Common Modeling Mistakes

• Leaving decision variable cells as formulas instead of numbers.
• Forgetting to declare variables as integer or binary in Solver.
• Using nonlinear expressions (e.g., products of decision variables) in a linear integer model.
• Missing upper bounds, causing unrealistic or unbounded integer solutions.
• Incorrect big-M values (too small → infeasible; too large → numerical instability).