In this paper, we study the problem of partitioning a complete weighted graph into complete subgraphs, each having the same number of vertices, with the objective of minimizing the total edge weights of the resulting subgraphs. This problem, denoted by GPP, is formally stated in Section 1.1 below, and Section 1.2 then presents some motivating examples.

Several graph partitioning problems have been studied in the literature, which are motivated by applications in microaggregation (Domingo-Ferrer and Mateo-Sanz, 2002), political districting (Mehrotra et al., 1998), video clustering (Schaeffer, 2007), telecommunication and VLSI design (Karypis et al., 1999), biological or social networks (Fan et al., 2009), and data mining (Zha et al., 2001). Typically such problems arise in the context of clustering, which is an unsupervised classification and the clusters must sometimes satisfy certain additional threshold criteria (Fan and Pardalos, 2012). The general graph partitioning problem aims to partition the vertex set of a graph into several disjoint subsets with the objective of minimizing the sum of edge weights between the disjoint subsets (Fan and Pardalos, 2010). This is an NP-complete combinatorial optimization problem (Garey et al., 1976) and different techniques were employed to solve it (Hager and Krylyuk, 1999). The case when the graph is partitioned into equal or different by 1 cardinalities for all partitions was solved either by linear programming (Lisser and Rendl, 2003) or semidefinite programming (Karisch and Rendl, 1998; Lisser and Rendl, 2003). Quadratic programming (Hager and Krylyuk, 1999, 2002) and semidefinite programming (Wolkowicz and Zhao, 1996) requires that the cardinalities of all partitions are known a priori. Fan and Pardalos (2010) extended this work by formulating a zero-one quadrating programming problem without the input of cardinalities of the required partitions. The objective of the problem studied in the current paper is to minimize the sum of edge weights of the resulting partitions while that in the general graph partitioning problem is to minimize the sum of edge weights between the disjoint partitions.

In the following, we discuss a number of applications that are addressed using different types of graph partitioning paradigms. Micro-aggregation is a technique used by statistical agencies, where some statistical information needs to be disclosed, while the related specific individual information must remain classified. Published data needs to be therefore presented in a manner such that: (a) the classified data cannot be concluded from the published data, and (b) the deleted unclassified data is minimized. Domingo-Ferrer and Mateo-Sanz (2002) used a graph partitioning approach to solve this problem. Political redistricting is another application of graph partitioning, where boundaries of districts need to be drawn within the states to attain certain characteristics and to avoid partisan political goals. Mehrotra et al. (1998) designed a graph partitioning political redistricting model with the motivation that (a) differences in populations for any two different districts should be minimized in order to adhere to the one-person-one-vote principle; (b) districts should be contiguous, and (c) districts should be geographically compact. Graph partitioning is also used in video scene clustering (Tan and Lu, 2003) to index, browse, and retrieve video data. In this context, a graph G(V,E) is constructed as follows, where each vertex v∈V represents a scene and an edge e∈E between two vertices indicates the similarity obtained from some defined relations of the colours of two scenes. The objective is to partition G with the goal of maximizing similarity in the individual partitions where the number of partitions is not restricted.

In telecommunication technology, graph partitioning is employed to subdivide a transmission network into clusters in order to maximize the routed traffic within the clusters (Laguna, 1994). Park et al. (2000) addressed the problem of clustering a telecommunication network into local networks and hub locations. Xiao et al. (2007) developed a graph partitioning model to cluster mobile units within mobile servers. In this case, a graph G(V,E) is constructed where v∈V represents a mobile unit and each edge e∈E represents a communication link between two units, and where the weight assigned to the edge depends on some technical parameters including the bandwidth and the distance between the two vertices. Laguna (1994) used a graph partitioning model to enhance several design features and to overcome limitations of optical fiber networks within the telecommunication industry.

Graph partitioning has also been used to tackle scheduling problems. Carlson and Nemhauser (1966) developed a clustering model for a scheduling problem that involves several activities and facilities, where the problem is to cluster activities and then to assign them to the facilities so as to minimize interaction costs, given the cost of assigning pairs of activities to a facility. Salido et al. (2007) employed graph partitioning in railway scheduling to generate optimal schedules for trains, taking into consideration connection points, railway types, and train capacities, among other restrictions.

