Engineering Branch-and-Cut Algorithms for the Equicut Problem

Abstract

A minimum equicut of an edge-weighted graph is a partition of the nodes of the graph into two sets of equal size such that the sum of the weights of edges joining nodes in different partitions is minimum. We compare basic linear and semidefinite relaxations for the equicut problem, and find that linear bounds are competitive with the corresponding semidefinite ones but can be computed much faster. Motivated by an application of equicut in theoretical physics, we revisit an approach by Brunetta et al. and present an enhanced branch-and-cut algorithm. Our computational results suggest that the proposed branch-and-cut algorithm has a better performance than the algorithm of Brunetta et al. Further, it is able to solve to optimality in reasonable time several instances with more than 200 nodes from the physics application.

Subject Classifications : 90C57, 90C22, 90C05, 90C27

1 Introduction

The maximum cut problem on an edge-weighted graph G = (V, E) is to find a partition of the set of nodes V into two shores (node sets) such that the weight of the cut (the sum of the weights of edges with endpoints in different shores) is maximum. It is a prominent NP-hard combinatorial optimization problem that has been studied intensively in the literature.

We consider the equicut problem which is the max-cut problem with the additional restriction that the sizes (number of nodes) of the shores must be equal. This work is motivated by an application in theoretical physics: equicuts can be used for the calculation of minimum-energy states, or ground states, for so-called Coulomb glasses. In a Coulomb glass, charges may be placed on the sites of a lattice. The number of charges is exactly half the number of sites. Randomly chosen local fields act on the charges. Since a quadratic function is used to represent the energy of a state as a graph G, the task is to determine an equicut in G.

Polyhedral investigations of the equicut polytope have been presented in [10, 11, 14]. Building upon this theoretical knowledge, an integer programming-based branch-and-cut approach was implemented in [8]. The bisection problem is the more general task of determining a cut in which the shore sizes are constrained (but not necessarily equal). Formulations using integer programming, semidefinite programming (SDP), a polyhedral study and computational results are presented in [2, 3, 29]. Another branch-and-bound algorithm using SDP formulations of the bisection problem that specifically accounts for the special case of equicut is given in [25]. A quadratic convex reformulation of the bisection problem is given in [6]. Further generalizations of the bisection problem with additional node capacities are studied in [17, 18, 22]. The maximum cut problem as well as other related problems have been investigated in great depth [15]. SDP-models for related graph partition problems have been introduced in [19, 24] and in the recent preprints [27, 32].

In this work, we first summarize important facts about the cut and the equicut polytopes and their relationships. The main part of this paper presents an algorithm engineering approach for an exact branch-and-cut algorithm for computing equicuts. Experimentally, we find that the bounds obtained from the SDP relaxation of [19] with several additional linear constraints are usually not stronger than those from solving the same linear relaxation without the SDP model. Furthermore, the computation of the SDP bounds often needed considerably more time. We then focus on the usage of integer linear programming (ILP) methods. We take the most important ingredients from the method of [8] and enrich it by target cuts, a variant of local cuts [9]. It turns out that within this separation routine, orthogonal projections on node-induced subgraphs together with zero-lifting of the separated inequalities works well in practice. For complete graphs, the projection and lifting approach is equivalent to the graph shrinking procedure from [23]. As target cut separation yields very strong bounds but can be time-consuming, we then design fast heuristics to separate those inequalities found by target cut separation. We finally show that our approach yields an effective method for determining optimal equicuts in graphs, i.e., the computation times needed are about two orders of magnitude less than those reported in [8] on average. Furthermore we could reduce the average number of branching nodes by a factor of approximately 4; for some of the largest instances the computation time was three orders of magnitude faster than those reported in [8]; and instances that required more than 50 branching nodes are now solved at the root node. Hence we could solve some large instances that were not reported in [8] as well as instances of Coulomb glasses to optimality. We also solved instances with more than 200 nodes, doubling the size of the instances reported in [8].

