We use the general model given below for the combinatorial optimization problem. The problem can be expressed as either maximum or minimum. This model structure is implemented in the Optimize add-in. We illustrate the model below using linear-integer programming (IP). We also refer to other combinatorial problems that are described in detail on the following pages.

This model places very few limitations on the the model components. Since the principal methods of solution involve enumeration there is no need to restrict the functions involved. Special cases of the model will add restrictions, and the solution methods for the special cases depend on these restrictions.

A solution x is a vector of integers. For a spreadsheet application, the individual solution components may be cells anywhere on the worksheet, usually arranged for convenience related to the application. A solution is a member of the solution space X. The discrete solution space X is defined using mathematical relations that members of the set must satisfy. The number of solutions in the solution space is finite. An example is below where the solution vectors are restricted to integers between lower and upper limits. This is the restriction for IP.

The definition of X is very important for our models, because it will be different for different classes of problems. For a permutation problem, X is the set of all permutations of n integers. For the traveling salesman problem it is the set of all tours through n cities. The definition of X might also include combinatorial constraints that limit individual components of x or combinations of components. The delineation of the set X determines the number of solutions that must be enumerated or partially enumerated in the search for the optimum.

The objective function, f(x), is a single real number and the measure by which alternative solutions are compared.

This function will be evaluated in a single worksheet cell, but it may be the result of computations performed in many cells and even on several worksheets in a workbook. For the general model, no specific form is specified for f(x), but it is important that its value be unique for a given x. The function must also be computable for all x in the solution space. By computable we mean that it contains no errors such as dividing by zero, taking the square root of a negative number, or using circular cell references. These errors are easy to make on a spreadsheet.

For the IP, the objective function is a linear function.

G is the set of solutions that are feasible. Many applications have several separate logical relations that must all be satisfied (logically TRUE) if the solution is feasible. Logical relations are easy to express on a spreadsheet. The expressions involved in G must be computable for all solutions in X.

Considering again an IP, the components of G come from linear constraints. The following shows the development for "less than or equal to" constraints. A similar development follows for "equality" and "greater than or equal to" constraints.

The optimum solution is the feasible solution that minimizes (or maximizes) the objective over all feasible solutions in the solution space.

Although X and G both limit the set over which the optimum is to be found, in our solution methods X is the most important. We will search the solutions delimited by X, but only consider for optimality those solutions that are feasible, members of G. The process of generating solutions from the set X is embodied in the solution algorithm for each special type of problem, so only members of X are generated.

Problem Types

We identify a problem type by its decisions and the space from which the decisions are to be drawn. For each case a solution is given by a vector of integer variables.

We consider four problem types identified by their solution spaces. More detail and examples are on the following pages.

Range
Permutation
TSP
Tree

Finding Solutions

In general our goal is to find the feasible solution in X that maximizes or minimizes the objective function. Much OR research and practice and many commercial products related to OR have been dedicated to this task for special classes of problems.

Some problems such as minimal spanning tree, shortest path tree and others have very efficient algorithms for finding optimum solutions. There are many papers describing faster and faster algorithms for solving these problems. We call these the easy problems. Other problems such as the traveling salesman and most sequencing problems are very difficult in that there are problems of moderate size that cannot be solved on today's high-speed computers and probably never will be solved. We call these the hard problems. We discuss the difference between easy and hard problems on the next page.

Hard problems are usually solved by enumeration of the solution space. In the most general case, exhaustive enumeration of all solutions is necessary to find the optimum. Although practical for small problems, this method becomes impossible for problems of only moderate size. For some kinds of problems, implicit enumeration methods may provide optimum solutions for larger problems. These include the branch and bound methods of integer programming and discrete dynamic programming. Implicit enumeration considers all solutions, but large subsets are eliminated by numerical tests that assure that the optimum cannot lie in the eliminated subsets.

The approach taken in our add-ins is primarily based on either exhaustive or partial enumeration. Partial enumeration searches a relatively small proportion of the solution space using heuristics. A solution obtained through heuristics is sometimes a good solution, but it cannot be claimed as optimum. It is often the best one can do for practical problems.

The heuristics used by the add-ins include greedy heuristics, random solution generation and improvement heuristics. These are only introductory to a large number of heuristic methods considered in the literature including Tabu Search, Simulated Annealing, Genetic Algorithms and others.

Excel Model

The Optimize add-in builds a form on the Excel worksheet that holds components of the combinatorial optimization model. The form is illustrated below for a problem of selecting the numbers of servers for the six stations of a queuing network. This is a nonlinear optimization problem with integer variables. For this application, the number of stations is limited to 20. The details of the model are at this link. The components of the model described above are represented on the form. The model is of the Range type. Formulas for the model refer to cells not shown in the figure. They compute values that are particular to the application.

Cell O3 holds the direction of optimization and cell O4 holds the formula computing the objective value, f(x). Cell Q4 holds the function that computes the total infeasibility of a solution. Its value is 0 for a feasible solution and positive for an infeasible one. Cell Q3 holds the value of the logical expression defining G. Q3 evaluates as TRUE if the content of Q4 is 0. Range M8:R8 holds the solution, and ranges M9:R9 and M10:R10 hold the lower and upper limits respectively.

The type of problem in cell M5, here General (the designation of the Range type), specifies the characteristics defining the set X. The solution algorithm, indicated in cell M4 as Exhaustive, will enumerate all solutions in X and report the best solution found. Since all solutions are enumerated, this is the optimum solution.

The formulation on this page places very few restrictions on how the objective function is computed, how the solution space is defined or how the feasibility conditions are written. Solution methods applicable to the COP return the optimum for only very small problems. Rather, heuristic methods are used to search in the solution space. For most problems the quality of the final solution depends on how much time is spent looking for it.

On the following pages we provide models for a variety of combinatorial problems using the COP model.