Classical facility location models like the P-median problem (PMP) and the uncapacitated fixed-charge location problem (UFLP) implicitly assume that once constructed, the facilities chosen will always operate as planned. In reality, however, facilities “fail” from time to time due to poor weather, labor actions, changes of ownership, or other factors. Such failures may lead to … Read more
We present a lagrangean heuristic based on the time-indexed formulation of the Single Machine Scheduling Problem with Release Dates. We observe that lagrangian relaxation of job constraints leads to a Weighted Stable Set problem on an Interval Graph. The problem is polynomially solvable by a dynamic programming algorithm. Computational experience is reported on instances up … Read more
This paper presents the results of the application of a non-differentiable optimization method in connection with the Vehicle Routing Problem with Time Windows (VRPTW). The VRPTW is an extension of the Vehicle Routing Problem. In the VRPTW the service at each customer must start within an associated time window. The Shortest Path decomposition of the … Read more
Semidefinite programming (SDP) relaxations are proving to be a powerful tool for finding tight bounds for hard discrete optimization problems. This is especially true for one of the easier NP-hard problems, the Max-Cut problem (MC). The well-known SDP relaxation for Max-Cut, here denoted SDP1, can be derived by a first lifting into matrix space and … Read more
In this paper we study two strengthened semidefinite programming relaxations for the Max-Cut problem. Our results hold for every instance of Max-Cut; in particular, we make no assumptions about the edge weights. We prove that the first relaxation provides a strengthening of the Goemans-Williamson relaxation. The second relaxation is a further tightening of the first … Read more
This paper presents an algorithm to obtain near optimal solutions for the Steiner tree problem in graphs. It is based on a Lagrangian relaxation of a multi-commodity flow formulation of the problem. An extension of the subgradient algorithm, the volume algorithm, has been used to obtain lowe r bounds and to estimate primal solutions. Due … Read more