We investigate the multi-trip elementary shortest path problem (MESPPRC) with resource constraints in which the objective is to find a shortest path between a source node and a sink node such that nodes other than the specified replenishment node are visited at most once and resource constraints are not violated. After each visit to the … Read more
Given a bipartite graph G = (S , T , E ), we consider the problem of finding k bipartite subgraphs, called clusters, such that each vertex i of S appears in exactly one of them, every vertex j of T appears in each cluster in which at least one of its neighbors appears, and … Read more
We consider a complex planning problem in integrated steel production. A sequence of coils of sheet metal needs to be color coated in consecutive stages. Di erent coil geometries and changes of coatings may necessitate time-consuming setup work. In most coating stages one can choose between two parallel color tanks in order to reduce setup times. … Read more
We report on experiments with turning the branch-cut-and-price framework SCIP into a generic branch-cut-and-price solver. That is, given a mixed integer program (MIP), our code performs a Dantzig-Wolfe decomposition according to the user’s specification, and solves the resulting re-formulation via branch-and-price. We take care of the column generation subproblems which are solved as MIPs themselves, … Read more
Resource leveling is a variant of resource-constrained project scheduling in which a non-regular objective function, the resource availability cost, is to be minimized. We present a branch-and-price approach together with a new heuristic to solve the more general turnaround scheduling problem. Besides precedence and resource constraints, also availability periods and multiple modes per job have … Read more
In many telecommunication networks a given set of client nodes must be served by different sets of facilities, providing different services and having different capabilities, which must be located and dimensioned in the design phase. Network topology must be designed as well, by assigning clients to facilities and facilities to higher level entities, when necessary. … Read more
We study the best OSPF style routing problem in telecommunication networks, where weight management is employed to get a routing configuration with the minimum oblivious ratio. We consider polyhedral demand uncertainty: the set of traffic matrices is a polyhedron defined by a set of linear constraints, and the performance of each routing is assessed on … Read more
This paper studies location routing and scheduling problems, a class of problems in which the decisions of facility location, vehicle routing, and route assignment are optimized simultaneously. For a version with capacity and time restrictions, two formulations are presented, one graph-based and one set-partitioning-based. For the set-partitioning-based formulation, valid inequalities are identified and their effectiveness … Read more
We investigate the problem of simultaneously determining the location of facilities and the design of vehicle routes to serve customer demands under vehicle and facility capacity restrictions. We present a set-partitioning-based formulation of the problem and study the relationship between his formulation and the graph-based formulations that have been used in previous studies of this … Read more
We investigate a network design problem under traffic uncertainty which arises when provisioning Virtual Private Networks (VPNs): given a set of terminals that must communicate with one another, and a set of possible traffic matrices, sufficient capacity has to be reserved on the links of the large underlying public network so as to support all … Read more