2 The Equicut Problem

Let a graph G = (V, E) with node set V, edge set E, and edge weights $c : E \rightarrow \mathbb{R}$ be given. We denote by n and m the cardinalities of V and E, respectively. The complete graph on n nodes is denoted by K _n . For $S \subseteq V$ a cut $\delta (S) \subseteq E$ is the set of edges with exactly one node in S. Its weight is the sum of the weights of edges in δ(S). We call S and $V \setminus S$ shores of δ(S). A cut δ(S) is an equicut if $\left \lfloor \frac{n} {2} \right \rfloor \leq \vert S\vert \leq \left \lceil \frac{n} {2} \right \rceil$. We associate with every cut δ(S) its characteristic vector $x(\delta (S)) = (x_{1},\ldots,x_{m}) \in \{ 0,{1\}}^{m}$ where x _e  = 1 if e ∈ δ(S) and x _e  = 0 otherwise. The cut polytope $\mathcal{C}(G)$ and the equicut polytope $\mathcal{Q}(G)$ of a graph G are the convex hulls of the characteristic vectors of all cuts and of all equicuts of G, respectively. The equicut problem consists in finding an equicut in G with minimum weight.

2.1 The Cut and the Equicut Polytope

In this section, we review known results about the equicut polytope [10, 11].

For a complete graph K _2p , the edge set induced by an equicut contains exactly p ² many edges. Furthermore, every equicut in K _2p + 1 contains p(p + 1) many edges. Thus, an equicut on a complete graph K _n has exactly $\left \lfloor \frac{n} {2} \right \rfloor \left \lceil \frac{n} {2} \right \rceil$ edges in the cut.

For complete graphs, the equicut polytope $\mathcal{Q}(K_{n})$ can be defined as

$$\displaystyle\begin{array}{rcl} \mathcal{Q}(K_{n})& =& conv\left \{x \in \mathcal{C}(K_{n})\mid \sum _{e}x_{e} = \left \lfloor \frac{n} {2} \right \rfloor \left \lceil \frac{n} {2} \right \rceil \right \}\!\!.{}\end{array}$$

(1)

Given a relaxation of the cut polytope we can use (1) to obtain a relaxation of the equicut problem as all inequalities remain valid.

We use the following classes of valid inequalities, some of which are well-known from the cut polytope [15]. For a more in-depth discussion see [10, 11] and [14].

Definition 1.

Let K _p  = (V′, E′) be a complete subgraph (clique) of G = (V, E). The clique inequality is given by

$$\displaystyle\begin{array}{rcl} \sum _{e\in E^{\prime}}x_{e}& \leq & \left \lfloor \frac{p} {2}\right \rfloor \left \lceil \frac{p} {2}\right \rceil.{}\end{array}$$

(2)

For each cut δ(S) in K _p the switched clique inequality reads

$$\displaystyle\begin{array}{rcl} \sum _{e\in E^{\prime}\setminus \delta (S)}x_{e} -\sum _{e\in \delta (S)}x_{e}& \leq & \left \lfloor \frac{p} {2}\right \rfloor \left \lceil \frac{p} {2}\right \rceil -\vert \delta (S)\vert.{}\end{array}$$

(3)

For the special case p = 3 the clique inequalities reduce to the triangle inequalities. For any triplet i, j, k such that (i, j), (i, k), (j, k) ∈ E, they take the following forms:

$$\displaystyle\begin{array}{rcl} x_{ij} + x_{ik} + x_{jk}& \leq & 2{}\end{array}$$

(4)

$$\displaystyle\begin{array}{rcl} x_{ij} - x_{ik} - x_{jk}& \leq & 0.{}\end{array}$$

(5)

Barahona et al. [4] proved that the clique inequalities (2) are facets of the cut polytope $\mathcal{C}(K_{p})$ iff p is odd. Hence the equicut polytope $\mathcal{Q}(K_{n})$ is a face of the cut polytope and it is a facet iff n is odd [10].

