In this article, we address the preemptive Resource-Constrained Precedence Scheduling Problem. We propose two mixed integer formulations containing an exponential number of variables and inequalities. An antichain is ...
详细信息
In this article, we address the preemptive Resource-Constrained Precedence Scheduling Problem. We propose two mixed integer formulations containing an exponential number of variables and inequalities. An antichain is a set of pairwise incomparable elements with respect to the precedence constraints. In the first formulation, the integer variables are associated with the antichains. For the second, the integer variables are limited to a particular subset of antichains. We propose two branchand-cut-and-pricealgorithms for each of these formulations. We introduce some valid inequalities in order to reinforce the second formulation. Finally, we give some computational results on instances of the PSPLIB and compare the formulations.
characteristics of a network satisfying requirements on connectivity, capacity, and level-of-service. It finds applications in logistics and transportation, telecommunications, data sharing, energy distribution, and d...
详细信息
characteristics of a network satisfying requirements on connectivity, capacity, and level-of-service. It finds applications in logistics and transportation, telecommunications, data sharing, energy distribution, and distributed computing. In multicommodity network design, one is required to design a network minimizing the installation cost of its arcs and the operational cost to serve a set of point-to-point connections. The definition of this prototypical problem was recently enriched by additional constraints imposing that each origin-destination of a connection is served by a single path satisfying one or more level-of-service requirements, thus defining the Network Design with Service Requirements. These constraints are crucial, for example, in telecommunications and computer networks to ensure reliable and low-latency communication. In this paper we provide a new formulation for the problem, where variables are associated with paths satisfying the end-to-end service requirements. We present a fast algorithm for enumerating all the exponentially many feasible paths, and when this is not viable, we provide a column generation scheme that is embedded into a branch-and-cut-and-price algorithm. Extensive computational experiments on a large set of instances show that our approach can move a step further in the solution of the network design with service requirements compared with the current state-of-the-art.
This paper introduces the vehicle routing problem with time windows and shifts (VRPTWS). At the depot, several shifts with nonoverlapping operating periods are available to load the planned trucks. Each shift has a li...
详细信息
This paper introduces the vehicle routing problem with time windows and shifts (VRPTWS). At the depot, several shifts with nonoverlapping operating periods are available to load the planned trucks. Each shift has a limited loading capacity. We solve the VRPTWS exactly by a branch-and-cut-and-price algorithm. The master problem is a set partitioning with an additional constraint for every shift. Each constraint requires the total quantity loaded in a shift to be less than its loading capacity. For every shift, a pricing subproblem is solved by a label-setting algorithm. Shift capacity constraints define knapsack inequalities;hence we use valid inequalities inspired from knapsack inequalities to strengthen the linear progr amming relaxation of the master problem when solved by column generation. In particular, we use a family of tailored robust cover inequalities and a family of new nonrobust cover inequalities. Numerical results show that nonrobust cover inequalities significantly improve the algorithm.
Given a directed graph G(V,A), the p-Median problem consists of determining p nodes (the median nodes) minimizing the total distance from the other nodes of the graph. We present a branch-and-cut-and-price algorithm y...
详细信息
Given a directed graph G(V,A), the p-Median problem consists of determining p nodes (the median nodes) minimizing the total distance from the other nodes of the graph. We present a branch-and-cut-and-price algorithm yielding provably good solutions for instances with vertical bar V vertical bar <= 3795. Key ingredients of the algorithm are a delayed column-and-row generation technique, exploiting the special structure of the formulation, to solve the LP-relaxation, and cutting planes to strengthen the formulation and limit the size of the enumeration tree.
暂无评论