unsplittable flow

A cardinality-indexed extended formulation with valid inequalities for unsplittable multicommodity network design

Categories Branch and Cut Algorithms, Facility Planning and Design, Integer Programming Tags , , , ,

We study the unsplittable multicommodity fixed-charge network design problem, in which every commodity follows a single path and each arc is installed at most once. Its linear relaxation is weak because a commodity may occupy a fraction of an arc. We propose an extended formulation that indexes the variables of each arc by the number … Read more

Resource Allocation with Time Intervals

Categories Combinatorial Optimization, Scheduling Tags , ,

We study a resource allocation problem where jobs have the following characteristics: Each job consumes some quantity of a bounded resource during a certain time interval and induces a given profit. We aim to select a subset of jobs with maximal total profit such that the total resource consumed at any point in time remains … Read more