Optimize - Combinatorial Form

To illustrate the process of adding an optimization form we use the Job Shop queuing network example shown below. The example is fully described in the section on the Queues add-in. The Queues add-in also has a new menu item that provides for constrained optimization of queuing models. The network consists of six stations labeled A through F. The system shown below uses the fewest number of servers that yield a stable result with a total of 15 servers used. We want to investigate the effects of adding more servers. The measure of interest is the mean time in the system computed in cell J9. Of course this time can be reduced to its minimum by adding an unlimited number of servers, but here we limit the total number of servers to 20, five more than the minimum. The number in cell J9 is a complicated function of the number of servers involving several formulas. Some user-defined functions provided by the Queues add-in are used in the computation, so Queues add-in must be installed to build and solve this model. If you open this model from the Optimize demonstration file, you must choose the Relink command from the Queues menu before proceeding.

 To begin the analysis, we choose the Add Form command from the menu. The Queues add-in commands appear in the list because that add-in is installed for the example. The dialog below is presented. The form must be placed so it does not disturb the cells describing the queuing network. Cell L2 is to the right of the model. The Name is used by the add-in to provide Excel range names, so it must be a valid Excel name and unique to other names in the workbook. The Number of Variables corresponds to the number of individual queues in the network. We have chosen to minimize the objective value. This problem is of the range type in that we will search over a range for the number of servers for each queue. The initial limits of the range are specified in the Min and Max boxes.

Model

A form is constructed by the add-in and is shown below. We call this the combinatorial form because we use it to optimize the discrete variables in combinatorial problems. In the second figure several of the cells have been changed from their initial values to represent the example.

Initial Form

Form after modifications

The form has 6 columns for the variables holding the values and lower and upper limits for the combinatorial search. We have placed formulas for the lower limits that compute the minimum number of channels for each station. We arbitrarily make the upper limits 2 greater than the lower limits. The value cells in row 8 are colored green to indicate that the program will manipulate these values during the search procedures. Cell M3 holds the name, cell M4 holds the search method that may be changed later, the Problem type appears in M5. We use the General type for the range problem. Cells colored yellow hold information manipulated by the add-in and should not be changed by the user.

Cell O4 holds the direction of optimization and cell O5 holds the formula for the objective function. In this case the formula is simply "=J9", where cell J9 holds the value of the mean time in the system for the queuing network. The cell is colored pink to indicate that the user must provide the formula that links the model to the combinatorial form. Cell O5 does not play a role in this example. When appropriate, this cell will hold the name of a VBA subroutine that is called as part of the evaluation process. For MIP, network or transportation models it will hold the names LP/IP, Network or Solver. For layout problems cell O5 holds the name of the layout solution subroutine.

We have added cells R12 and R13 to describe the constraint on the total number of servers. R11 computes the total as the sum of the values in row 7 and R12 holds the upper limit. Cells R12 and R13 are not part of the combinatorial form, but were added after the form was constructed. Cell Q4 is created by the add-in to hold a Boolean expression that indicates whether the current solution is feasible. In other situations this cell can use very complex computations to determine feasibility, but in this case we want the cell to indicate TRUE (feasible) whenever the total number of servers is less than or equal to 20 and FALSE (infeasible) otherwise. The easiest way to do this is by the logical expression:

=Q4=0

This expression returns TRUE whenever the contents of cell Q5 is 0, and false otherwise. The add-in uses the cell Q5 to provide a numeric measure of infeasibility. In this case we place in Q5 the expression:

=MAX(0, R11-R12)

This expression is 0 for feasible solutions and positive for infeasible solutions.

The next important step of preparation is to link the variables of the queuing model with the variables on the combinatorial form. To do this we place formulas for the Number of Servers that link the enumeration variables to the model variables. This is easily accomplished by typing "=M7" in cell C6 and using fill right for the remainder of the row.

Exhaustive Enumeration

 To initiate the search, we choose Search from the menu. The dialog below is presented. The program places the name of a combinatorial form on the active worksheet in the name field. If there is more than one form on the worksheet, use the Next button to cycle through them. The buttons in the search method area select the method. For the example, we have chosen to enumerate all the solutions within the range.

The program will show the best solutions encountered during the enumeration in a list on the worksheet. Select the desired number in the field provided and click the checkbox if you want them sorted by objective value. At the end of the time limit specified, the program will stop and ask if the process is to continue. Since the enumeration time may be very large, it is good to have this opportunity to terminate the run. The infeasibility weight is not important for exhaustive enumeration, but it plays a role in the other search methods.

After clicking OK, the program computes an estimate of the number of solutions and shows it on a dialog. The user may wish to terminate the process if this number is too large.

The results of the enumeration are shown below. The program places the variable values for each alternative in row 8 and evaluates the solution. A total of 729 solutions are generated. For those that are feasible, the objective function is computed. At termination, the optimum number of servers is displayed in green cells of row 8.

It is important to note that the add-in controls the enumeration process and generates the values of the decision variables. The objective value and feasibility value and state (cells O4, Q4 and Q3 for the example) are computed by arbitrary formulas placed on the worksheet. There are no restrictions on the worksheet model, so the add-in makes no assumptions about linearity or other mathematical characteristics. It is necessary that the objective value and feasibility value and state be computable for at least some of the values of the decisions. Otherwise, the process might be interrupted by an Excel error message.

 In addition to the optimum, a sorted list is placed to the right of the combinatorial form. For the example, the 19 best solutions encountered are shown on the list. The optimum is recomputed at the end of the run and is shown as the 20th solution. The list is often valuable when there are non-quantitative aspects of the problem that would suggest the use of a solution different than the optimum. The example required 46 seconds on the author's computer. The time is proportional to the number of evaluations and the time required for each worksheet computation. The latter depends on the complexity of the worksheet model and the speed of the computer. For the queuing network, there are a number of user-defined functions involved. These take much longer to evaluate that Excel formulas or built-in functions.

Exhaustive enumeration is a very general procedure for combinatorial optimization. There are no restrictions on the format of the objective function other that it be computed by an evaluation of an Excel worksheet or VBA subroutine. Issues such as convexity or continuity are irrelevant and the global optimum solution is always obtained if the process is run to completion. Of course the difficulty with this approach is the exponential growth in the number of solutions with the number of variables and the width of the range for each. Nevertheless many practical problems have low dimensionality and exhaustive enumeration can play an important role.

The other search alternatives may require less computation time but no longer guarantee optimality.

Feasibility

Feasibility plays an important role for many optimization problems. There are two kinds of infeasibility. First a feasible solution must have each of the variables within the ranges specified by the upper and lower limits on the variables (rows 9 and 10 for the example). The exhaustive generation procedure does not generate solutions that fall outside these limits, so keeping the feasible range as small as possible is important to reducing the time of enumeration.

The second kind of infeasibility is represented by the Boolean expression in cell Q3. The contents of this cell can be the result of many complex feasibility conditions. When the cell evaluates as TRUE, the solution is feasible and its objective function is compared with the objective values of other feasible solutions. When the cell evaluates as FALSE, the solution is infeasible and disregarded. Although this feasibility test can be very powerful and important to modeling, it does not reduce the number of solutions that are generated.

The value in cell Q4 measures the amount of infeasibility for an infeasible solution. This cell is not important for exhaustive enumeration unless it determines the value of Q3, as it does in the example. The formula for Q3 could have been easily written so that it not depend on Q4. Then the contents of Q4 would have no effect on the process.

Operations Research Models and Methods
Internet
by Paul A. Jensen