Solving Graph Partitioning on Sparse Graphs: Cuts, Projections, and Extended Formulations

This paper explores new solution approaches for the graph partitioning problem. While the classic formulations for graph partitioning are compact, they either suffer from a poor relaxation, symmetry, or contain a cubic number of constraints regardless of the graph density. These shortcomings often result in poor branch-and-bound performance. We approach this problem from perspective of … Read more

Computational study of a branching algorithm for the maximum k-cut problem

This work considers the graph partitioning problem known as maximum k-cut. It focuses on investigating features of a branch-and-bound method to efficiently obtain global solutions. An exhaustive experimental study is carried out for two main components of a branch-and-bound algorithm: computing bounds and branching strategies. In particular, we propose the use of a variable neighborhood … Read more

A Strictly Contractive Peaceman-Rachford Splitting Method for the Doubly Nonnegative Relaxation of the Minimum Cut Problem

The minimum cut problem, MC, and the special case of the vertex separator problem, consists in partitioning the set of nodes of a graph G into k subsets of given sizes in order to minimize the number of edges cut after removing the k-th set. Previous work on this topic uses eigenvalue, semidefinite programming, SDP, … Read more

Strong Mixed-Integer Formulations for Power System Islanding and Restoration

The Intentional Controlled Islanding (ICI) and the Black Start Allocation (BSA) are two examples of problems in the power systems literature that have been formulated as Mixed Integer Programs (MIPs). A key consideration in both of these problems is that each island must have at least one energized generator. In this paper, we provide three … Read more

Endogenous Price Zones and Investment Incentives in Electricity Markets: An Application of Multilevel Optimization with Graph Partitioning

In the course of the energy transition, load and supply centers are growing apart in electricity markets worldwide, rendering regional price signals even more important to provide adequate locational investment incentives. This paper focuses on electricity markets that operate under a zonal pricing market design. For a fixed number of zones, we endogenously derive the … Read more

Improving the linear relaxation of maximum hBccut with semidefinite-based constraints

We consider the maximum $k$-cut problem that involves partitioning the vertex set of a graph into $k$ subsets such that the sum of the weights of the edges joining vertices in different subsets is maximized. The associated semidefinite programming (SDP) relaxation is known to provide strong bounds, but it has a high computational cost. We … Read more

Global Optimization of Multilevel Electricity Market Models Including Network Design and Graph Partitioning

We consider the combination of a network design and graph partitioning model in a multilevel framework for determining the optimal network expansion and the optimal zonal configuration of zonal pricing electricity markets, which is an extension of the model discussed in [25] that does not include a network design problem. The two classical discrete optimization … Read more

Optimal Price Zones of Electricity Markets: A Mixed-Integer Multilevel Model and Global Solution Approaches

Mathematical modeling of market design issues in liberalized electricity markets often leads to mixed-integer nonlinear multilevel optimization problems for which no general-purpose solvers exist and which are intractable in general. In this work, we consider the problem of splitting a market area into a given number of price zones such that the resulting market design … Read more

Computational study of valid inequalities for the maximum hBccut problem

We consider the maximum k-cut problem that consists in partitioning the vertex set of a graph into k subsets such that the sum of the weights of edges joining vertices in different subsets is maximized. We focus on identifying effective classes of inequalities to tighten the semidefinite programming relaxation. We carry out an experimental study … Read more

Projection Results for the k-Partition Problem

The k-partition problem is an NP-hard combinatorial optimisation problem with many applications. Chopra and Rao introduced two integer programming formulations of this problem, one having both node and edge variables, and the other having only edge variables. We show that, if we take the polytopes associated with the `edge-only’ formulation, and project them into a … Read more