There exist several other such examples of graph partitioning problems that have been studied in the literature, e.g. see Ji (2004). These include the clique partitioning problem (Grotschel and Wakabayashi, 1989; 1990), the graph equipartitioning problem (Conforti and Rao, 1990a, 1990b), the capacitated graph partitioning problem (Mehrotra and Trick, 1998), the maximum balanced connected q-partition (Chlebikova, 1996; Salgado and Wakabayashi, 2004), and the minimum edge-cut graph partitioning problem (Donath and Hoffman, 1973; Goldschmidt and Hochbaum, 1988), among others. All of the above graph partitioning problems are NP-hard (Ji, 2004). In particular, similar to the problem considered in the present paper, the k-way graph equipartitioning problem is to partition the vertex set V into k subsets of equal size, with the objective of minimizing the total weight of edges that have both end-points in the same partitioned subset. Mitchell (2001) formulated a mathematical model for the k-way graph equipartitioning problem, investigated its polyhedral structure and presented a branch-and-cut algorithm to solve the resulting model. The algorithm in Mitchell (2001) was used to realign the National Football League (NFL). Results for partitioning 32 teams into eight groups with the objective of minimizing the overall travel time among teams within each group were reported in Mitchell (2003). The sports realignment problem studied in Mitchell (2001, 2003) was revisited later along with other similar contextual problems by Xiaoyun and Mitchell (2005) who modelled the realignment of NBA, NHL, and NFL as k-way equipartition problems. A branch-and-price scheme with cutting plane features was designed and implemented to solve the resulting k-way equipartitioning problems, where the pricing problem was modelled as an integer program. Computational results indicated that the branch-and-price-and-cut scheme of Xiaoyun and Mitchell (2005) performed well on small-sized instances (with about 40 vertices). However, for larger test instances, the solution of the pricing problem turned out to be cumbersome to solve. Nonetheless, for such problems, the root algorithm was found to yield relatively good quality feasible solutions. The algorithm in Xiaoyun and Mitchell (2005) was also used to solve certain micro aggregation problems. The authors concluded that the performance of their proposed branch-and-price-and-cut approach was comparable to that of the price-and-cut method of Mitchell (2001, 2003).

In this section, we formulate a model for Problem GPP, denoted GPM, which directly attempts to select a minimum-cost collection of n valid partitions from the set P in order to constitute an n-partition.

Model formulation

Define the following set of binary decision variables: xp=1if partitionp∈Pis selected,0otherwise.

For a given partition p∈P, we define the following set of parameters that indicate whether a vertex v∈V belongs to the associated vertex subset Vp or not: λv,p=1ifv∈Vp,0otherwise.

Note that the values of the parameters λv,p are known a priori based on information derived from the corresponding subset Vp. Then, the following model determines a minimum-cost n-partition: (3.1) GPM: Minimize∑p∈Pwpxp,subject to∑p∈Pλv,pxp=1,∀v∈V, (3.2) ∑p∈Pxp=n,xp∈{0,1},∀p∈P. The objective function of GPM minimizes the overall weight of edges associated with the selected n-partition. Constraint (3.1) assures that each v∈V belongs to exactly one valid partition. The required number of valid partitions (n) is enforced by Constraint (3.2). The continuous relaxation of Model GPM, denoted by GPM‾, is given as follows: Minimize{∑p∈Pwpxp:(3.1) and (3.2), wherexp⩾0,∀p∈P}. Note that xp⩽1 is implied by (3.1). The following structural result indicates that Constraint (3.2) can be deleted from the above model without affecting the solution, even in the continuous sense.

Notwithstanding Proposition 1, we retain Constraint (3.2) in the model because of the lower bounding facility it provides for GPM‾, which enables a useful practical stopping criterion when solving the latter problem (see Proposition 2 below).

