Informatica

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\in V$ represents a scene and an edge $ e\in 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\in V$ represents a mobile unit and each edge $ e\in 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.

Define the following set of binary decision variables:

For a given partition $ p\in P$, we define the following set of parameters that indicate whether a vertex $ v\in V$ belongs to the associated vertex subset $ {V_{p}}$ or not:

Note that the values of the parameters $ {\lambda _{v,p}}$ are known a priori based on information derived from the corresponding subset $ {V_{p}}$. Then, the following model determines a minimum-cost n-partition: The objective function of GPM minimizes the overall weight of edges associated with the selected n-partition. Constraint (3.1) assures that each $ v\in 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 $ \overline{\mathrm{GPM}}$, is given as follows: Note that $ {x_{p}}\leqslant 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 $ \overline{\mathrm{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 $ \overline{\mathrm{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 $ \overline{\mathrm{GPM}}$, we have a basic feasible solution. Let $ \{\xi \equiv ({\xi _{v}},v\in V),{\xi _{0}}\}$ denote the corresponding complementary dual solution, where ξ and $ {\xi _{0}}$ are the dual variables associated with Constraints (3.1) and (3.2), respectively. We can then find a candidate entering nonbasic variable $ {x_{p}}$ that has the smallest (most negative) reduced cost by solving the following auxiliary subproblem, where $ {\pi _{v}}$ equals one if vertex $ v\in V$ is selected for inclusion within $ {V_{p}}$ and is zero otherwise:

Note that the resulting vector $ \pi \pi \equiv ({\pi _{v}},v\in V)$ corresponds to a valid partition, say $ p\in P$, where $ {\lambda _{v,p}}={\pi _{v}}$, $ \forall v\in V$, and where the first term of the objective function represents $ {w_{p}}$ for the generated entering column. To solve Problem SP, each product relationship $ {\pi _{{v_{i}}}}{\pi _{{v_{j}}}}$ that appears in the objective function can be linearized by substituting a continuous variable $ {\gamma _{{v_{i}},{v_{j}}}}$ instead, while incorporating the following constraints, noting that $ {\pi _{{v_{i}}}}$ and $ {\pi _{{v_{j}}}}$ are required to be binary-valued and that the w-parameters are positive (see Sherali and Warren, 1998):

Hence, letting $ {\tau ^{\ast }}(M)$ denote the optimal objective function value of any model M, if $ M{\tau ^{\ast }}(\mathrm{SP})\geqslant 0$, then no nonbasic variable is a candidate to enter the basis, and an optimal solution to Problem $ \overline{\mathrm{GPM}}$ is at hand. Otherwise, if $ {\tau ^{\ast }}({\mathrm{AP}_{lb}})<0$, we will have obtained a candidate entering variable $ {x_{p}}$ for $ \overline{\mathrm{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 $ \overline{\mathrm{GPM}}$ obtained via the ECGA method outlined in the foregoing section.

To describe this procedure, cconsider an optimal solution to $ \overline{\mathrm{GPM}}$ obtained via ECGA. Let $ {S_{b}^{1}}$ be the index set of the basic variables that equal one when ECGA terminates, and let $ {S_{b}^{f}}$ be the set of fractional basic variables at optimality. (Note that if $ {S_{b}^{f}}=\varnothing $, we have an n-partition at hand, and we stop with this solution as optimal for GPM.) Initialize the set $ \Gamma ={S_{b}^{1}}$. Hence, $ {V^{{p^{i}}}}\cap {V^{{p^{j}}}}=\varnothing $, $ \forall \hspace{0.1667em}{p^{i}},{p^{j}}\in \Gamma $ with $ i\ne j$, because otherwise, if there exists some $ v\in {V^{{p^{i}}}}\cap {V^{{p^{j}}}}$, then equation (3.1) corresponding to vertex v would be violated. Note that $ |\Gamma |\leqslant n$, or else, we would have an $ \overline{n}$-partition, where $ \overline{n}>n$, which involves $ \alpha \overline{n}$ vertices from V, contradicting the fact that $ |V|=\alpha n$.

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

Let $ \overline{x}$ be the optimal solution obtained for $ \overline{\mathrm{GPM}}$ and let $ {\overline{x}_{\max }}={\max _{p\in {S_{b}^{f}}}}\{{\overline{x}_{p}}\}$, and determine $ \Lambda =\{p\in {S_{b}^{f}}:{\overline{x}_{p}}={\overline{x}_{\max }}\}$, $ {w_{\min }}=\min \{{w_{p}}:p\in \Lambda \}$, and $ \overline{\Lambda }=\{p\in \Lambda :{w_{p}}={w_{\min }}\}$. Pick $ \hat{p}\in \overline{\Lambda }$ and update $ \Gamma \gets \Gamma \cup \{\hat{p}\}$. Let $ \Pi =\{p\in P:{V^{p}}\cap {V^{{p^{1}}}}=\varnothing ,\forall {p^{1}}\in \Gamma \}$, and correspondingly, define $ {V^{\Pi }}=\{v\in V:v\notin {\textstyle\bigcup _{p\in \Gamma }}{V^{p}}\}$.

Based on the above variable-fixing step, we let $ {\mathrm{GPM}_{\Pi }}$ to be a modified version of $ \mathrm{GPM}$ obtained by: (a) restricting the set of partitions P to Π, and (b) replacing V by $ {V^{\Pi }}$ in (3.1). This problem is given as follows: We can now solve $ \overline{{\mathrm{GPM}_{\Pi }}}$ 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 $ |\Gamma |=n$, we have at hand an n-partition that is described by the set of valid partitions $ \{p\in \Gamma \}$.

Set $ \Gamma =\varnothing \Gamma =\varnothing $, $ \Pi =P$, and $ {V^{\Pi }}=V$.

Solve $ \overline{{\mathrm{GPM}_{\Pi }}}$ using ECGA, and let $ \overline{X}$ denote the resulting solution. Determine the index sets $ {S_{b}^{1}}$ and $ {S_{b}^{f}}$. If $ {S_{b}^{f}}=\varnothing {S_{b}^{f}}=\varnothing $, then update $ \Gamma \gets \Gamma \cup {S_{b}^{1}}$ and stop, since $ |\Gamma |=n$, then stop; otherwise, proceed to the Variable-Fixing Step.

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

Let $ \Gamma \gets \Gamma \cup \{\hat{p}\}$. If $ |\Gamma |=n$; otherwise, update Π and $ {V^{\Pi }}$, and repeat the LP-Step.

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 $ {\mathit{TP}_{i}}$, $ i=1,\dots ,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 $ {\varepsilon _{2}}=0$, in which case we have the provable lower bound given either by $ {\tau ^{\ast }}(\overline{\mathrm{GPM}})$ if $ {\tau ^{\ast }}(\mathrm{SP})\geqslant 0$ or otherwise by $ {\mathit{LB}^{\ast }}$. However, when using a tolerance $ {\varepsilon _{2}}>0$ while solving Problem SP, we can modify Proposition 2 to assert that the established duality gap is given by $ -n{\tau ^{\ast }}(\mathrm{SP})+n{\varepsilon _{2}}\geqslant 0$, with $ {\mathit{LB}^{\ast }}\gets {\mathit{LB}^{\ast }}-n{\varepsilon _{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 $ {\varepsilon _{1}}={\varepsilon _{2}}=0$ and try to solve Model GPM within some specified time. In case a solution is not obtainable, we then set $ {\varepsilon _{2}}=0$ and set $ {\varepsilon _{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 $ {\varepsilon _{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 $ \overline{\mathrm{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 $ {\mathit{TP}_{1}}$ (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 $ {S_{1}},{S_{2}}$ and $ {S_{3}}$, 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 $ {S_{1}}$ (with $ n\leqslant 36$) were solvable without using any termination tolerances for solving either $ \overline{\mathrm{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 $ {S_{2}}$ (having $ n\leqslant 84$), we solved Model $ \overline{\mathrm{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 $ {S_{3}}$ (having $ n\leqslant 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 $ \overline{\mathrm{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 $ {\overline{\mathrm{GPM}}_{\mathrm{LR}}}$ be the current restricted version of Model $ \overline{\mathrm{GPM}}$ obtained from the final iteration of Algorithm ECGH. We can then solve $ {\overline{\mathrm{GPM}}_{\mathrm{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.