Optimal Residential Coordination Via Demand Response: A Distributed Framework

This paper proposes an optimization framework for retailers that are involved in demand response (DR) programs. In a first phase responsive users optimize their own household consumption, characterizing not only their appliances and equipment but also their comfort preferences. Then, the retailer exploits in a second phase this preliminary non-coordinated solution to implement a strategy … Read more

Branch-and-cut-and-price for the Cardinality-constrained Multi-cycle Problem in Kidney Exchange

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

Branch-and-Cut-and-Price for Multi-Agent Pathfinding

There are currently two broad strategies for optimal Multi-agent Pathfinding (MAPF): (1) search-based methods, which model and solve MAPF directly, and (2) compilation-based solvers, which reduce MAPF to instances of well-known combinatorial problems, and thus, can benefit from advances in solver techniques. In this work, we present an optimal algorithm, BCP, that hybridizes both approaches … Read more

Decomposition-based approaches for a class of two-stage robust binary optimization problems

In this paper, we study a class of two-stage robust binary optimization problems with objective uncertainty where recourse decisions are restricted to be mixed-binary. For these problems, we present a deterministic equivalent formulation through the convexification of the recourse feasible region. We then explore this formulation under the lens of a relaxation, showing that the … Read more

Optimal Aggregated Peak Shaving Via Residential Demand Response: A Framework for Retailers

This paper proposes an optimization framework for retailers that are involved in demand response (DR) programs. In a first phase responsive users optimize their own household consumption, characterizing not only their smart home components but also their comfort preferences. Then, the retailer exploits in a second phase this preliminary non-coordinated solution to implement a peak … Read more

Feeder Routing for Air-to-Air Refueling Operations

We consider the problem of routing a fleet of feeders for civil air-to-air refueling operations. In the air-to-air refueling problem, a fixed set of cruisers requires refueling by a fleet of feeders at fixed locations and fixed points in time. A typical objective function is to minimize the fuel consumption or the total number of … Read more

A Generic Exact Solver for Vehicle Routing and Related Problems

Major advances were recently obtained in the exact solution of Vehicle Routing Problems (VRPs). Sophisticated Branch-Cut-and-Price (BCP) algorithms for some of the most classical VRP variants now solve many instances with up to a few hundreds of customers. However, adapting and reimplementing those successful algorithms for other variants can be a very demanding task. This … Read more

Consensus-Based Dantzig-Wolfe Decomposition

Dantzig-Wolfe decomposition (DWD) is a classical algorithm for solving large-scale linear programs whose constraint matrix involves a set of independent blocks coupled with a set of linking rows. The algorithm decomposes such a model into a master problem and a set of independent subproblems that can be solved in a distributed manner. In a typical … Read more

Avoiding redundant columns by adding classical Benders cuts to column generation subproblems

When solving the linear programming (LP) relaxation of a mixed-integer program (MIP) with column generation, columns might be generated that are not needed to express any integer optimal solution of the MIP. Such columns are called strongly redundant and the dual bound obtained by solving the LP relaxation is potentially stronger if these columns are … Read more

Bin Packing Problem with Time Dimension: An Application in Cloud Computing

Improving energy efficiency and lowering operational costs are the main challenges faced in systems with multiple servers. One prevalent objective in such systems is to minimize the number of servers required to process a given set of tasks under server capacity constraints. This objective leads to the well-known bin packing problem. In this study, we … Read more