Budgeted max cut heuristic

Question

I am looking for a heuristic that solves a budgeted variant of the max cut problem.

Given a graph $G = (V, E)$, if the original problem is to find a partition of $V$ into two subsets $A$ and $B$ where $A \cap B = \emptyset$ such that the size of the cut set $\{(u, v) \in E \mid u \in A, v \in B\}$ is maximised, then I define the budgeted variant of this problem to be almost identical except with the constraint that $|A| = b $ for some $b \in \mathbb{N}$, i.e. find the $b$ nodes in $V$ that maximise the cut set.

Is this a well studied problem?

I have found some papers that seem related to this, e.g. [1], [2] and [3] but I am finding them difficult to read and relate back to the max cut problem. For instance [1] and [2] discuss auctions which I am finding quite confusing. [3] seems to more directly address it but is from 2001, so I am curious whether there are any more recent papers, potentially with better run time complexity, etc.

Does anyone know if there is a paper that addresses this budgeted max cut problem directly and provides a heuristic for solving it?

Answer 1

There are a number of metaheuristics that can be applied to this problem. One of them is a genetic algorithm. I'll assume that the vertices are denoted by the integers $1,\dots,N$ with $N=|V|$. To implement a GA, you can define a "chromosome" (solution) to be a permutation of the integers . The fitness of a chromosome is the size of the cut set (or the value of the cut set in the weighted case) when $A$ is defined to be the vertices indexed by the first $b$ elements in the permutation. There are GA libraries available in many programming languages, and some of them directly support permutation chromosomes. (The GA package for R is one such.)

Simpler heuristics include generating a random partition (pick $b$ vertices randomly to get your initial $A$) and then looking at possible swaps of a vertex in $A$ with a vertex in $B$. A greedy version makes the swap only if the value of the cut set improves. A simulated annealing metaheuristic will occasionally make a swap that decreases the objective value (in the hopes of it leading to swaps that make things even better). These can be implemented with restarts (get a random solution, try to improve it for a while, then start over with a new random solution, keeping track of the best solution ever found).

Being heuristics, none of these are guaranteed to produce an optimal solution, and if any of them have a performance guarantee (objective value no worse than $\alpha$ times the optimal value for some $\alpha$ hopefully not too much less than 1), I'm unaware of it.

Addendum: Just for completeness, I should mention that you can get an exact solution using an integer programming (IP) model (assuming that the graph size does not exceed what your solver can handle). That in turn leads to another heuristic: set up the IP model, let the solver chew on it for a specified amount of time, then accept the (possibly suboptimal) incumbent solution.

Addendum 2: I ran some tests using a MIP model to compute the optimal solution, plus a genetic algorithm and a very simple pairwise-exchange heuristic with random restarts. The GA had a stagnation limit (100 generations with no improvement) and the exchange heuristic had a fixed time limit (2 minutes). The exchange heuristic outperformed the GA, although that could be a function of parameter choices. (The GA hit its limit in well under 2 minutes, so large populations and/or longer stagnation limits might have made it competitive.) The big surprise for me, though, was that the exchange heuristic found the optimum in three of five test runs and had objective gaps of 0.4% and 1.6% in the other two. Since the exchange heuristic is very easy to program and requires no special libraries, it might be a good starting point.

Answer 2

If you have a Max-Cut solver (or even a generic MILP solver) you can dualize the cardinality constraint and apply Dantzig-Wolfe decomposition or Lagrangian relaxation. Explicitly, let binary decision variable $x_i$ indicate whether $i\in A$. The problem is to maximize $$\sum_{(i,j) \in E} (x_i(1-x_j)+x_j(1-x_i))=\sum_{(i,j) \in E} (x_i+x_j-2x_i x_j) \tag0$$ subject to \begin{align} \sum_{i \in V} x_i &= b \tag1 \end{align} Constraint $(1)$ enforces $|A|=b$. You can linearize the objective function $(0)$ by introducing binary decision variable $y_{i,j}$ and linear constraint \begin{align} x_i + x_j - 1 &\le y_{i,j} &&\text{for $(i,j)\in E$} \tag2 \\ \end{align} Constraint $(2)$ enforces $(x_i \land x_j) \implies y_{i,j}$.

The linearized problem is to maximize $$\sum_{(i,j) \in E} (x_i+x_j-2y_{i,j}) \tag{$0^\prime$}$$ subject to $(1)$ and $(2)$. Now dualizing $(1)$ yields a (weighted) Max-Cut problem for each fixed value of the dual multiplier.

Answer 3

The problem you are proposing is closely related to the Maximum Cut with Limited Unbalance which generalizes both the Maximum Bisection problem and the Maximum Cut problem.

The problem is defined as follows. Given vertex set $V$ of cardinality $n$ and edge set $E$, where each edge $(i, j)$ has an integer weight $w_{ij}$, and given a constant $B$, with $0 \leq B \leq n$, find a cut $(S, V\setminus S)$ of $G$ of maximum weight such that the difference between the cardinalities of the two shores of the cut is not greater than $B$. Note that $B$ is equal to zero it is known as the Max Bisection problem, whereas when $B$ is equal to $n − 1$ it is well-known as the Maximum Cut problem.

In a later paper, we proposed an SDP-based polynomial-time approximation algorithm (same style of the famous Goemans's Max Cut algorithm), based on the following model:

$$ \max \left\{\frac{1}{4} \sum_{ij} w_{ij} (1 - x_i x_j) \mid \sum_{ij} x_i x_j \leq B^2, x_i \in \{-1,1\},i=1,\dots,n\right\} $$

The semidefinite relaxation of this binary quadratic program can be formulated as follows:

$$ \max \left\{\frac{1}{4} \sum_{ij} w_{ij} (1 - X_{ij}) \mid \sum_{ij} X_{ij} \leq B^2, X_{ii} = 1,i=1,\dots,n, X \in M_n\right\} $$

where $M_n$ is the set of real, symmetric, positive semidefinite matrices of order $n$.

In the paper, we describe our randomized algorithm, which was implemented in C++ using the very nice DSDP v5.8 solver and the LAPACK linear algebra libraries (in particular to perform the Cholesky decomposition step).

If you cannot access our paper online, I can share by email an archived preprint.