In addition some constraints of the following type are added. Consider a subset S ofV and letT ⊂E be a spanning tree onS. Then the following constraints are valid.
This is a generalization of (5). For|S|equal to 3, these constraints are used in the cutting plane algorithm. During each iteration, the constraints are evaluated and, if violated, added.
G.4 A Column Generation Model
In this section an alternative model of the HLCND problem is considered. A variable exists for each possible cluster and each possible backbone. Since there are an exponential number of these variables, the model is solved using column generation. To explain the model, a substantial number of constants and vari-ables need to be defined and thus a short example is given to ease understanding.
The paper [8] solves a clustering problem by using column generation in much the same way as we suggest for the HLCND. The subproblem in the column generation approach suggested in [8] is the quadratic knapsack problem. In case of the HLCND, it turns out that the subproblems in the column generation approach can be solved by solving a series of quadratic knapsack problems.
Thus, methods developed for the quadratic knapsack problem are used.
Let C be the set of all feasible clusters with a hub selected and B be the set of all backbone networks, i.e. each backbone is a set of hubs. For the clusters, three types of constants are defined, aci, ace, and hci. The constant aci is 1 if node iis in cluster c, otherwise 0 andace is 1 if both endpoint nodes of edgee are in cluster c, otherwise 0. The constanthci is 1 if node iis hub in cluster c, otherwise 0.
Two types of constants are defined for the backbone, abi andabe. Similarly to the cluster variables,abi is 1 if nodei is in backboneb, otherwise 0 and abeis 1 if both endpoint nodes of edge eare in backboneb, otherwise 0.
Figure G.2 gives an example of a network with clusters and hubs indicated. The two clusters give rise to two columns, denotedc1 andc2, and similarly the two hubs correspond to a backbone network column denotedb1.
For cluster c1, the constantsac11,ac21 andac31 are 1, since nodes 1, 2, and 3 are
168 Appendix G
Figure G.2: An example with clusters and hubs indicated.
in the cluster. The constants ac121, ac131 and ac231 are 1 since these links may be in the cluster. Finallyhc31 is 1, since node 3 is hub. Remaining constants for clusterc1are 0.
For cluster c2, the constants ac42, ac52 are 1, since nodes 4 and 5 are in the cluster. The constantac452 is 1, since the link between 4 and 5 may be in the cluster. Finally hc42 is 1, since node 4 is hub. Remaining constants for cluster c2 are 0.
For the backboneb1,ab31 andab41 are 1 since nodes 4 and 5 are in the backbone.
Alsoab341 is 1 since node 3 and 4 are in the backbone, and remaining constants for the backbone are 0.
Note that in defining the link constants, there is no indication as to whether a link is actually selected. The definition only considers whether the endpoint nodes of a link is in the cluster. In the example, the three links in cluster c1
are possible to select, thus the corresponding constants are one, but when the network is designed they may not be included in the optimal solution.
Two types of variables are used, one type for the clusters and one for the back-bone. Let uc, cin C be 1 if cluster cis selected, 0 otherwise andvb,b inB be 1 if backboneb is selected, 0 otherwise. The model for the HLCND problem is then as given in the following.
minX
G.4 A Column Generation Model 169
The core of the formulation is the three constraints (13), (14), and (15). Con-straints (13) ensure that each node is in exactly one cluster and conCon-straints (14) ensure that nodes that are hub nodes of a selected cluster are in the back-bone network. In addition to selecting clusters and the backback-bone, it has to be ensured, that links are only established between nodes within clusters or in the backbone. This is ensured by Constraints (15). Finally constraint (16) ensures that exactly one backbone network is selected. This constraint is not necessary but strengthens the linear programming relaxation. The dual vari-ables corresponding to each type of constraint are indicated in brackets after the constraints.
Two column generation problems are now apparent, one for the cluster columns, uc and one for the backbone columns,vb. These are described in the following.
G.4.1 The Cluster Generation Problem
For an optimal solution and thus a set of values for the dual variables, the reduced cost of auc column is the following.
−X
The column generation subproblem seeks the column with the most negative reduced cost, or equivalently, has the following objective:
maxX
In this objective,ai,ae, and hi are binary variables representing whether node iis in the cluster, edge eis in the cluster, and nodeiis hub, respectively. The following constraints ensure that feasible clusters are generated.
X
i∈V
hi= 1 (20)
170 Appendix G
Exactly one hub has to be determined, which is ensured by constraint (20).
Furthermore, constraint (21) ensure that bounds are enforced on the number of nodes in the cluster. Consistency between the variables is ensured by the remaining constraints. Constraints (22) ensure that a node is selected if it is the hub. The connection betweenai and ae is established by constraints (23) and (24), and finally constraints (25) ensure that all variables are integer.
Instead of solving the problem directly, a series of problems are solved. This has the beneficial side-effect that more than one column is usually being generated per iteration. Thehi variables are fixed one at a time and the bounds on the cluster size is fixed to each of [vmin, vmin+ 1, . . . , vmax] in turn. Thus in total
|V|(vmax−vmin+ 1) problems are solved.
Fixing these values has the consequence that one node is mandatory (and the hub) and the number of nodes in the cluster is fixed. Assume the node fixed to be hub is denotedk and that the cluster size is fixed tovk. Given this, the problem that has to be solved is the following:
maxX
Except for constraint (28) and the fact that constraint (27) is an equation rather than an inequality, this problem is the quadratic knapsack problem(QKP) [1].
However, by replacingak by a sufficiently high constant, by adding a sufficiently
G.4 A Column Generation Model 171
high value to all constants, such that all constants are non-negative, and by replacing constraint (27) by an inequality, the problem can be solved as a QKP.
The code developed and described by Caprara, Pisinger, and Toth in [1] has been used to do the computations. The generated cluster columns are added if the reduced cost is negative, which corresponds to that the objective value is positive. The algorithm used to generate clusters is shown in figure G.3.
forh∈V
forvk =vmin tovmax
Solve the QKP with vk as bound andhmandatory.
If the solution has a positive value add the corresponding cluster column.
Figure G.3: The cluster generation algorithm.
G.4.2 The Backbone Generation Problem
Similarly to the cluster generation problem, the following model is obtained for generation of backbone columns. In the model, ai and ae are binary vari-ables representing whether node iis in the cluster and edgeeis in the cluster, respectively.
maxX
i∈V
βiai+X
e∈E
γeae+δ (32)
s.t. cmin≤X
i∈V
ai≤cmax (33)
ae≤ai e∈E, iendpoint ofe (34) ai+aj≤ae+ 1 e∈E,(i, j) =e (35) ai∈ {0,1},ae∈ {0,1} (36)
Constraint (33) enforces bounds on the number of nodes. Consistency between variables is established by constraints (34) and (35). Finally constraints (36) ensure that the variables are integer.
The bounds on the number of nodes in the backbone is fixed to [cmin, cmin+ 1, . . . , cmax] in turn. Each of the cmax−cmin+ 1 problems are then solved as
172 Appendix G
QKPs. The generated backbone columns are added if the reduced cost is neg-ative, corresponding to that the objective is positive. The backbone generation algorithm is shown in figure G.4.
forck =cmin tocmax
Solve the QKP with ck as bound.
If the solution has a positive value
add the corresponding backbone to the master.
Figure G.4: The backbone generation algorithm.
Solving the QKPs optimally is time consuming. However, since good heuristics exist for the QKP, these are used first, and when no heuristic solutions can be obtained, the optimal method is invoked. This is done for both the cluster and backbone generation algorithm. The heuristic developed in [1] is used.
In addition to generation of the cluster and backbone columns, thexvariables are priced in the same manner as for the cutting plane algorithm described in Section G.3. Also, similarly to the cutting plane algorithm, all of the con-straints (2) and (3) are not included initially, but added when needed.