Note that Model GPM attempts to directly select a minimal cost n-partition, i.e. a minimal cost collection of n valid partitions from the set P. An alternative modelling approach to solve Problem GPP is to designate decision variables that assign vertices to different subsets and to designate constraints to ensure the cardinality of each subsets. This modelling approach is the subject of a follow-on paper, where we will attempt to employ a Lagrangean-based decomposition scheme in concert with symmetry defeating strategies to solve Problem GPP. As it will be seen later, the formulation of Model GPM enabled us to devise a column generation algorithm to heuristically solve Problem GPP, which is the focus of the current paper.

In this section, we exploit the special column structure of GPM in order to solve its continuous LP relaxation GPM‾ via a column generation procedure (e.g. see Barnhart et al., 1998), along with three enhancing features as discussed below. Suppose that at some iteration of the revised simplex method for solving GPM‾, we have a basic feasible solution. Let {ξ≡(ξv,v∈V),ξ0} denote the corresponding complementary dual solution, where ξ and ξ0 are the dual variables associated with Constraints (3.1) and (3.2), respectively. We can then find a candidate entering nonbasic variable xp that has the smallest (most negative) reduced cost by solving the following auxiliary subproblem, where πv equals one if vertex v∈V is selected for inclusion within Vp and is zero otherwise: SP:Minimize∑vi,vj∈Vi<jw(vi,vj)πviπvj−ξTπ−ξ0,subject to:∑v∈Vπv=α,andπv∈{0,1},∀v∈V.

Note that the resulting vector ππ≡(πv,v∈V) corresponds to a valid partition, say p∈P, where λv,p=πv, ∀v∈V, and where the first term of the objective function represents wp for the generated entering column. To solve Problem SP, each product relationship πviπvj that appears in the objective function can be linearized by substituting a continuous variable γvi,vj instead, while incorporating the following constraints, noting that πvi and πvj are required to be binary-valued and that the w-parameters are positive (see Sherali and Warren, 1998): (4.1) γvi,vj⩾πvi+πvj−1andγvi,vj⩾0,∀vi,vj∈V,i<j.

Hence, letting τ∗(M) denote the optimal objective function value of any model M, if Mτ∗(SP)⩾0, then no nonbasic variable is a candidate to enter the basis, and an optimal solution to Problem GPM‾ is at hand. Otherwise, if τ∗(APlb)<0, we will have obtained a candidate entering variable xp for GPM‾ from the optimal solution obtained for SP as noted above, and we then introduce this column into the basis and reiterate.

In this section, we present a heuristic approach to solve Model GPM, denoted by ECGH, which is a sequential variable-fixing procedure that constructs a feasible n-partition in a sequential fashion in order to solve Problem GPP. Essentially, this procedure generates an n-partition by augmenting fixed partitions from solutions to GPM‾ obtained via the ECGA method outlined in the foregoing section.

To describe this procedure, cconsider an optimal solution to GPM‾ obtained via ECGA. Let Sb1 be the index set of the basic variables that equal one when ECGA terminates, and let Sbf be the set of fractional basic variables at optimality. (Note that if Sbf=∅, we have an n-partition at hand, and we stop with this solution as optimal for GPM.) Initialize the set Γ=Sb1. Hence, Vpi∩Vpj=∅, ∀pi,pj∈Γ with i≠j, because otherwise, if there exists some v∈Vpi∩Vpj, then equation (3.1) corresponding to vertex v would be violated. Note that |Γ|⩽n, or else, we would have an n‾-partition, where n‾>nn$]]>, which involves αn‾ vertices from V, contradicting the fact that |V|=αn.

The following Variable-Fixing Step will be used with our proposed enhanced column generation heuristic described subsequently.

Variable-Fixing Step

Let x‾ be the optimal solution obtained for GPM‾ and let x‾max=maxp∈Sbf{x‾p}, and determine Λ={p∈Sbf:x‾p=x‾max}, wmin=min{wp:p∈Λ}, and Λ‾={p∈Λ:wp=wmin}. Pick pˆ∈Λ‾ and update Γ←Γ∪{pˆ}. Let Π={p∈P:Vp∩Vp1=∅,∀p1∈Γ}, and correspondingly, define VΠ={v∈V:v∉⋃p∈ΓVp}.

