Search

In the context of community detection, correlation clustering (CC) provides a measure of balance for social networks as well as a tool to explore their structures. However, CC does not encompass features such as the mediation between the clusters, which could be all the more relevant with the recent rise of ideological polarization. In this work, we study correlation clustering under mediation (CCM), a new variant of CC in which a set of mediators is determined. This new signed graph clustering problem is proved to be NP-hard and formulated as an integer programming formulation. An extensive investigation of the mediation set structure leads to the development of two efficient exact enumeration algorithms for CCM. The first one exhaustively enumerates the maximal sets of mediators in order to provide several relevant solutions. The second algorithm implements a pruning mechanism, which drastically reduces the size of the exploration tree in order to return a single optimal solution. Computational experiments are presented on two sets of instances: signed networks representing voting activity in the European Parliament and random signed graphs. History: Accepted by Van Hentenryck, Area Editor for Pascal. Funding: This work was supported by Fondation Mathématique Jacques Hadamard [Grant P-2019-0031]. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information (https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2022.0129) as well as from the IJOC GitHub software repository (https://github.com/INFORMSJoC/2022.0129). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/. [ABSTRACT FROM AUTHOR]

We propose a two‐stage recoverable robustness approach that minimizes the recovery cost. In many applications, once the uncertainty ξ$$ \xi $$ is revealed, it can be more important to recover a solution xξ$$ {x}^{\xi } $$ which is as similar as possible to the nominal solution xnom$$ {x}^{nom} $$ than to minimize the nominal objective value of xξ$$ {x}^{\xi } $$. This for example occurs when the nominal solution is implemented on a regular basis or when the uncertainty is revealed late. We define the proactive problem which minimizes the weighted recovery costs over a discrete set of scenarios while ensuring optimality of the nominal objective value of xnom$$ {x}^{nom} $$. We model the recovery cost of a scenario by a distance between the first‐stage nominal solution and the second‐stage solution recovered for this scenario. We show for two different solution distances dval$$ {d}_{val} $$ and dstruct$$ {d}_{struct} $$ that the proactive problem is 풩풫‐hard for both the integer min‐cost flow problem with uncertain arc demands and for the integer max‐flow problem with uncertain arc capacities. For these two problems, we prove that once uncertainty is revealed, even identifying a reactive solutionxr$$ {x}^r $$ with a minimal distance to a given solution xnom$$ {x}^{nom} $$ is 풩풫‐hard for dstruct$$ {d}_{struct} $$, and is polynomial for dval$$ {d}_{val} $$. We highlight the benefits of the proactive approach in a case study on a railroad planning problem. First, we compare it to the anchored and the k$$ k $$‐distance approaches. Then, we show the efficiency of the proactive solution over reactive solutions. Finally, we illustrate the recovery cost reduction when relaxing the optimality constraint on the nominal objective of the proactive solution xnom$$ {x}^{nom} $$. We also consider the min–max version of the proactive problem where we minimize the maximal recovery cost over all scenarios. We show that the same complexity results hold for this version. We also exhibit a class of problems for which the set of extreme points of the convex hull of a discrete uncertainty set always contain a worst‐case scenario. We show that this result does not hold for three distinct classes deduced from the first one. [ABSTRACT FROM AUTHOR]

The K‐partitioning problem consists in partitioning the nodes of a complete graph G = (V, E) with weights on the edges in exactly K clusters such that the sum of the weights of the edges inside the clusters is minimized. For this problem, we propose two node‐cluster formulations adapted from the literature on similar problems as well as two edge‐representative formulations. We introduced the first edge‐representative formulation in a previous work while the second is obtained by adding an additional set of edge variables. We compare the structure of the polytopes of the two edge‐representative formulations and identify a new family of facet‐defining inequalities. The quality of the linear relaxation and the resolution times of the four formulations are compared on various data sets. We provide bounds on the relaxation values of the node‐cluster formulations which may account for their low performances. Finally, we propose a branch‐and‐cut strategy, based on the edge‐representative formulations, which performs even better. [ABSTRACT FROM AUTHOR]