As the number of cut edges in a cycle is even, for every cycle C with $\vert C\vert = p + 1$ and n = 2p the cycle inequalities (6) are valid for $\mathcal{Q}(K_{n})$:

$$\displaystyle\begin{array}{rcl} \sum _{e\in C}x_{e} \geq 2.& &{}\end{array}$$

(6)

For a formal proof and facet inducing properties of these inequalities we refer to Conforti et al. [11].

If an edge e = st is fixed to be in the cut, the resulting polytope is known as s-t-(equi-)cut polytope. Given a path $P = (s = v_{0},v_{1},\ldots,v_{k} = t)$ we consider the following s-t path inequalities that make sure that at least one edge on that path is cut:

$$\displaystyle\begin{array}{rcl} \sum _{e\in P}x_{e} \geq 1.& &{}\end{array}$$

(7)

It is easy to see that inequalities (7) are valid for the respective s-t-cut polytopes and they can be separated efficiently by shortest path computations. For further reasons to use these inequalities we refer to Conforti et al. [11].

For complete graphs K _2p , any equicut is also a p-regular subgraph of K _2p  [8], i.e. each node has degree | δ(v) |  = p. Therefore, $\mathcal{Q}(K_{2p})$ is contained in $\mathcal{P}\mathcal{F}(K_{2p})$, which is the convex hull of all p-regular subgraphs of K _2p . Edmonds et al. [16] give the following complete description of $\mathcal{P}\mathcal{F}(K_{2p})$:

$$\displaystyle\begin{array}{rcl} \sum _{e\in \delta (v)}x_{e}& =& p{}\end{array}$$

(8)

$$\displaystyle\begin{array}{rcl} \sum _{e\in W\times W}x_{e} +\sum _{e\in T}x_{e}& \leq & \frac{p\vert W\vert + \vert T\vert - 1} {2},{}\end{array}$$

(9)

where v ∈ V, $W \subseteq V$, $T \subseteq \delta (W)$ and p | W |  +  | T | is odd. Inequalities (9) are called blossom inequalities.

We will work with complete graphs K _2p in the following as the inequalities (8) may be invalid for non-complete graphs.

2.2 Inequalities Outside the Template Paradigm

The classes of inequalities introduced earlier follow the template paradigm, i.e. inequalities within a class share a similar structure. A general procedure to generate valid inequalities for some polytope is given by separation of local cuts [1] or their variant called target cuts [9]. For the separation, the polytope in question and the point to be separated are projected into a low-dimensional space. A cutting plane separating the projected point from the projected polytope is generated by solving a small linear program. The size of the linear program is basically determined by the number of vertices of the projected polytope. Inequalities are then lifted to inequalities valid for the original problem.

2.3 Non-polyhedral Model

Given a weight matrix C = { c _ij } for the edges e = ij of a complete graph K _n the following SDP relaxation for the equicut problem was introduced by Frieze and Jerrum [19]:

$$\displaystyle\begin{array}{rcl} \min \left \{\frac{1} {4}\mathit{trace}(C(J_{n} - X))\mid \mathit{diag}(X) = e,Xe = 0,X \succcurlyeq 0\right \}.& &{}\end{array}$$

(10)

The notation trace(A) refers to the sum of all elements of the main diagonal of a matrix A and the matrix J _n is the n ×n matrix of all ones. In the positive semidefinite relaxation of the cut polytope [15], we restrict ourselves to positive-semidefinite matrices X ($X \succcurlyeq 0$) where all elements of the main diagonal are equal to one (diag(X) = e). This SDP relaxation is also referred to as the elliptope $\mathcal{E}_{n}$. A relaxation of the equicut problem is obtained by adding the constraint Xe = 0 as in [19] or in the form e ^T Xe = 0 as in [25].

