EURO 2024 Copenhagen
Abstract Submission

EURO-Online login

4202. Mixed-integer linear programming formulations and column generation algorithms for the Minimum Normalized Cuts problem on networks

Invited abstract in session TC-29: Exact Algorithms and Formulations for Network Optimization Problems, stream Combinatorial Optimization.

Tuesday, 12:30-14:00
Room: 157 (building: 208)

Authors (first author is the speaker)

1. Diego Ponce
Institute of Mathematics of the University of Seville (IMUS), Universidad de Sevilla
2. Justo Puerto
Estadistica e I.O., Universidad de Sevilla
3. Francisco Temprano Garcia
Stats and OR, Universidad de Sevilla

Abstract

The normalized cut function in networks was introduced by Shi and Malik in 2000 to solve some issues concerning the interpretability of the minimum cut problem, which is a classical problem in graph theory whose aim is to provide the bipartition that minimizes the number of edges between nodes from different subsets, applied to partitioning and districting problems. The minimum k-way normalized cut problem (MkWNCP) tries to minimize the external edge density of each subset of a k-partition, also considering the number of internal edges.
We develop several reformulations using mathematical programming tools to exactly obtain the minimum k-way normalized cut of a graph. This is a challenging task since the normalized cut function is non-linear because it is defined by the ratio of two linear functions of integer variables. We also propose a branch-and-price procedure for the MkWNCP which scales better than the compact formulations. Extensive computational experiments assess the usefulness of these methods to solve the k-way normalized cut problem on large graphs and random graphs. In addition, all methods have been analyzed and studied in order to try to improve them as much as possible.

Keywords

Status: accepted

Back to the list of papers