Based on the above variable-fixing step, we let GPMΠ to be a modified version of GPM obtained by: (a) restricting the set of partitions P to Π, and (b) replacing V by VΠ in (3.1). This problem is given as follows: (5.1) GPMΠ:Minimize∑p∈Πwpxpsubject to∑p∈Πλv,pxp=1,∀v∈VΠ, (5.2) ∑p∈Πxp=n−|Γ|,xp∈{0,1},∀p∈Π. We can now solve GPMΠ‾ using ECGA as before, based on the remnant set of vertices, and repeat the process until an n-partition is obtained. The proposed heuristic (ECGH) for generating an n-partition is stated formally below, noting that whenever |Γ|=n, we have at hand an n-partition that is described by the set of valid partitions {p∈Γ}.

Heuristic ECGH

Initialization

Set Γ=∅Γ=∅, Π=P, and VΠ=V.

LP-Step

Solve GPMΠ‾ using ECGA, and let X‾ denote the resulting solution. Determine the index sets Sb1 and Sbf. If Sbf=∅Sbf=∅, then update Γ←Γ∪Sb1 and stop, since |Γ|=n, then stop; otherwise, proceed to the Variable-Fixing Step.

Variable-Fixing Step (This step is described above).

Final Step

Let Γ←Γ∪{pˆ}. If |Γ|=n; otherwise, update Π and VΠ, and repeat the LP-Step. Remark 3.

a)

At each iteration of ECGH, the set Γ is augmented by at least one valid partition in a feasible fashion, and the number of elements in Γ cannot exceed n. Consequently, the algorithm terminates finitely whenever |Γ|=n, yielding a desired n-partition.

In this section, we present computational results for the proposed complementary column generation approach for solving Model GPM. We use a set of 24 test problems described in Table 1 for GPM, where TPi, i=1,…,24, represents the i-th test problem. For all the test instances, the weights associated with the edges are randomly generated using a random function within the interval [1,1000]. All computational results have been performed on a Core™ i7 Processor, CPU 4.00 GHz computer having 4 GB of RAM and using the CPLEX Commercial Package (version 12) as the optimization solver.

Below, we summarize the notation that will be used in this section.

We begin by presenting computational results pertaining to solving Model GPM using Heuristic ECGH based on a set of 24 test problems having up to 100 vertices with different partitioning requirements. Tables 2 and 3, respectively, present our computational experience in solving Model GPM with and without the CCG Features. Note that because the weights associated with Problem GPP are randomly generated, repeated implementations of Heuristic ECGH might produce different objective function values, optimality gaps and run-times for a given test problem. Also, observe that in Proposition 2, we have assumed that Problem SP is solved using ε2=0, in which case we have the provable lower bound given either by τ∗(GPM‾) if τ∗(SP)⩾0 or otherwise by LB∗. However, when using a tolerance ε2>00$]]> while solving Problem SP, we can modify Proposition 2 to assert that the established duality gap is given by −nτ∗(SP)+nε2⩾0, with LB∗←LB∗−nε2. The use of this lower bounding scheme is instrumental in curtailing the tailing-off effect associated with column generation. Hence, for each test problem, we first set ε1=ε2=0 and try to solve Model GPM within some specified time. In case a solution is not obtainable, we then set ε2=0 and set ε1 to some sufficiently small value and gradually increment it until we reach a solution within the specified time. For test instances that remain unsolved, we set ε2 to a sufficiently small positive value and increment it until we obtain a solution within the specified time. From our preliminary computational experiments, we noticed that solving Problem SP even with the default cutting plane feature of CPLEX was cumbersome in some test instances, especially those having a relatively large number of vertices, while the time to update the solution to GPM was in most cases just a few seconds.

In order to better understand the efficiency of the CCG Features and its contribution toward enhancing the solution quality for Model GPM, we experimented with solving this model using Heuristic ECGH both with and without the CCG Features. As shown in Tables 2 and 3, the incorporation of the CCG Features reduced the average solution time for solving Model GPM‾ by 11-fold and for solving Model GPM by 12-fold. This substantial reduction in the average solution times is attained by virtue of mitigating the tailing-off effect at termination. The average optimality gap at termination when solving Model GPM with and without the enhancing features are given by 3.08% and 4.22%, respectively. Although the higher average optimality gap obtained for the latter is skewed because of the relatively high optimality gap of 57.89% obtained when solving problem TP1 (without this test case, the average optimality gap is given by 1.88%), but still the significant reduction in the average solution time when using the CCG Features strengthens the robustness of the proposed column generation approach.

