The Math Programming add-in creates a structure
that is useful for specifying the objective function and constraints
of an algebraic optimization model. An example is shown below.
The model has a nonlinear objective with separable linear and
quadratic terms. The coefficients of the linear terms are in
row 12. Row 13 holds the square of each variable and row 14
holds the quadratic coefficients. This objective is a convex
Even without the integrality requirement the model shown is
difficult to solve. The objective is to maximize a convex function
in a linearly constrained region. For the continuous problem
(dropping integrality) there are several local maxima at the
extreme points of the feasible region. The solution obtained
with the Excel Solver depends on the initial solution. For example
when the initial solution is set to all 0's, the Solver terminates
at the solution with all 0's, however, this is not the global
maximum. We will use exhaustive enumeration to solve the problem.
To treat the math
programming model as a combinatorial problem choose Math
Program from the Optimize menu. The dialog below
The buttons in the Search Variables region
of the dialog select the variables to be used for the combinatorial
optimization. For this example we choose the All button.
This means that all the model variables will be varied in the
search for the optimum. We illustrate the other choices later.
The worksheet is modified in several ways by the add-in. The
cells that represent the model variables, Values and
the Lower and Upper Bounds, receive new names
so that they also become the combinatorial variables and their
limits. Thus the range H8:N8 holds both the math programming
variables and the combinatorial variables, so it is unnecessary
to manually link them. Similarly, cell F4 is assigned a new
name so it represents both the model objective function and
the combinatorial objective function, again removing the requirement
to manually link the two cells.
Formulas are added to the right of the model (column O for
this case) that compute the values of the slack variables for
the constraints. In the next column (P) formulas are included
that evaluate as positive quantities for violated constraints
and 0 for satisfied constraints. A value in column P shows the
amount by which a constraint is violated. Since the current
solution is feasible (all 0's) and all the constraints are satisfied,
column P holds all 0's. The figure below shows the added columns.
We choose to solve the problem with exhaustive
enumeration. The remainder of the combinatorial cells constructed
by the add-in are shown below after exhaustive enumeration
is complete. Cell U3 holds the sum of the numbers in the range
P17:P21, and cell U2 returns TRUE if the sum is 0 and FALSE
if the sum is positive. Thus cell U2 indicates whether a given
solution is feasible. Selecting the Search
from the menu initiates exhaustive enumeration. The optimum
solution has x6 = x7 = 2, and all others equal to 0.
The seach process evaluates each of the 2188 solutions allowed
by the lower and upper bounds of the variables. During the
process, the program collects the 20 best feasible solutions
and presents them starting in column W. The optimum appears
at the top of the sorted list.
A partial list of the solutions
investigated by the greedy approach is shown below. The list
presents the solutions in the order generated. Only variations
that provide improvement and are feasible are shown in the
list. Although 37 solutions were examined only 25 are shown.
Each iteration begins from the incumbent from the previous
iteration. The first incumbent is the initial solution with
all zeros. The first set of iterations examines all solutions
obtained by changing each variable by 1 unit. Only positive
variations are attempted because the variables are bounded
from below by 0. The best solution obtained is:
x = (0,0,0,0,0,1,0), z =
Iteration 2 starts from this solution and examines all solutions
obtained by unit changes of each variable. The best for iteration
x = (0,0,0,0,0,2,0), z =
In a similar manner, iteration 3 starts from
the best solution of iteration 2 and finds the improved solution:
x = (0,0,0,0,1,2,0), z =
Iteration 4 starts from the best solution of
iteration 3 and finds the improved solution:
x = (0,0,0,0,2,2,0), z =
Iteration 5 cannot improve on this solution and
the greedy method terminates. Run 37 simply replaces the current
solution with the best of the 36 previous runs.
At each iteration tries to improve the best of the previous
iteration. When an improving move cannot be found the methods
The best solution found happens to be the optimum determined
by exhaustive enumeration, however the greedy process only requires
37 solutions evaluations while exhaustive enumeration required
over 2000. Of course this fortunate result cannot be guaranteed.
The number of solutions evaluated depends on the parameters
of the problem, but the effort grows polynomially with the size
of the problem.
We have illustrated the greedy solution applied to the math
programming model. The method only uses the objective value
to select the improving variable. Feasibility is considered
by adding a penalty for solutions that violate the constraints.
The values of the constraint coefficients for the variables
do not affect the choice of the improving variable.
A solution obtained with greedy enumeration can be improved
by performing the improvement
procedures described on the next page.