IBM ILOG Solver User's Manual > More on Solving > Limits and Problem Decomposition: Locating Warehouses > Suggested answers > Exercise 3

Exercise 3

 INDEX Gray bullet PREVIOUS NEXT

Modify the program in this lesson to use the data file YourSolverHome/examples/data/store_ex3.dat. This data file contains information for 30 stores and 15 warehouses. The ten additional potential warehouse sites are: Munich, Barcelona, Prague, Dublin, Madrid, Lisbon, Berlin, Amsterdam, Brussels, and Milan.

Suggested Answer

You can view the complete program online in the file YourSolverHome/examples/src/storecpx_ex3.cpp. You only need to change the following line of code to add the additional warehouse sites to the enumeration:

const char* Suppliers[] = {"Bonn", "Bordeaux", "London", "Paris", "Rome",
                           "Munich", "Barcelona", "Prague", "Dublin", "Madrid",
                           "Lisbon", "Berlin", "Amsterdam", "Brussels", 
"Milan"};

You change the following line of code to use the new data file:

      fileName = "../../../examples/data/store_ex3.dat";

The results will vary depending on platform, machine, configuration, and so on. 

------------------------------
Solution:
Store  0 Warehouse:  Lisbon
Store  1 Warehouse:  Barcelona
Store  2 Warehouse:  Barcelona
Store  3 Warehouse:  Munich
Store  4 Warehouse:  Rome
Store  5 Warehouse:  Munich
Store  6 Warehouse:  Bonn
Store  7 Warehouse:  London
Store  8 Warehouse:  Berlin
Store  9 Warehouse:  Barcelona
Store  10 Warehouse:  Paris
Store  11 Warehouse:  Bordeaux
Store  12 Warehouse:  Bonn
Store  13 Warehouse:  Bordeaux
Store  14 Warehouse:  Lisbon
Store  15 Warehouse:  Munich
Store  16 Warehouse:  Bonn
Store  17 Warehouse:  Munich
Store  18 Warehouse:  Berlin
Store  19 Warehouse:  Barcelona
Store  20 Warehouse:  Bordeaux
Store  21 Warehouse:  Bonn
Store  22 Warehouse:  Paris
Store  23 Warehouse:  Prague
Store  24 Warehouse:  Barcelona
Store  25 Warehouse:  Munich
Store  26 Warehouse:  Munich
Store  27 Warehouse:  Bonn
Store  28 Warehouse:  London
Store  29 Warehouse:  Lisbon
 
Store  0 Cost:  2
Store  1 Cost:  15
Store  2 Cost:  8
Store  3 Cost:  1
Store  4 Cost:  4
Store  5 Cost:  1
Store  6 Cost:  1
Store  7 Cost:  13
Store  8 Cost:  6
Store  9 Cost:  22
Store  10 Cost:  2
Store  11 Cost:  5
Store  12 Cost:  11
Store  13 Cost:  15
Store  14 Cost:  10
Store  15 Cost:  11
Store  16 Cost:  1
Store  17 Cost:  10
Store  18 Cost:  5
Store  19 Cost:  22
Store  20 Cost:  8
Store  21 Cost:  1
Store  22 Cost:  9
Store  23 Cost:  19
Store  24 Cost:  22
Store  25 Cost:  1
Store  26 Cost:  1
Store  27 Cost:  10
Store  28 Cost:  19
Store  29 Cost:  2
 
Total cost:  557
------------------------------
------------------------------
Number of fails               : 5
Number of choice points       : 39
Number of variables           : 526
Number of constraints         : 526
Reversible stack (bytes)      : 76404
Solver heap (bytes)           : 361824
Solver global heap (bytes)    : 24144
And stack (bytes)             : 4044
Or stack (bytes)              : 4044
Search Stack (bytes)          : 4044
Constraint queue (bytes)      : 11160
Total memory used (bytes)     : 485664
Elapsed time since creation   : 0.181

As you can see, the solution is not the same as that found in Chapter 13, Controlling the Search: Locating Warehouses. The total cost is also higher; 557 for using problem limits and decomposition, and 490 for a complete Slice-Based Search. Since the search uses limits, it is not complete and may miss an optimal solution. However, Solver was able to find a solution more quickly. There are fewer fails and fewer choice points. Using problem limits and decomposition, there are only 5 fails and 39 choice points, as opposed to 68,415 fails and 65,840 choice points using Slice-Based Search without problem limits and decomposition. The performance also improved. Using problem limits and decomposition, Solver found the solution in 0.181 seconds, compared to 86.835 seconds using Slice-Based Search without problem limits and decomposition. (Solution time varies depending on platform, machine, and so on.) This demonstrates the importance of choosing good search strategies, especially as problem size and complexity increase.

Here are the results using Slice-Based Search without problem limits and decomposition from Chapter 13, Controlling the Search: Locating Warehouses: 