The variables $x_{ij}^{lp} \in \{ 0,1\}$ from the LP formulation are in one-to-one correspondence with the elements $x_{ij}^{sdp} \in X$ of the positive-semidefinite matrix X via the transformation $x_{ij}^{sdp} = 1 - 2x_{ij}^{lp}$.

Our basic LP relaxation includes degree and triangle inequalities:

$$\displaystyle\begin{array}{rcl} \min \left \{\sum _{e}c_{e}x_{e}\mid \forall i,j,k \in V : (\mbox{4}) - (\mbox{ 5}),\forall v \in V : (\mbox{8})\right \}.& &{}\end{array}$$

(11)

As we will see, the relaxation obtained by separating (switched) clique (3), cycle (6) and blossom (9) inequalities is already very good in practice. In fact we can solve most instances of the benchmark from Brunetta et al. [8] at the root node without branching. In some cases a better performance of our method can be obtained by forcing the algorithm to branch when there is too little improvement in the objective value (cf. tailing-off, Sect. 3.1). Target cut separation may improve the performance when applied before branching.

In order to evaluate the respective bounds based on SDP and LP relaxations we first applied our branch-and-cut algorithm to the benchmark from Brunetta et al. [8]. For each instance we studied the relaxation that was obtained in the root, i.e. without branching.

In order to get reasonable computation times and memory usage we chose all instances with less than 10⁵ inequalities in the final LP. There were 11 such instances. Since they were already solved at the root node, the respective SDP bounds are not significantly better than the LP bounds. In order to evaluate their strengths in practice nevertheless, we compare the LP bounds with those of the SDP when adding only a fraction of the inequalities separated by branch-and-cut. All SDP relaxations were computed using CSDP 6.1.1. [7]. The LPs were solved using version 12.1 of the CPLEX callable library [12]. We show in Table 1 the bounds that are obtained by solving the LP as well as the SDP when adding all separated inequalities (All), when adding only all triangle inequalities (Triangles) and when adding all inequalities but leaving out the (switched) clique inequalities (All but cliques). The generated inequalities are very strong in practice. It turns out that the triangle inequalities are important in practice as the corresponding bound is quite close to that given by all inequalities. This is known to hold for maximum cut as well, see e.g. [31].

Table 1 LP and SDP bounds of root relaxations

Furthermore, the switched clique inequalities are most significant for improving the relaxation over the triangle bound as the remaining inequalities do not improve the bound any further. Similar results are obtained for most instances. Hence we conclude that using SDP relaxations does not significantly improve the root bounds compared to those obtained from the LP approach. Furthermore, the LP relaxations were obtained within minutes whereas some of the SDP relaxations needed several days of CPU time. We also tried to use a general maximum cut solver (BiqMac [31]) by dualizing the equicut constraint in the form e ^T Xe = 0. Therefore we introduced sufficiently large penalties for solutions that would use less than $\frac{{n}^{2}} {4}$ cut edges. More precisely we added the sum of the absolute values of edge weights to each edge in the maximization problem. Hence optimal maximum cuts had to be equicuts and its values could be obtained by substracting a large constant. The solver sometimes was about two orders of magnitudes faster than our implementation. Unfortunately we observed that the precision of the solution values was limited to three digits. While this did not adversely affect the results for instances from [8], the solutions obtained by this approach for instances with fractional edge weights may be incorrect. Specifically for instances coming from the physics application, we could not obtain useful solutions even for the smallest instances. We thus chose to use the LP relaxation for our purposes.

Armbruster et al. [3] present relaxations using LP and SDP methods to solve a generalization of the equicut problem, i.e. the minimum bisection problem, where the number of nodes in each shore has to be larger than some parameter $F \leq \lfloor \frac{n} {2} \rfloor$. Their computational results on sparse instances suggest that SDP relaxations are superior to the corresponding LP relaxations. As equicut is a special case of the minimum bisection problem this appears to contradict the above observations. However, in contrast to the relaxations used in [3], our model is defined on complete graphs and includes constraints that are not valid for the minimum bisection polytope in general. Hence it is likely that our LP relaxation for the equicut problem is stronger than more general relaxations for the minimum bisection problem, and that it is especially well suited for dense instances such as those coming from the physics application.