In the remainder of this section, we focus and analyse results obtained using the CCG Features. To provide insights into the performance of our approach for solving Model GPM, we partition our test problems into three sets, denoted by S1,S2 and S3, based on the number of vertices ranging up to 36, 84, and 100, respectively. Tables 4 and 5 provide results for these partitioned subsets of problems. As expected, with an increase in the number of vertices, both the total run-time for solving Model GPM using ECGH and the resulting optimality gap at termination increased. Test problems from the set S1 (with n⩽36) were solvable without using any termination tolerances for solving either GPM‾ or Problem SP, and in this case the least, largest, and average optimality gaps obtained were given by 0%, 5.88%, and 1.35%, respectively. For test problems from S2 (having n⩽84), we solved Model GPM‾ using a range of incrementally increasing gap tolerances. In this case, the least, largest, and average optimality gaps obtained were given by 0.7%, 6.96%, and 3.45%, respectively. For test problems in S3 (having n⩽100), using the aforementioned modified lower bounding result, the least, largest, and average optimality gaps obtained were given by 5.72%, 12.22%, and 8.35%, respectively.

This paper examines a graph partitioning problem that is concerned with the partitioning of a complete weighted graph G(V,E) into n complete subgraphs each having the same number of α vertices, with the objective of minimizing the total weight of edges included in the subgraphs. This problem has many applications in various contexts such as assignment-related group partitioning problems, micro aggregation in statistics, telecommunication, and political redistricting. To solve this problem, we formulated a mixed-integer program, denoted by GPM, which directly attempts to select a minimum-cost collection of n valid partitions from the entire set of valid partitions in order to constitute an n-partition. Exploiting the structure of Model GPM, we then designed a column generation heuristic (ECGH) that incorporates the following three enhancing features for solving this model: (a) a lower bounding facility based on solving the pricing subproblem, which helps to curtail the tailing off effect typically associated with column generation; (b) a complementary column generation feature that attempts to generate multiple columns at each iteration to constitute a feasible n-partition, and (c) the generation of initial columns for Model GPM that serve to provide a starting basis as well as to restrict the dual solution space, thereby contributing toward dual stabilization.

Detailed computational results were presented for solving Model GPM. These results demonstrated that the CCG Features proposed for enhancing the traditional column generation framework yielded comparable quality solutions (3% optimality on average) with respect to the standard classical column generation approach while reducing the average run-time for solving Models GPM‾ and GPM by 11-fold and 12-fold, respectively. Based on our computational results, we propose investigating further algorithmic strategies for dealing with relatively larger problems. In particular, solving Problem SP within algorithm ECGH was especially cumbersome in test instances of Problem GPP that involve a relatively large number of vertices. In fact, we were able to obtain reasonable solutions for up to 100 vertices for Model GPM, but for problems having 150 vertices, we were unable to solve even the linear programming relaxation of Problem SP after two days of run-time. Hence, we recommend exploring some alternative ways for solving Problem SP, including a polyhedral analysis coupled with more effective heuristic solution approaches.

Another extension worth exploring for solving Model GPM is as follows. Let GPM‾LR be the current restricted version of Model GPM‾ obtained from the final iteration of Algorithm ECGH. We can then solve GPM‾LR to optimality as a 0-1 program directly using a commercial package such as CPLEX by utilizing some suitable specialized decomposition scheme as necessary, in order to obtain a good quality feasible solution to Model GPM. This might be particularly attractive because of the complementary column generation strategy implemented within the solution process (Ghoniem and Sherali, 2009). Moreover, this solution approach can further provide facility to consider equity issues within the vertex partitioning scheme through the addition of suitable side-constraints, which are difficult otherwise to accommodate within the column generation modelling and solution process. In the future, we also aim to explore alternative modelling approaches for Problem GPP that attempt to directly generate the required partitions and use decomposition schemes such as Lagrangian relaxation while incorporating necessary equity.