Using default file
Cost to build a warehouse:
30
Relative costs for stores:
[[20, 24, 11, 25, 30, 28, 27, 82, 83, 74,
2, 55, 73, 69, 61], [28, 27, 82, 83, 74, 93, 15, 63, 87, 46,
47, 57, 55, 71, 95], [74, 97, 71, 96, 70, 42, 8, 29, 67, 59,
93, 15, 63, 87, 46], [2, 55, 73, 69, 61, 1, 65, 73, 59, 56,
93, 35, 19, 85, 46], [46, 96, 59, 83, 4, 42, 22, 56, 67, 59,
11, 73, 15, 43, 96], [42, 22, 29, 67, 59, 1, 5, 57, 67, 56,
42, 8, 29, 67, 59], [1, 5, 73, 59, 56, 1, 5, 73, 59, 56,
42, 8, 29, 67, 59], [10, 73, 13, 43, 96, 42, 22, 56, 67, 59,
42, 56, 29, 56, 59], [93, 35, 63, 85, 46, 13, 22, 29, 66, 59,
65, 6, 73, 59, 56], [47, 65, 55, 71, 95, 42, 22, 29, 69, 59,
93, 25, 45, 85, 46],
[17, 19, 67, 2, 15, 93, 35, 19, 85, 46,
47, 57, 55, 71, 95], [26, 5, 78, 43, 19, 10, 15, 13, 9, 96,
68, 35, 62, 85, 46], [11, 73, 15, 43, 96, 42, 56, 29, 56, 59,
47, 57, 55, 71, 95], [93, 15, 63, 87, 46, 93, 55, 63, 92, 46,
47, 65, 55, 92, 95], [47, 65, 37, 71, 95, 47, 65, 45, 71, 95,
10, 73, 58, 43, 96], [42, 22, 29, 67, 49, 11, 45, 13, 43, 96,
42, 56, 29, 56, 59], [1, 5, 73, 59, 56, 47, 65, 45, 71, 95,
68, 35, 62, 85, 46], [10, 75, 13, 43, 62, 10, 15, 13, 9, 96,
93, 35, 19, 85, 46], [93, 25, 45, 85, 46, 65, 6, 73, 59, 56,
12, 5, 92, 59, 56], [47, 65, 55, 92, 95, 42, 22, 29, 69, 59,
47, 57, 55, 71, 95],
[42, 8, 29, 67, 59, 93, 35, 89, 85, 46,
47, 65, 56, 71, 95], [1, 5, 57, 67, 56, 42, 22, 56, 67, 5,
65, 6, 73, 59, 56], [10, 15, 13, 9, 96, 42, 22, 29, 69, 59,
47, 57, 55, 71, 95], [68, 35, 62, 85, 46, 93, 35, 19, 85, 46,
47, 57, 55, 71, 95], [47, 57, 55, 71, 95, 42, 22, 29, 69, 59,
93, 25, 45, 85, 46], [42, 22, 29, 69, 59, 1, 65, 73, 59, 56,
93, 35, 19, 85, 46], [1, 65, 73, 59, 56, 1, 65, 73, 59, 56,
93, 35, 19, 85, 46], [10, 73, 13, 83, 96, 11, 45, 13, 43, 96,
42, 56, 29, 56, 59], [93, 35, 19, 85, 46, 93, 35, 19, 85, 46,
47, 57, 55, 71, 95], [47, 65, 45, 71, 95, 28, 27, 82, 83, 74,
2, 55, 73, 69, 61]]
Warehouse capacities:
[5, 9, 12, 3, 4, 6, 8, 1, 6, 11,
3, 10, 8, 9, 3]
 
------------------------------
Solution:
Store  0 Warehouse:  London
Store  1 Warehouse:  Barcelona
Store  2 Warehouse:  Barcelona
Store  3 Warehouse:  Munich
Store  4 Warehouse:  Lisbon
Store  5 Warehouse:  Munich
Store  6 Warehouse:  Bordeaux
Store  7 Warehouse:  London
Store  8 Warehouse:  Munich
Store  9 Warehouse:  Barcelona
Store  10 Warehouse:  Bordeaux
Store  11 Warehouse:  Bordeaux
Store  12 Warehouse:  London
Store  13 Warehouse:  Bordeaux
Store  14 Warehouse:  Lisbon
Store  15 Warehouse:  Munich
Store  16 Warehouse:  Bordeaux
Store  17 Warehouse:  London
Store  18 Warehouse:  Barcelona
Store  19 Warehouse:  Barcelona
Store  20 Warehouse:  Bordeaux
Store  21 Warehouse:  Bordeaux
Store  22 Warehouse:  London
Store  23 Warehouse:  Bordeaux
Store  24 Warehouse:  Barcelona
Store  25 Warehouse:  Munich
Store  26 Warehouse:  Munich
Store  27 Warehouse:  London
Store  28 Warehouse:  London
Store  29 Warehouse:  Lisbon
 
Store  0 Cost:  11
Store  1 Cost:  15
Store  2 Cost:  8
Store  3 Cost:  1
Store  4 Cost:  11
Store  5 Cost:  1
Store  6 Cost:  5
Store  7 Cost:  13
Store  8 Cost:  13
Store  9 Cost:  22
Store  10 Cost:  19
Store  11 Cost:  5
Store  12 Cost:  15
Store  13 Cost:  15
Store  14 Cost:  10
Store  15 Cost:  11
Store  16 Cost:  5
Store  17 Cost:  13
Store  18 Cost:  6
Store  19 Cost:  22
Store  20 Cost:  8
Store  21 Cost:  5
Store  22 Cost:  13
Store  23 Cost:  35
Store  24 Cost:  22
Store  25 Cost:  1
Store  26 Cost:  1
Store  27 Cost:  13
Store  28 Cost:  19
Store  29 Cost:  2
 
Total cost:  490
 
 
------------------------------
Number of fails               : 68415
Number of choice points       : 65840
Number of variables           : 526
Number of constraints         : 526
Reversible stack (bytes)      : 104544
Solver heap (bytes)           : 361824
Solver global heap (bytes)    : 4584576
And stack (bytes)             : 4044
Or stack (bytes)              : 4044
Search Stack (bytes)          : 4044
Constraint queue (bytes)      : 13164
Total memory used (bytes)     : 5076240
Elapsed time since creation   : 86.835
© Copyright IBM Corp. 1987, 2009. Legal terms. PREVIOUS NEXT