3 Enhanced Branch-and-Cut Algorithm

Branch-and-cut is a framework often used for solving NP-hard combinatorial optimization problems exactly. Upper and lower bounds on the objective value are iteratively improved until optimality of a known solution can be proven. The size of the branching tree is kept small by using strong relaxations for the lower bounds and primal heuristics for the upper bounds. In this section, we describe cutting-plane separation and primal heuristics for our proposed branch-and-cut algorithm.

3.1 Cutting-Plane Separation

Given a (possibly fractional) vector ${x}^{{\ast}}\in {\mathbb{R}}^{m},0 \leq {x}^{{\ast}}\leq 1$, the separation problem asks for either an inequality violated by x ^∗ or a proof that all inequalities valid for the polytope in question are satisfied. An algorithm that solves the separation problem for any fractional solution is called exact. In contrast heuristic separation algorithms find violated inequalities but if none is found, they cannot prove that there are no violated inequalities for the polytope. Separation algorithms are often defined for classes of inequalities such as those introduced in Sect. 2.

In general some classes of inequalities are more important than others or may become more important after several iterations. Brunetta et al. [8] use the relative change in the objective value from the previous iteration to decide which class of inequalities should be separated. Therefore they introduce certain threshold values for each class of inequalities. Hence they separate triangle inequalities if the relative change is above a certain value, then clique separation is applied if the relative change is above another value and then blossom inequalities and (p + 1)-cycle inequalities are separated if the relative change is above their respective thresholds. If the relative change is below any thresholds branching is applied. Because the thresholds are very sensitive to small changes in the separation routines, we decided to use just a single threshold to decide whether any separation is applied or we branch. We found that a factor $\alpha = 1{0}^{-4}$ for the relative change of the objective value was a reasonable choice. Further in each iteration we stop separation whenever we found a certain number of violated inequalities. We found that 500 violated inequalities are a reasonable choice for most instances.

The degree inequalities (8) are all added from the beginning. In contrast to the heuristics for separating blossom inequalities in [8], we separate them exactly by the efficient algorithm [28].

Finally, target cut separation is applied whenever the other routines do not find any violated inequality. Target cuts were introduced in [9]. The key observation for target cuts is the following. For k ≤ m, let π be some projection ${\mathbb{R}}^{m} \rightarrow {\mathbb{R}}^{k}$. Then the projection $\overline{P} =\pi (P) \subseteq {\mathbb{R}}^{k}$ of some polytope P in ${\mathbb{R}}^{m}$ is the convex hull of all points in ${\mathbb{R}}^{k}$ that can be extended to a point in P. Thus, $\overline{P}$ is the convex hull of all points $\pi (x_{1}),\ldots,\pi (x_{r}) \in {\mathbb{R}}^{k}$ such that $x_{1},\ldots,x_{r}$ are the vertices of P. For k ≪ m, many of the π(x _i ) are equal so that for small k, $\overline{P}$ can be dealt with efficiently. For details, we refer the reader to [9].

For the equicut polytope, we use orthogonal projections to (node-induced) subgraphs. More specifically, edges incident on nodes which are not in the considered subgraph are neglected. The projected polytope is then again a cut polytope. Given an inequality valid for $\overline{P}$, the corresponding inequality with coefficients set to zero for the neglected edges is then valid for P (‘zero-lifting’).

For the maximum cut problem, another projection is given through shrinking nodes to supernodes as introduced by Jünger et al. [23]. This projection is especially tailored for sparse graphs. For an edge (s, t) ∈ E nodes s, t are replaced by a supernode v. Loops and multiple edges are deleted. Given a valid inequality ax ≤ b for $\overline{P}$ with complete graphs the corresponding lifted inequality a′x ≤ b′ w.l.o.g. is defined as a′ _st  = 0, $a^{\prime}_{sn} = a_{vn}$ and a′ _tn  = 0 for all nodes that are neighbours of s, t and v.

