Integer Programming Essentials: Methods and a Chocolate Production Example

1. Integer Programming Concept

Integer programming is a mathematical optimization or feasibility problem where some or all variables are constrained to be integers. In many contexts this refers to Integer Linear Programming (ILP), where the objective function and constraints (except the integrality constraints) are linear.

A special case is 0‑1 integer linear programming, where variables are restricted to 0 or 1 and only the constraints need to be satisfied.

If the decision variables are not all discrete, the problem is called a Mixed Integer Programming problem.

2. Standard Form of Integer Programming

In integer programming, the standard form differs from the linear programming standard form. A standard‑form integer program can be expressed as (note, … is a vector).

3. Solution Methods

Two common solution methods for integer programming:

Branch‑and‑Bound

Cutting‑Plane

Branch‑and‑Bound Method

Step 1: Solve the relaxed problem without integer constraints to obtain an optimal solution (generally non‑integer).

Step 2: Use the upper and lower integer bounds of that solution to create two new subproblems (branch).

Step 3: Solve each subproblem without integer constraints; if a solution is integer, stop; otherwise continue branching.

Step 4: Use the original objective value as an upper bound and any integer solution from subproblems as a lower bound (bounding); prune subproblems that cannot improve the bound.

Step 5: Repeat the steps until the optimal integer solution is found.

Cutting‑Plane Method

Step 1: Solve the relaxed problem without integer constraints to obtain an optimal solution (generally non‑integer).

Step 2: Generate a cutting plane (a line in two dimensions) through that solution to shrink the feasible region.

Step 3: Solve the reduced feasible region for an optimal solution (still ignoring integrality).

Step 4: Repeat steps 2 and 3 until the optimal solution satisfies the integer constraints.

4. Case Study

Assume a chocolate‑production company manufactures two types of chocolate—A and B. Each unit of A requires 1 unit of milk and 3 units of chocolate; each unit of B requires 1 unit of milk and 2 units of chocolate. Available resources: 5 units of milk and 12 units of chocolate. Profit per unit: A yields 6 rupees, B yields 5 rupees. The company wants to maximize profit. How many units of A and B should be produced?

Clearly the decision variables (quantities of A and B) must be integers, making this an integer programming problem.

5. Summary

This article briefly introduced the concept of integer programming, its standard form, solution methods, and a practical case.

References

https://en.wikipedia.org/wiki/Integer_programming

https://github.com/ThomsonRen/mathmodels