In this paper we implement a branch and price (BP) algorithm for a time dependent vehicle routing problem with time windows (TDVRPTW) in which the goal is to minimize the total route duration (DM-TDVRPTW). The travel time between two customers depends on the departure time and, thus, it need not remain fixed along the planning … Read more
A 0/1 matrix has the Consecutive Ones Property if a permutation of its columns exists such that the ones appear consecutively in each row. In many applications, one has to find a matrix having the consecutive ones property and optimizing a linear objective function. For this problem, literature proposes, among other approaches, an Integer Linear … Read more
One of the challenges of cloud computing is to optimally and efficiently assign virtual machines to physical machines. The aim of telecommunication operators is to mini- mize the mapping cost while respecting constraints regarding location, assignment and capacity. In this paper we first propose an exact formulation leading to a 0-1 bilinear constrained problem. Then … Read more
Covering problems constitute an important family of facility location problems. This paper intro- duces a new exact algorithm for two important members of this family: i) the maximal covering location problem, which requires finding a subset of facilities that maximizes the amount of demand covered while respecting a budget constraint on the cost of the … Read more
Sparse regression and variable selection for large-scale data have been rapidly developed in the past decades. This work focuses on sparse ridge regression, which enforces the sparsity by use of the L0 norm. We first prove that the continuous relaxation of the mixed integer second order conic (MISOC) reformulation using perspective formulation is equivalent to … Read more
We study a multiple-vehicle routing problem with a minimum makespan objective and compatibility constraints. We provide an approximation algorithm and a nearly-matching hardness of approximation result. We also provide computational results on benchmark instances with diverse sizes showing that the proposed algorithm (i) has a good empirical approximation factor, (ii) runs in a short amount … Read more
This paper studies extended formulations for radial cones at vertices of polyhedra, where the radial cone of a polyhedron P at a vertex v of P is the polyhedron defined by the constraints of P that are active at v. Given an extended formulation for P, it is easy to obtain an extended formulation of … Read more
Two nodes of a wireless network may not be able to communicate with each other directly perhaps due to obstacles or insufficient signal strength. This necessitates the use of intermediate nodes to relay information. Often, one designates a (preferably small) subset of them to relay these messages (i.e., to serve as a virtual backbone for … Read more
We analyze the computational complexity of the synthesis problem of decentralized energy systems. This synthesis problem consists of combining various types of energy conversion units and determining their sizing as well as operations in order to meet time-varying energy demands while maximizing an objective function, e.g., the net present value. In this paper, we prove … Read more
We study the following optimization problem over a dynamical system that consists of several linear subsystems: Given a finite set of n-by-n matrices and an n-dimensional vector, find a sequence of K matrices, each chosen from the given set of matrices, to maximize a convex function over the product of the K matrices and the … Read more