Closure problem

From formulasearchengine
Revision as of 04:03, 27 August 2012 by en>David Eppstein (more footnotes; templatize refs)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigation Jump to search

Template:Lead too short Template:Orphan Template:More footnotes

A Closure problem is a problem in graph theory for finding a set of vertices in a directed graph such that there are no edges from the set to the rest of the graph. More specifically, the minimum closure problem asks for a set of this type with the minimum possible weight in a weighted graph.

Closure problem

Definition

In a directed graph G = (VA), a set S of vertices is said to be closed if every successor of every vertex in S is also in S. Equivalently, S is closed if it has no outgoing edge.

It may be assumed without loss of generality that G is a directed acyclic graph. For, if it is not acyclic, each of its strongly connected components must either be entirely contained in or entirely disjoint from any closed set. Therefore, the closures of G are in one-to-one correspondence with the closures of the condensation of G, a directed acyclic graph that has one vertex for each strongly connected component of G. In weighted closure problems, one may set the weight of any vertex of the condensation to the sum of the weights of the vertices in the corresponding strongly connected component of G.

Minimum closure problem

For a directed graph G = (VA) with vertex weights wi the minimum closure problem is to find a closed set of total minimum weight. If all the weights are positive or negative, the minimum closure problem is trivial. Indeed, if all weights are positive the empty subgraph is a solution, and if all weights are negative, the whole graph is solution. We may therefore assume that G has both positive and negative weights.

Open-pit mining

Picard studied the closure problem on the open-pit mining problem, which he modeled as a maximum-closure problem.

Maximum and minimum closure problem

File:Closure.png
Setting up the graph for a closure problem

In the maximum closure problem a directed graph G = (VA) with vertex weights wi is given and we want to find a closed subset of vertices V ' such that is maximum. Picard showed that the maximum closure problem can be solved using a minimum cut procedure. Additionally it is clear that the selection problem is closure problem on a bipartite graph therefore the selection problem is a special case of the closure problem. Maximum and minimum closure problems can be converted to each other by negating the vertex weights. A maximum closure problem can be formulated as follows

Where xi is 1 if the vertex is in the closure and it is 0 otherwise, and the first constraint ensures that if a vertex is in the closure its successor is also in it. Since each row has at most one 1 and one −1 we know that the constraint matrix is totally unimodular and an integer solution is obtained by solving the LP relaxation of the problem.

In order to solve the maximum closure problem we can use the max-flow min-cut theorem. Let us construct the s-t graph for maximum closure problem. The graph has a vertex j for each variable xj. We also add a source s and a sink vertex t. If the weight of the variable wj is positive we include an arc from the source to the vertex j with capacity wj. If the weight is negative we add the arc from j to the sink vertex (t) with capacity −wj. Each inequality xjxi is associated with an arc (ij) with capacity ∞. Let V+be the set of vertices with positive weights and V the set of vertices with negative weights. Figure \ref{fig:cl4} shows the graph constructed for the closure problem. We can find the minimum cut in this graph by solving a max-flow problem from source to the sink . The source set of a minimum cut separating s from t is a maximum closure in the graph. This statement holds because the minimum cut is finite and cannot include any arc from A that has the weight equal to ∞ [5]. Minimizing the value of the finite cut is equivalent to maximizing the sum of weights of the vertices in the source set of the finite cut. Denote (A,B) the collection of arc with tails at A and heads at B. Also where cijis the capacity of arc (i,j). Let . For a finite cut we have:

In the last expression is a constant. Therefore the closed set of minimum weight is also the sink set of the minimum cut and vice versa—the sink set of a minimum cut (without t), which has to be finite, also minimized the weight of the closure.

History

During the 1970s J.C. Picard was working on the open-pit mining problem and during that time worked on generalizing the selection problem to the closure problem. During that time the mining industry was developing optimization methods on their own. Picard's contribution introduced the closure problem to the mining industry.

References

  • {{#invoke:citation/CS1|citation

|CitationClass=citation }}.

  • {{#invoke:citation/CS1|citation

|CitationClass=citation }}.

  • {{#invoke:citation/CS1|citation

|CitationClass=citation }}

  • {{#invoke:citation/CS1|citation

|CitationClass=citation }}.

  • {{#invoke:citation/CS1|citation

|CitationClass=citation }}.

  • {{#invoke:citation/CS1|citation

|CitationClass=citation }}.