Geoscience Reference
In-Depth Information
one to find good upper bounds (primal heuristics) and another to obtain lower
bounds and cutting planes (dual heuristics). Subgradient optimization is applied to
find better lower bounds. This last technique is also used in Beasley (
1987
)where
a branch-and-bound method is proposed whose main elements are a dual ascent
procedure and subgradient optimization. This algorithm is improved in Beasley and
Jørnsten (
1992
) by incorporating the heuristic published in Beasley (
1990
) along
with some other enhancements.
Of special interest is Neebe (
1988
) which solves the problem of calculating for
every possible maximum distance the minimum number of facilities that cover
all the nodes (instead of solving the set covering problem for a single maximum
distance). This approach uses a chain of linear programming relaxations and, after
every linear model, some tests are used to obtain an integer solution. Although
these tests do not guarantee that an optimal integer solution will be found, the
author claims to solve to optimality almost all the instances he considers (up to
100 nodes). Each of the auxiliary problems is solved with a modification of the
procedure suggested in Lemke et al. (
1971
).
Fisher and Kedia (
1990
) propose an algorithm for a model which includes
both set covering and set partitioning constraints. It is an exact branch-and-bound
algorithm that uses greedy and 3-opt heuristics applied to the dual problem.
Exploiting the use of bounds, Mannino and Sassano (
1995
) propose a lower
bounding procedure and a branch-and-bound scheme to solve set covering problems
that appear in Steiner triple systems (a certain matrix structure). Balas and Carrera
(
1996
) develop a procedure applied to a Lagrangian dual problem at each node that
combines subgradient optimization with primal and dual heuristics which tighten
the upper and lower bounds. These strengthened bounds allow to fix some variables.
In general, Lagrangian methods are the most extended and effective methods in
the literature. More recently, Avella et al. (
2009
) propose a cutting plane algorithm
where the separation algorithm is solved in an exact way on a subproblem defined
by a subset of the original constraints and variables of the set covering problem
formulation.
On the contrary, not many exact algorithms have been developed for the Maximal
Covering Location Problem. Downs and Camm (
1996
) obtain a primal solution
using the greedy heuristic of Church and ReVelle (
1974
). They use complementary
slackness conditions for the maximal covering problem formulation to obtain a
dual feasible solution. This solution is the starting vector of multipliers for the
Lagrangian dual problem of MCLP which is solved with subgradient optimization.
If an integer solution is not obtained, branch-and-bound is used.
5.5
Approximate Solution Methods
As it happens with any hard optimization problem, there are more heuristic
algorithms than exact methods in the literature. Roth (
1969
), the first paper to
formulate the Set Covering Problem, already proposes a probabilistic heuristic. A
