COMP4041-LDO Workshop 8 Multi-objective Optimization
Purpose: Apply various approaches to find trade-off solutions to multi-objective optimization problems.
Consider the following 2-objective optimization LP model. Solve this model first to optimize objective Z1 and then to optimize objective Z2. This should produce the two extreme trade-off solutions. That is, one solution with the optimal Z1 but the worst Z2 and another solution with the optimal Z2 but the worst Z1. Make sure to take note of the solutions obtained.
Maximize : Z1 = 0.04×2 + 0.045×3 + 0.055×4 + 0.07×5 + 0.105×6 + 0.085×7 + 0.092×8
Minimize: Z2 =12(0.005×2 +0.04×3 +0.05×4 +0.075×5 +0.1×6 +0.1×7 +0.1×8)
Subjectto: x1 +x2 +x3 +x4 +x5 +x6 +x7 +x8 =250 (1) x1 24.2 (2) x1 +0.995×2 +0.96×3 +0.9×4 +0.85×5 99.3 (3) xi 12.5 foralli=2,…7, (4) x8 75 (5) xi 0 foralli=1,2,…8, (6)
Now you should solve the problem from Step 1 using a weighted sum approach in order to obtain a set of trade-off solutions. For this, instead of optimizing only Z1 or Z2, you should optimize a weighted sum of the two objectives as follows:
Maximize: W1×Z1 – W2×Z2
Using this approach, solve the problem for various combinations of W1 and W2. The aim is to obtain a handful of efficient solutions. That is, each efficient solution will represent a trade-off between the two objectives.
Warning: there is no ‘recipe’ for setting values for the weights. In fact, this is one of the difficulties of using a weighted sum approach. For this problem you might want to first try W1=1 and W2=1 to see what solution is produced. Then try other values aiming to obtain a few trade-off solutions in addition to the two found in Step 1. For example, you could try to find at least the 4 efficient points shown in the graph below where the horizontal axis is Z1 and the vertical axis is Z2. Make sure to take note of the solutions obtained and the weights used.
Now you should solve the problem from Step 1 using a Lexicographic approach in order to obtain at least 10 efficient solutions (perhaps including the ones found in the previous two steps) that are also reasonably well distributed in the efficient frontier or trade-off surface. Note that the 4 efficient solutions shown in the above graph are not well distributed.
For this Lexicographic approach, calculate 10 (or more) values for Z1 that are uniformly distributed within the range of values for Z1. This range is given by the two extreme trade-off solutions found in Step 1. Then, for each of these values add a constraint to the model so that Z1 ≥ value and then solve the model to optimize Z2. This process should allow you to find 10 (or more) efficient points well distributed in the trade-off surface of the objective space like in the graph below where the horizontal axis is Z1 and the vertical axis is Z2.
Now you should solve the problem from Step 1 using a Goal Programming approach. For this, two deficiency variables should be added to the model and the objectives Z1 and Z2 become constraints in the model. See the lecture notes for details of how to formulate a goal programming version of the LP model.
Use your goal programming model to fill the following table. Each row corresponds to a set of goals. You should find the values of the deficiency variables and the actual
values for the objectives when solving the problem for those goals. Reflect on how to determine which of these points corresponds to an efficient solution.
Z1 Goal (at least) 18.5 15.6
Z2 Goal (at most) 8.5 7.5
Z1 Z2 (obtained) (obtained)
Consider the following assignment optimization problem.
BI-OBJECTIVE SALESMEN Problem
The manager of a company wants to distribute 18 salesmen over the 4 branches of the company. For each salesman, the company has estimated the sales that the person would generate in each of the branches when the salesman is assigned to that branch. The table Estimated Sales gives the estimated sales per branch for each salesman. For example, if salesman 1 is assigned to branch B, the expected individual sales for that salesman is 16. Also, each salesmen has expressed their preference for being assigned to each of the branches. The table Satisfaction Factors gives these preference values, the higher the better. Each salesman has to be assigned to exactly 1 of the branches, that is, a salesman cannot work simultaneously in more than 1 branch. Also, each of the branches should get at least 2 salesmen assigned. The data for this problem is provided in the spreadsheet for this workshop.
a) The manager wants to know exactly to which branch each salesman should be assigned in order to maximize the overall expected sales.
b) The manager also wants to know the assignment to maximize the overall satisfaction.
c) Then, the manager wants to know if maximizing the sum of these two objectives would give an overall optimal solution, i.e. a solution that dominates the two solutions found in a) and b).
d) Finally, use any of the approaches from Steps 2, 3 or 4 in order to obtain 5 trade- off solutions that are also efficient solutions to this bi-objective optimization problem.