It is easy to see that for complete graphs the shrinking procedure is equivalent to the orthogonal projection that we use. Indeed, in the notation introduced above, a supernode v may be replaced by either s or t. Thus, when lifting an inequality the coefficients of variables x _st and x _tn are zero-lifted.

For the equicut problem, we can solve the target cut linear programs for subgraphs with up to 20 nodes within reasonable time. Therefore if we solve graphs with more than n = 40 nodes the subgraph induced by our projection always has less than $\lceil \frac{n} {2} \rceil$ nodes. Thus, for instances of interesting sizes the projection of the equicut polytope is again a cut polytope without any restrictions on the size of the shores.

Next, we describe how we choose the nodes of the subgraphs used for projection. In order to separate a valid inequality the projected fractional solution needs to be infeasible. It is well known, that the cut polytope is a very symmetric object, i.e. the structure of inequalities valid with equality is the same at each vertex of the polytope. Furthermore the barycenter of the (equi)cut polytope is the vector m = (0. 5, 0. 5, …, 0. 5) and the closer a fractional solution $\tilde{x}$ is to m, the less likely it is to be violated. Therefore given the fractional value $\tilde{x}_{e}$ of an edge e we assume that the value $b_{e} = \vert 0.5 -\tilde{ x}_{e}\vert$ correlates to the probability that the variable x _e contributes to a violated inequality, and we assume that these probabilities can be cumulated as $b_{u} =\sum _{e\in \delta (u)}b_{e}$ at node u. Unfortunately choosing the first k nodes with the largest values of b _u may as well result in a subgraph where the fractional solution $\tilde{x}$ is integral, hence given an integer feasible solution there is no violated inequality. Consequently the more fractional the solution $\tilde{x}$ is, the more likely it will yield a violated inequality. Further results on the projection we used as well as on the performance of target cut separation are described in Sect. 4.

3.2 Primal Heuristic

Given a fractional optimum solution ${x}^{{\ast}}\in {\mathbb{R}}^{m}$ of the current LP-relaxation, primal heuristics round x ^∗ to a feasible solution that is hopefully better than the best one known to date. For the maximum cut problem, a primal heuristic works as follows [5]. A cut is given by a spanning tree where each edge is either a cut or a non-cut edge according to the corresponding value of the solution. The ‘most decided’ edges are used if the spanning tree in G is minimum with respect to the weights $w_{e} =\min (x_{e}^{{\ast}},1 - x_{e}^{{\ast}})$ on the edges e ∈ E. The LP-values on the tree are then rounded appropriately, and the corresponding cut is returned. A minimum spanning tree may be computed by Prim’s algorithm in O( | E |  +  | V | log | V | ) [30].

For the equicut problem, a cut has to additionally satisfy the cardinality constraint on the shore size. We thus adapt the above greedy approach using Prim’s algorithm. In each step, several trees are combined to larger trees until a spanning tree arises. Each of these trees induces a cut in the subgraph induced by its nodes, which we will call partial cuts.

Furthermore we have to make sure that in each iteration it is possible to combine these partial cuts to an equicut. We will call such a set of partial cuts compatible, and incompatible otherwise. Let a _i and b _i denote the size of the shores induced by the partial cut δ _i (S) and $d_{i} = \vert a_{i} - b_{i}\vert$ the absolute difference of the shore sizes. The subset-sum problem asks whether a subset $D^{\prime} \subseteq \{ d_{i}\}$ exists such that $\sum _{d_{i}\in D^{\prime}}d_{i} = k$. Choosing $k = \frac{\sum d_{i}} {2}$, the partial cuts are compatible if the answer to the subset-sum problem is positive, and incompatible otherwise. In general the subset-sum problem is NP-complete. Nevertheless, we use the well-known pseudo-polynomial algorithm due to Ibarra and Kim [21] for the knapsack problem which can be used to solve the subset-sum problem as well. As in our case the number of items and their weights are bounded above by | V | , the pseudo-polynomial algorithm yields an O( | V | ²) algorithm.

