What Is Discrete Programming with Excel VBA

Discrete programming studies extremum problems in which the decision variables are subject to discreteness and the feasible set is finite. These are primarily problems where many factors and objects are physically indivisible. Discrete programming also includes a range of integer programming problems in which the decision variables take only integer values (e.g., staffing/scheduling) or logical, Boolean values 0 or 1 (e.g., the assignment problem). Below we consider the solution of an assignment problem.

Each instructor can teach certain types of classes. The hourly pay cij for instructor ii on class type is given in Table. Construct a teaching plan so that all class types are covered, each instructor teaches only one class type, and the total hourly cost is minimized.

Table. Hourly costs

Steps to Solve

Check balance

The problem is balanced because the number of instructors equals the number of class types. If unbalanced, introduce the missing number of dummy instructors (rows) or dummy class types (columns).

Constructing the mathematical model of the problem.
Let x_ij=1 if the i-th teacher performs the j-th type of class, and x_ij=0 otherwise.
Then the mathematical model is: minimize the functional

subject to the constraints:

Solve with the Solver add-in

Prepare the worksheet as in Fig.

The calculation formulas are shown in Table.

Table. Worksheet formulas for the assignment problem

In the Solver Parameters window :

• Set Objective: the total cost cell.
• To: Min.
• By Changing Variable Cells: the assignment matrix x_ij.
• Subject to the Constraints:
  • Row sums =1=1 (each instructor once).
  • Column sums =1=1 (each class once).
  • Binary on all xijcells.
• In Options, ensure appropriate precision; enable Assume Linear Model if using Simplex with binary constraints (still requires Binary flag).

The resulting optimal assignment is shown: