COMP4041-LDO Workshop 7 Packing, Routing and Sequencing Problems
Purpose: Write and solve BIP models for some packing, routing and sequencing optimization problems with Excel, LP-Solve and OpenSolver.
The Excel file for this workshop contains a spreadsheet with the data for an instance of the GENERALISED ASSIGNMENT problem with N=15 tasks and N=5 workers Develop the spreadsheet and LP-Solve models to solve this problem. Caution: think how speed up typing the considerable number of decision variables in LP-Solve. Some suggestion will be given during the workshop.
The data for an instance of the GENERALISED ASSIGNMENT problem with N=60 tasks and N=10 workers is available in Moodle. You can import the data in Excel using Data¡úGet Data¡úFrom File. Develop the spreadsheet model to solve this problem. Developing the LP-Solve model is not required unless you want to do it. Note: after completing step 1, this step should be straightforward, so you might want to use the workshop session for the other steps.
The Excel file for this workshop contains two spreadsheets for a BIN PACKING problem with N=12 items and M=6 bins each of capacity B=1. The non-linear model is complete. Try solving this non-linear model with the three different solving methods (Simplex LP, GRG Nonlinear and Evolutionary) in the Excel solver. Then, following the algebraic formulation given in the lecture, complete the linear model to solve this problem. Compare the time taken by the Excel solver and by OpenSolver to solve the linear model.
The spreadsheet for this workshop includes a non-linear model for an asymmetric TSP with N=6. Implement the linear version of the spreadsheet model, see slides 25-28 of the Lecture 7 notes. Verify whether subtour breaking constraints are needed for the linear model and whether solvers get the correct optimal solution for both linear and non-linear versions.
Develop the optimization model in Excel and/or LP-Solve to solve the following optimization problem.
WIREHOUSE Problem
The Wirehouse company wants to place 8 groves of trees within some land area. Therefore, it must develop a system of roads that makes each grove accessible from every other grove. The distance between every pair of groves is given in the table
(see the workshop spreadsheet). The two separate problems are to a) determine between which pairs of groves the roads should be constructed to connect all groves with the overall minimum total length of road, and b) determine the roads to be constructed allowing a tour to visit all the groves exactly once.
Step 6 (Optional, Not Included in the Test)
The Excel file for this workshop contains the spreadsheet with the data for a BIN PACKING problem with N=120 items and M=60 bins of capacity B=150. Develop the spreadsheet model to find the optimal solution to this problem.
Warning: this is a considerably difficult problem to solve, you might want to solve first with lower integer precision and then solve again with higher precision once you have an estimation of the time required to solve the model. The integer precision is set with the parameter Integer Optimality % in the Excel solver and with the parameter Branch and Bound Tolerance % in the Open Solver. The highest integer precision is when the parameter is set to 0% but this also makes the solver to take longer to solve the model. Lower integer precision (e.g. 20%) means faster computation but it could result in the solver not finding the global optimal solution, but a local optimum instead. Then, the aim is to set the lowest integer precision parameter that achieves the best-known number of bins. The maximum computation time can be set in the solver parameter options. Can you obtain a better solution than the best known with 48 bins?