Project topics and materials
Get Complete Project Material File(s) Now! »
Computational study
In order to test the performance of our new formulations for DOMP, we have performed intensive computational tests comparing results with re-spect to previous available formulations of DOMP (see Boland et al. [2006], Dom nguez-Mar n [2003], Nickel [2001], Nickel and Puerto [2005]) and Mar n et al. [2010]).
Description of the test instances
We use two di erent types of instances. First, we consider random instances in which the elements of the cost matrix are integer numbers randomly gen-erated between 10000 and 100000. The second set of instances consists in p-median instances from OR Lib, Beasley [2012].
Regarding the random instances; we vary the number of clients n in ;;;; n consider three possible values for the f10 20 30 40 50g and for each , we n n n number of facilities to be open: p = ; ; : 4 3 2 As for the p -median instances from Beasley’s library, we have selected graphs corresponding to p med1; : : : ; p med20 with up to 400 nodes from the original data. Each set of nodes is divided in two disjoint subsets containing, respectively, the set of clients and the set of facilities. (The reader may observe that in these instances we force these two sets to be disjoint). Next, each cost Cij is computed as the shortest path between client i and facility j in the resulting complete graph induced by the above described set of nodes.
Eight di erent types of -vectors are tested. Their description is provided in Table 2.3. We consider, among others, p-median, p-center, p-k-centrum, p-trimmed mean, random and p- -centdian problems. In the k-centrum case, k = n2 . In the (k1 + k2)-trimmed mean, k1 = k2 = 10n . When is taken as a random vector we generate 5 instances which contain values randomly drawn between 1 and 100. Finally, we use = 0:5 in the centdian case.
Computational results
All our experiments have been carried out on a PC with two Intel Xeon processors with 3.46 GHz and 48 GB of RAM. The models were written in Mosel and solved using Xpress IVE 7.3. To have a clean comparison of our solution approaches, all automatic cuts from Xpress have been disabled. We now report a summary of our computational experiments. Detailed informa-tion can be found in the material included in the Appendix A. In particular, we report results for the di erent types of lambda vectors from Table 2.3. Random allocation costs data sets. Table 2.5 provides a comparison of the LP-relaxations of models DOM P1, DOM P2, DOM P3, DOM P4 and DOM P4\1, averaging for n = 20 and n = 40 and all possible values of p and . The last model DOM P4\1 con-sists in DOM P4 to which constraints (2.7) of DOM P1 have been appended.
Speci cally, we report the integrality gap de ned as GAP = z zLP , where z and zlLP represent the optimal value of DOM Pl and its LP-relaxation, respectively. We observe that the values of the integrality gap vary between 2.29% and 7.34%, obtained in formulations DOM P3 the best and DOM P2 or DOM P1 the worst. In all cases, the LP-gaps are good but specially in formulation DOM P3 which seems to be rather tight. We remark also the small di erence that is obtained adding constraints (2.7) to the formulation DOM P4 in terms of integrality gap. Moreover, we point out that we have ob-tained the same LP-gap with formulations DOM P1 and DOM P2 for all the tested instances. (It is still an open question whether this is also theoretically true.) Thus, from Table 2.5 one could conclude that the best formulation is DOM P3. In spite of that, the large number of inequalities (O(n3)) used in the model makes it rather slow whenever the number of clients n is of moderate size (n > 50). In order to de ne a solution approach which presents the best perfor-mance, we have conducted a preliminary computational test with instance sizes n = 10; 20; 30. Our rst strategy consists in solving DOM P3 with a pure branch-and-bound. Our second strategy, DOM P4\1(B&B), solves DOM P4\1 with a pure branch-and-bound. The third approach, DOM P4\1 (B&C 3), starts by solving the LP-relaxation of DOM P4 and then adds inequalities (2.7) at the root node and order constraints (2.21) as long as they are violated by the current solution of the LP. The reader may observe that both families of inequalities are cliques in the con ict graph induced by the three index variables of our formulation. Therefore, order constraints could in principle be added by standard clique cuts generation techniques implemented in Xpress. Nevertheless, our own implementation is more e – cient since the separation of the entire family of valid inequalities (2.21) can be performed in O(n3) by sequentially updating the l.h.s. value of the order constraints when switching from a couple ij to the adjacent one in the same position k. The fourth and last strategy DOM P4(B&C 3) is a branch and cut algorithm based upon DOM P4 adding only valid inequalities from (2.21).
Table of contents :
1 Introduction and State of the art
1.1 Location theory
1.1.1 The Ordered Median Problem
1.2 Combinatorial optimization
1.3 Column generation
1.3.1 Linear programs
1.3.2 Mixed Integer Linear Programs
1.3.3 Column Generation on Location Problems
2 New formulations and comparative study for DOMP
2.1 Introduction
2.2 The problem and some formulations
2.2.1 Three-index formulation
2.2.2 Two-index formulation
2.2.3 A new formulation for DOMP
2.2.4 An aggregated formulation
2.3 Theoretical results
2.3.1 Comparison of formulations
2.3.2 On the polytope dened by the assignment constraints
2.4 Computational study
2.4.1 Description of the test instances
2.4.2 Preprocessing
2.4.3 Computational results
3 A Branch-and-Cut-and-Price procedure for the discrete ordered median problem
3.1 Introduction
3.2 The problem and its formulation
3.3 Column generation to solve LRMP
3.3.1 Solving the pricing subproblem
3.3.2 Dealing with infeasibility
3.3.3 Stabilization
3.4 Branch-and-cut-and-price
3.4.1 Preprocessing
3.4.2 Initialization
3.4.3 Upper bound for the Master Problem: A GRASP heuristic
3.4.4 Branching
3.4.5 Valid inequalities
3.5 Computational results
3.5.1 Cuts
3.5.2 Comparing with DOMP4(B&C 3)
4 The monotone ordered median problem
4.1 Introduction
4.2 The model by Ogryczak-Tamir (OT)
4.2.1 Further extensions: New formulations for DOMP
4.3 The Blanco-El Haj-Puerto model (BHP)
4.4 Theoretical results
4.5 Computational experiments
5 Conclusions and Future Research
A Supplementary material for the Chapter 2 \New formulations and comparative study for DOMP »
A.1 GAP
A.2 Random instances: CPU times
A.3 Beasley instances: CPU times
B Supplementary material for the Chapter 4 \The monotone ordered median problem »
B.1 Detailed results for comparison between formulations DOMPOTG and DOMP2
B.2 GAP
B.3 Random instances: CPU times (pleriminary study)
B.4 Random instances: CPU times and number of nodes .
