Computation - Operations Research Models and Methods

Computation

Combinatorics


IP Tour

Download

	Combinatorics

The Combinatorics add-in builds models for specific combinatorial problems. It is to be used with the Optimize add-in that provides most of the form building and search algorithms. An advantage of the Combinatorics add-in is that it constructs graphical maps for problems defined on the Euclidean plane.

The Combinatorics menu is shown at the left. At this time there are six model types. QAP, stands for the Quadratic Assignment Problem. This is a well studied optimization problem. There is a nonlinear-integer programming model for the problem, but we use a combinatorial representation that is much easier to implement with Excel. We solve the problem with the search methods of the Optimize add-in. The exhaustive enumeration approach will yield the optimum for small problems, but it will be necessary to use random search and improvement methods for larger problems. These do not guarantee optimality.

The Spanning Tree, the Shortest Path Tree and the Traveling Salesman (TSP) problems.are also considered by the Optimize add-in through the Add Form command, but here we provide search methods that are much faster, allowing the solution of larger problems in reasonable times. A map display is provided for problems with arc lengths determined by the Euclidean distance measure.

The Sequence problem is the problem of arranging a set of jobs into a sequence that will pass through one or more stages of production. The model includes setup times. A graphic display of the schedule is provided by a Gantt chart.

The Routing Problem is concerned with determining a route for a vehicle that must visit a number of sites. There is a travel time between every pair of sites as well as a time spent at each site. The cost of a route depends on the departure times from the sites as well as the transportation costs between sites. The model allows early and late due times. Violations of the due times are penalized in the cost function. A map display shows the routes graphically. Two options are provided. The first routes a single vehicle and the second routes multiple vehicles. The Routing add-inhas a more extensive model for the routing problem.

The only limits to the size of problems that can be formulated by this add-in are the worksheet limitations of Excel, but for large problems time and memory requirements may be excessive.

The commands shown under the Combinatorics menu item are discussed on the following pages.

QAP: This command is used to create a worksheet and place on the worksheet the combinatorial form for the quadratic assignment problem.
Spanning Tree: Constructs minimal or maximal spanning tree models and provides efficient greedy and improvement algorithms.
Path Tree: Constructs shortest path tree models and provides efficient greedy and improvement algorithms. The models constructed do not solve the longest path tree problem.
TSP: Constructs models for the traveling salesperson problem. The solution algorithms are more efficient with this add-in than those provided in the Optimize add-in.
Sequence: Constructs models for the problem of sequencing a given set of jobs that must pass through one or more stages of production. Processing times are specified for each job in each state. Stage dependent job setup times may also be considered. The goal is to minimize the cost of a sequence or minimize the total time interval between the start of the first job and the completion of the last (make-span).
Routing/Single: Constructs models for the vehicle routing problem. The model allows early and late due times. The objective is to minimize the sum of travel costs and early and late penalties. The Routing add-inhas a more extensive model for the routing problem.
Routing/Multiple: Extends the single vehicle routing problem to allow multiple vehicles with more than one trip. Includes resource constraints that model truck capacity.
Add Buttons: A worksheet model for a combinatorial problem may include buttons. If an Excel workbook containing a model is opened in a different computer than the one that created the model, it will be necessary to select this command to create a new buttons linked to the new computer.
Remove Buttons: This command removes all the buttons created by the Combinatorics add-in.When the buttons are removed, a workbook can be opened in a different computer without encountering an error message about links. Use the Add Buttons command to put the buttons on the worksheets.

Please Note: The Combinatorics add-in uses subroutines from the Optimize add-in, so both must be loaded.