Global Optimization of the Maximum K-Cut Problem
Bibliographic record
Abstract
In graph theory, the maximum k-cut (max-k-cut) problem is a representative problem of the class of N P-hard combinatorial optimization problems.It arises in many industrial applications and the objective of this problem is to partition vertices of a given graph into at most k partitions such that the total weight of the cut is maximized.The methods proposed in the literature to optimally solve the max-k-cut employ, usually, the associated semidefinite programming (SDP) relaxation in a branch-and-bound framework.In comparison with the linear programming (LP) relaxation, the SDP relaxation is stronger but it suffers from high CPU times.Therefore, methods based on SDP cannot solve large problems.This thesis introduces an efficient branch-and-bound method to solve the max-k-cut problem by using tightened SDP and LP relaxations.This thesis presents three approaches to improve the solutions of the problem.The first approach focuses on identifying relevant classes of inequalities to tighten the relaxations of the max-k-cut.This approach carries out an experimental study of four classes of inequalities from the literature: clique, general clique, wheel and bicycle wheel.In order to include these inequalities, we employ a cutting plane algorithm (CPA) to add only the most important inequalities in practice and we design several separation routines to find violations in a relaxed solution.Computational results suggest that the wheel inequalities are the strongest by far.Moreover, the inclusion of these inequalities in the max-k-cut improves the bound of the SDP formulation by more than 2%.The second approach introduces the SDP-based constraints to strengthen the LP relaxation.Moreover, the CPA is improved by exploiting the early-termination technique of an interior-point method.Computational results show that the LP relaxation with the SDP-based inequalities outperforms the SDP relaxations for many instances, especially for a large number of partitions (k ≥ 7).The third approach investigates the branch-and-bound method using both previous approaches.Four components of the branch-and-bound are considered.First, four heuristic methods are presented to find a feasible solution: the iterative clustering heuristic, the multiple operator heuristic, the variable neighborhood search, and the greedy randomized adaptive search procedure.The second procedure analyzes the dichotomic and polytomic strategies to split a subproblem.The third feature studies five branching rules.Finally, for the node selection, we consider the following strategies: best-first search, depth-first search, and breadth-first search.For each component, we provide computational tests for different values of k.Computational results show that the proposed exact method is able to uncover many solutions.viii Each one of these three approaches contributed to the design of an efficient method to solve the max-k-cut problem.Moreover, the proposed approaches can be extended to solve generic mixinteger SDP problems.
Fetched live from OpenAlex and de-inverted. Abstracts are not stored in this database: the inverted indexes are 8.6 GB of the frame’s 9.3 GB of text, and the host has 13 GB free.
How this classification was reachedexpand
Full frame machine prediction
Teacher imitationNot calibrated prevalence, not ground truth. Human validation pending. The Gemma side is a direct model label for every work in the frame, read from the title-only record. The Codex side is a classifier learned from the 10,348 direct Codex labels and calibrated to design-weighted sample rates; fields without enough sample support carry no Codex call. Candidate is the union of the two sides; consensus is their intersection. These outputs are machine_predicted_unvalidated and are not human labels.
Distilled classifier scores by category (both heads)
| Category | Codex | Gemma |
|---|---|---|
| Metaresearch | 0.002 | 0.008 |
| Meta-epidemiology (narrow) | 0.001 | 0.001 |
| Meta-epidemiology (broad) | 0.002 | 0.001 |
| Bibliometrics | 0.001 | 0.001 |
| Science and technology studies | 0.001 | 0.001 |
| Scholarly communication | 0.003 | 0.002 |
| Open science | 0.002 | 0.002 |
| Research integrity | 0.002 | 0.002 |
| Insufficient payload (model declined to judge) | 0.018 | 0.002 |
Machine scores (provisional)
The two teacher heads of the student model, read on this work. A score orders the frame for review; it never asserts a category, and the validation status ships verbatim with every row.
Baseline scores from an immature model (maturity gate not passed, 7 training rounds). Scores rank; they never assert a category.
score_only:v0-immature-baseline · verbatim from the scoring run: score_only means the number may rank works, and no category label ships from itClassification
machine, unvalidatedMachine predicted; a candidate call from one source (direct Gemma or distilled Codex), not a consensus.
How this classification was reached, model by model and score by score, is at the end of the page under "How this classification was reached".