\(\) We consider the bilevel knapsack problem with interdiction constraints, a fundamental bilevel integer programming problem which generalizes the 0-1 knapsack problem. In this problem, there are two knapsacks and \(n\) items. The objective is to select some items to pack into the first knapsack such that the maximum profit attainable from packing some of … Read more
The objective of this paper is to develop a scalable binary linear programming model for finding the optimal aggregation of communes into spatially contiguous administrative territorial units (ATUs) constrained on certain balancing criteria. The requirement for the ATUs to be contiguous represents the main computational bottleneck and, therefore, it prevents one from using such models … Read more
The capacitated vehicle routing problem with stochastic demands (CVRPSD) is a variant of the deterministic capacitated vehicle routing problem where customer demands are random variables. While the most successful formulations for several deterministic vehicle-routing problem variants are based on a set-partitioning formulation, adapting such formulations for the CVRPSD under mild assumptions on the demands remains … Read more
We propose a novel approach to solve K-adaptability problems with convex objective and constraints and integer first-stage decisions. A logic-based Benders decomposition is applied to handle the first-stage decisions in a master problem, thus the sub-problem becomes a min-max-min robust combinatorial optimization problem that is solved via a double-oracle algorithm that iteratively generates adverse scenarios … Read more
Abstract. Citation Chaves et al., A parallel branch-and-cut and an adaptive metaheuristic to solve the Family Traveling Salesman Problem. Submitted to …
Motivated by applications in cloud computing, we study a temporal bin packing problem with jobs that occupy half of a bin’s capacity. An instance is given by a set of jobs, each with a start and end time during which it must be processed, i.e., assigned to a bin. A bin can accommodate two jobs … Read more
We consider the temporal bin packing problem with fire-ups (TBPP-FU), a branch of operations research recently introduced in multi-objective cloud computing. In this scenario, any item is equipped with a resource demand and a lifespan meaning that it requires the bin capacity only during that time interval. We then aim at finding a schedule minimizing … Read more
Motivated by applications in political districting, we consider the task of partitioning the n vertices of a planar graph into k connected components. We propose an extended formulation that has two desirable properties: (i) it uses just O(n) variables, constraints, and nonzeros, and (ii) it is perfect. To explore its ability to solve real-world problems, … Read more
Additive Manufacturing (AM), the technology of rapid prototyping directly from 3D digital models, has made a significant impact on both academia and industry. When facing the growing demand of AM services, AM production planning (AMPP) plays a vital role in reducing makespan and costs for AM service companies. This research focuses on the AMPP problem … Read more
We study the D-optimal Data Fusion (DDF) problem, which aims to select new data points, given an existing Fisher information matrix, so as to maximize the logarithm of the determinant of the overall Fisher information matrix. We show that the DDF problem is NP-hard and has no constant-factor polynomial-time approximation algorithm unless P = NP. … Read more