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
This paper presents an algorithm aiming to compute an upper bound set for a multi-objective linear optimisation problem with binary variables (p-01LP). Inspired by the well known « Feasibility Pump » algorithm in single objective optimisation, it belongs to the class of primal heuristics. The proposed algorithm, named « Gravity Machine », aims to deal … Read more
This paper establishes and analyzes a service center location model with a simple but novel decision-dependent demand induced from a maximum attraction principle. The model formulations are investigated in the distributionally-robust optimization framework for the capacitated and uncapacitated cases. A statistical model that is based on the maximum attraction principle for estimating customer demand and … Read more
Linear complementarity problems (LCPs) are an important modeling tool for many practically relevant situations but also have many important applications in mathematics itself. Although the continuous version of the problem is extremely well studied, much less is known about mixed-integer LCPs (MILCPs) in which some variables have to be integer-valued in a solution. In particular, … Read more
Semidefinite programs (SDPs) can be solved in polynomial time by interior point methods. However, when the dimension of the problem gets large, interior point methods become impractical in terms of both computational time and memory requirements. Certain first-order methods, such as Alternating Direction Methods of Multipliers (ADMMs), established as suitable algorithms to deal with large-scale … Read more
The Graphical Traveling Salesperson Problem (GTSP) is the problem of assigning, for a given weighted graph, a nonnegative number x_e to each edge e such that the induced multi-subgraph is of minimum weight among those that are spanning, connected and Eulerian. Naturally, known mixed-integer programming formulations use integer variables x_e in addition to others. Denis … Read more
In this work we investigate the min-max-min robust optimization problem applied to combinatorial problems with uncertain cost-vectors which are contained in a convex uncertainty set. The idea of the approach is to calculate a set of k feasible solutions which are worst-case optimal if in each possible scenario the best of the k solutions would … Read more
Kidney exchange programmes increase the rate of living donor kidney transplants, and operations research techniques are vital to such programmes. These techniques, as well as changes to policy regarding kidney exchange programmes, are often tested using random instances created by a Saidman generator. We devise a new matheuristic that can optimally solve a benchmark set … Read more
We introduce a new graph-theoretic paradigm called a graph signature that describes persistent patterns in a sequence of graphs. This framework is motivated by the need to detect subgraphs of significance in temporal networks, e.g., social and biological networks that evolve over time. Because the subgraphs of interest may not all “look alike” in the … Read more
In this paper, we provide an equivalent condition for the Chvatal-Gomory (CG) closure of a closed convex set to be finitely-generated. Using this result, we are able to prove that, for any closed convex set that can be written as the Minkowski sum of a compact convex set and a closed convex cone, its CG … Read more