Within Prim’s algorithm, we make sure that whenever an edge is added to the spanning tree the partial cuts are compatible. This can be achieved by either skipping critical edges which lead to incompatible partial cuts or by repairing the partial cuts in such a way that the partial cuts become compatible. In either case we must never add edges that lead to a cycle. We also avoid using edges with weights w _e larger than a certain value r by temporarily removing them from G. From our experiments, r = 0. 25 is a good choice.

Then according to Prim’s algorithm all edges are iterated in order of increasing values w _e and edges which lead to cycles are skipped. Our method then uses three phases where edges are added and components of the graph are joined until a spanning tree is found. In the first phase we avoid repairing the partial cuts by skipping critical edges. In the second phase edges which lead to incompatible partial cuts are added. After adding an edge the partial cuts are then repaired greedily with respect to a minimum increase of the total edge weights w _e of the tree and such that no partial cut induces a shore of size greater than $\frac{\vert V \vert } {2}$. In the third phase we iteratively join the two largest components, which may occur from removing all edges with weights w _e  > r. Again if a shore size exceeds $\frac{\vert V \vert } {2}$ nodes we have to repair that shore as in the second phase. Finally, we apply the Kernighan-Lin heuristic [26] to the solution to further improve the objective value.

We applied the above heuristic in our branch-and-cut algorithm. For all instances that were computed, whenever the root relaxation was strong enough to avoid branching, the optimal solution had been found by our primal heuristic.

4 Computational Results

In this section we evaluate our proposed branch-and-cut algorithm which is based upon a reimplementation of the algorithm presented in [8] using state-of-the-art tools. We used C++ and version 12.1 of CPLEX callable library as the branch-and-cut framework. For our experiments we used machines with Intel Xeon CPUs E5410 at 2.33 GHz. We use instances from [8] and instances from the physics application to evaluate the performance of our algorithm. The data for the instances we used and complete tables of computational results are available at [20].

In the determination of ground states in Coulomb glasses, we need to compute the minimum of the energy function:

$$\displaystyle\begin{array}{rcl} H(q)& =& \sum _{i<j}p_{ij}q_{i}q_{j} +\sum _{i}c_{i}q_{i}.{}\end{array}$$

(12)

The values q _i  ∈ { − 1, 1} represent the positive or negative charges of sites i and are to be optimized. We are interested in charge-neutral systems, i.e. $\sum _{i}q_{i} = 0$. Those sites are located on a lattice and the values p _ij represent the pairwise interaction of sites i and j. We can use the same variable transformation as in Sect. 2.3 to obtain a quadratic unconstrained binary optimization (QUBO) problem. It was proved by de Simone [13] that QUBO is equivalent to the maximum cut problem. For this transformation the quadratic terms in the objective function are represented by edges in a graph. The linear terms are represented by edges connected to an artificial node s that is added to the graph. The Coulomb glass instances are generally defined on an even number of sites, hence the above transformation would yield a graph with an odd number of nodes. A complete graph K _2n is then obtained by adding another artificial node t. Further the constant term from the transformation to QUBO is represented by the weight of the edge st. Since we restrict to charge-neutral systems we have to find a minimum s-t equicut (cf. Sect. 2.1).

In order to improve the quality of the LP relaxation we used target cut separation. We found that a significant number of violated inequalities found by target cut separation were switched clique inequalities (3).

