We investigate the NP-hard problem of computing the spark of a matrix (i.e., the smallest number of linearly dependent columns), a key parameter in compressed sensing and sparse signal recovery. To that end, we identify polynomially solvable special cases, gather upper and lower bounding procedures, and propose several exact (mixed-)integer programming models and linear programming … Read more
This paper studies the Hamiltonian p-median problem defined on a directed graph, which consists of finding p mutually disjoint circuits of minimum total cost, such that each node of the graph is included in one of the circuits. Earlier formulations are based on viewing the problem as one resulting from the intersection of two subproblems. … Read more
We investigate how the numerical properties of the LP relaxations evolve throughout the solution procedure in a solver employing the branch-and-cut algorithm. The long-term goal of this work is to determine whether the effect on the numerical conditioning of the LP relaxations resulting from the branching and cutting operations can be effectively predicted and whether … Read more
Food rescue organizations collect and re-distribute surplus perishable food for hunger relief. We propose novel approaches to address this humanitarian logistics challenge and find envy-free allocations of the rescued food together with least travel cost routes. We show that this food rescue and delivery problem is NP-hard and we present a cutting-plane algorithm based on … Read more
We focus on a problem of locating recharging stations in one-way station based electric car sharing systems which operate under demand uncertainty. We model this problem as a mixed integer stochastic program and develop a Benders decomposition algorithm based on this formulation. We integrate a stabilization procedure to our algorithm and conduct a large-scale experimental … Read more
Mixed-integer second-order cone optimization (MISOCO) has become very popular in the last decade. Various aspects of solving these problems in Branch and Conic Cut (BCC) algorithms have been studied in the literature. This study aims to fill a gap and provide a novel way to find feasible solutions early in the BCC algorithm. Such solutions … Read more
Extreme events such as disasters cause partial or total disruption of basic services such as water, energy, communication and transportation. In particular, roads can be damaged or blocked by debris, thereby obstructing access to certain affected areas. Thus, restoration of the damaged roads is necessary to evacuate victims and distribute emergency commodities to relief centers … Read more
We present a new tool for generating cutting planes for NP-hard combinatorial optimisation problems. It is based on the concept of gadgets — small subproblems that are “glued” together to form hard problems — which we borrow from the literature on computational complexity. Using gadgets, we are able to derive huge (exponentially large) new families … Read more
It is common knowledge that symmetries arising in integer programs could impair the solution process, in particular when symmetric solutions lead to an excessively large branch and bound (B&B) search tree. Techniques like isomorphic pruning [11], orbital branching [16] and orbitopal fixing [8] have been shown to be essential to solve very symmetric instances from … Read more
Problem instances found in the literature that are used in computational studies of the resource constrained project scheduling problem, typically include only a few resources. In some practical applications, however, the number of resources may be significantly higher. In this paper, problem instances with a large number of resources are considered and a Benders decomposition … Read more