6
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ I can't help with relevant references, but are you interested in suggestions (without citation) for heuristics? $\endgroup$
    – prubin
    Nov 12 at 16:57
  • $\begingroup$ @prubin yes, please, any answer that can even give me a start point of where to begin would be great, thanks. $\endgroup$ Nov 12 at 19:37
5
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ Many thanks for the detailed answer! $\endgroup$ Nov 15 at 16:26
  • $\begingroup$ do you have a good reference for where I can make a good start on a simple genetic algorithm that you used in Addendum 2? ideally something that introduces well the idea of a genetic algorithm (I have only a high level idea of how they work). I am really just looking for something that is relatively easy to implement -- for my purposes the heuristic does not need to be perfect, that is not what my work is trying to demonstrate. is the genetic algorithm that you ran in addendum 2 similar to the GA you mentioned at the start of the question? $\endgroup$ Nov 23 at 13:16
  • $\begingroup$ I wrote a blog post about my experiments, which includes a link to an R notebook containing my code. As far as references go, I'm afraid I don't know any easy intro-level ones. (I learned about GAs from some of the seminal papers, so long ago that I don't recall the references.) I suspect that contemporary intro to OR books will in some cases provide easy introductions ... but not necessarily to GAs using permutation chromosomes, which is relatively recent and a bit "niche". $\endgroup$
    – prubin
    Nov 23 at 16:20
  • $\begingroup$ If you want a citation on "random key" GAs (which include permutation chromosomes), you might look at: Bean, James C. "Genetic Algorithms and Random Keys for Sequencing and Optimization". ORSA Journal on Computing (1994). Vol. 6, Nr. 2, pp. 154-160. $\endgroup$
    – prubin
    Nov 23 at 16:39
  • $\begingroup$ oh wow, I'll definitely check your blog post out! thanks for all the info! $\endgroup$ Nov 23 at 16:43
5
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ thanks for the answer! $\endgroup$ Nov 15 at 16:26
  • $\begingroup$ I am quite interested now in this MIP formulation of the problem, however I am not quite sure what you do from line (2) beyond. What is this binary decision variable $y_{i,j}$? do we need one for every possible edge in the graph? $\endgroup$ Nov 23 at 13:09
  • $\begingroup$ Yes, $y_{i,j}$ represents $x_i x_j$ for $(i,j)\in E$. The formulation enforces only $y_{i,j}\ge x_i x_j$ because the other direction will naturally be satisfied at optimality due to the $-2$ coefficient in the objective. You can also relax $y$ to $y_{i,j}\ge 0$ for the same reason. $\endgroup$
    – RobPratt
    Nov 23 at 14:14
  • $\begingroup$ Thanks @RobPratt. $\endgroup$ Nov 23 at 14:28
4
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ thanks for the references and answer. I'll check the references out! I should be able to access via my university :-) $\endgroup$ Nov 15 at 16:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.