We use a greedy heuristic to separate switched clique inequalities that extends the algorithm described in [8] in a straight forward way. We start with the most violated triangle inequality which is also a switched clique inequality. Given a switched clique inequality for a clique K _p  = (V′, E′) and a cut δ(S) with $\vert S\vert \leq \vert \bar{S}\vert$, we iteratively compute switched clique inequalities for a clique K _p + 1 unless p + 1 exceeds a certain node limit k. Considering the switching operation we further improve the violation of the inequality in each iteration by iteratively switching pairs of nodes i and j if the violation of the switched clique inequality is increased.

In Table 2 we give the results for instances reported in [8] with our branch-and-cut algorithm including switched clique and target cut separation with different projections to subgraphs with 15 nodes. Further we give the number of subproblems reported in [8] as a reference.

Table 2 Root bounds, number of subproblems and CPU time to solve instances reported in [8] without target cut separation (N), with random (R) and with greedy (G) projections. Number of branching nodes reported in [8] are given in columns (B). Results for instances with less than 40 nodes and instances that are not reported in [8] are omitted. Bounds are given as “*” if optimum was found in the root node

The results suggest that target cut separation improves the LP relaxation for all projections and no choice of projection dominates the others in terms of the number of subproblems. Considering CPU times for most instances the overhead of target cut separation is moderate for the given size of projections but helps to reduce the number of subproblems. Comparing our results with those reported in [8] is very difficult since their reported computation times are for experiments carried out in the mid-1990s. Nevertheless we point out that our computation times are two orders of magnitude smaller on average, and more importantly, we need fewer subproblems. We conclude that our computation times outperform previous approaches based on LP relaxations. With respect to using SDP, the computation times reported in [25] for the branch-and-bound algorithm based on SDP relaxations seem to be better while our method needs fewer subproblems. In general LP relaxations can be solved much faster than SDP relaxations. Consequently the method described in [25] needs to solve fewer relaxations. Using equivalent SDP and LP relaxations we further observed that the bounds are very similar (cf. Sect. 2.3). Therefore we suspect that better computation times can be explained by stronger inequalities that were separated due to the different fractional points given by the interior-point method.

In Table 3 we give the bounds at the root node, the number of subproblems and the CPU time needed by our branch-and-cut algorithm with and without switched clique separation for instances from [8], including some instances that were not reported in [8]. Further we did not apply target cut separation. The results suggest that switched clique separation improves the bounds significantly.

Table 3 Root bounds, number of subproblems and CPU time to solve instances from [8] with and without switched clique (SC) separation. Results for instances with less than 52 nodes are omitted. Bounds are given as “*” if optimum was found in the root node. No target cut separation was applied

Furthermore, as switched clique inequalities and target cut separation significantly improve the LP relaxations, we were able to solve larger instances than those reported in [8]. We illustrate this by presenting our results on Coulomb glass instances with up to 258 nodes. Table 4 gives the number of subproblems and CPU time required. For some instances that could not be solved, we report the gaps after 3 days of computation.

Table 4 Mean values for the relative gap at the root node, number of subproblems and computation times for large instances from the Coulomb glass model with two- and three-dimensional grid graphs. Each class of instances is characterized by the length of the grids L and its dimension. For each class of instances we present results averaged over five randomly generated instances with different random seeds to compute the values c _i of the local field. Due to our transformation the number of nodes is given as $\vert V \vert = Size + 2$

5 Conclusions

Our experimental results support the conclusion that the proposed branch-and-cut algorithm based on a linear relaxation with additional switched clique inequalities and target cut separation is able to efficiently solve medium-sized instances of equicut and larger instances of Coulomb glasses. This new algorithm thus contributes to the practical solution of equicut problems.

Most inequalities separated by target cut separation are hypermetric inequalities which is a very general class of inequalities [15]. It would be interesting to find heuristics to separate more specific hypermetric inequalities. Therefore target cut separation could be used to classify important inequalities. Further improving the performance of target cut separation would allow the use of larger subgraphs for the projection. It would also be interesting to improve the projections to find violated inequalities more efficiently.