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 function.

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 is presented.

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.

The remainder of the combinatorial cells constructed by the add-in are shown below after exhaustinve 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 command from the menu initiates exhaustive enumeration. The optimum solution has x6 = x7 = 2, and all others equal to 0.

During the search 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.

Any of the search methods can be applied to the model by simply selecting the method in the search dialog. Of course options such as greedy search or random search may yield a solution in fewer iterations, but the solution found may not be optimum. Note that we are using combinatorial search rather than math programming to solve the problem. The math programming add-in simply provides a convenient structure on which to define the model.

To perform a greedy approach, select Greedy from the Search dialog.

For the general model the greedy solution starts with the solution presented in the value row (row 8). We use all 0's for the example. Each variable in turn is increased by 1 unit and the variable yielding the best objective value is the first greedy selection. That variable is changed and the process repeats. At each step all variables are inspected and the variable showing the greatest objective value increase is increased or decreased by 1 unit. The process continues until no improving steps are found. This is a greedy solution because once a variable is changed it is not allowed to return to a previously held value. The combinatorial form and math programming model with final solution for the example is below. The list shows the feasible solutions generated by the greedy procedure.

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. These are described on the next page.