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
The establishment of kidney exchange programs has dramatically improved rates for kidney transplants by matching donors to compatible patients who would otherwise fail to receive a kidney for transplant. Rather than simply swapping kidneys between two patient-donor pairs, having multiple patient-donors pairs simultaneously donate kidneys in a cyclic manner enables all participants to receive a … Read more
Data are often represented as graphs. Many common tasks in data science are based on distances between entities. While some data science methodologies natively take graphs as their input, there are many more that take their input in vectorial form. In this survey we discuss the fundamental problem of mapping graphs to vectors, and its … Read more
For sparse graphs, the odd cycle polytope can be used to compute useful bounds for the maximum stable set problem quickly. Yannakakis introduced an extended formulation for the odd cycle inequalities of the stable set polytope in 1991, which provides a direct way to optimize over the odd cycle polytope in polynomial time, although there … Read more
Cutting planes from the Boolean Quadric Polytope (BQP) can be used to reduce the optimality gap of the NP-hard nonconvex quadratic program with box constraints (BoxQP). It is known that all cuts of the Chvátal-Gomory closure of the BQP are A-odd cycle inequalities. We obtain a compact extended relaxation of all A-odd cycle inequalities, which … Read more
Data quality in population surveys suffers from missing responses. We use combinatorial optimization to create a complete and coherent data set. The methods are based on the widespread nearest neighbor hot deck imputation method that replaces the missing values with observed values from a close unit, the so-called donor. As a repeated use of donors … Read more
The minimum color-degree perfect b-matching roblem (Col-BM) is a new extension of the perfect b-matching problem to edge-colored graphs. The objective of Col-BM is to minimize the maximum number of differently colored edges in a perfect b-matching that are incident to the same node. We show that Col-BM is NP-hard on bipartite graphs by a … Read more
In this paper it is considered how graphs can be used to generate copositive matrices, and necessary and sufficient conditions are given for these generated matrices to then be irreducible with respect to the set of positive semidefinite plus nonnegative matrices. This is done through combining the well known copositive formulation of the stable set … Read more
In 2013, Orlin proved that the max flow problem could be solved in O(nm) time. His algorithm was the fastest for very sparse graphs. If the graph was not sufficiently sparse, the fastest running time was an algorithm due to King, Rao, and Tarjan. We describe a new variant of the excess scaling algorithm for … Read more
In the last decades, research on emergency traffic management has received high attention from the operations research community and many pioneer researchers have established it as one of the most fertile research areas. We consider the computationally hard flows over time problems from wider perspective including flow/time dependent attributes (dynamic flows), a possibility of flows … Read more