Given a bipartite graph G=(V,E)G=(V,E), a weight for each node, and a weight for each edge, we consider an extension of the MAX-CUT problem that consists in searching for a partition of VV into two subsets V1V1 and V2V2 such that the sum of the weights of the edges from EE that have one endpoint in each set plus the sum of the weights of the nodes from VV that are in V1V1, is maximal. We prove that this problem can be modeled as a linear program (with real variables) and therefore efficiently solved by standard algorithms. Then, we show how this result can be applied to model a land allocation problem by a 0–1 linear program. This problem consists in determining the cells of a land area, divided into a matrix of identical square cells, which must be harvested and the cells which must be left in old growth so that the weighted sum of the expected populations of some species is maximized. Some computational results are presented to illustrate the efficiency of the method.
Integer linear programming is a classical tool in operations research that can be applied to a lot of optimization problems. Many studies have already shown that (integer) linear programming was a useful tool to optimize a management objective in an ecosystem (see, for example [1], [2], [3] and [4]). The technique is known and well-tried but must be carefully implemented since some formulations may require a prohibitive computation time (see, for example [5], [6] and [7]). Indeed, several models are often possible for the same problem, and the choice of a good one is important. If a particular formulation of a problem fails, another one may appear more efficient in practice, as we will see when considering a cut problem in a bipartite graph. We prove that a classical 0–1 linear model of this cut problem, of quadratic nature, can be solved by linear programming (in real variables). So, it is possible to solve large sized instances of this problem only using a linear programming tool, and finally a standard, commercially available, software. Then we use this formulation to efficiently model a land allocation problem by 0–1 linear programming. This problem, presented in [1] arises in land allocation modelling and consists in determining the cells of a land area, divided into a matrix of identical square cells, which must be harvested and the cells which must be left in old growth so that the weighted sum of the expected populations of three species is maximized. The species S1 prefers recently harvested areas contrary to the species S2, and the species S3 population is determined as a linear function of the amount of edge between harvested cells and non-harvested cells. Edges concern the interface between forest and non-forest elements and have environmental characteristics that are different from either of the adjacent elements. We suppose that the species S3 uses edges as its habitat. In Section 2, we recall some properties and mathematical programming formulations of the well-known MAX-CUT problem. In Section 3, we present the considered cut problem, a variant of MAX-CUT, and we prove that, in bipartite graphs, it can be solved (in polynomial time) by linear programming. In Section 4, we recall the forest management problem presented in [1], and a numerical example in Section 5. In Section 6, we give the linear 0–1 programming model proposed in [1]. In Section 7, we propose another linear 0–1 programming formulation based on the results of Section 3. In Section 8, we report comparisons of the two formulations, from a computational time viewpoint, which show the efficiency of the second formulation to compute the species S3 population. Section 9 is a conclusion.
Given a bipartite graph G=(V,E)G=(V,E), we considered the cut problem consisting of searching for a partition of VV into two subsets V1V1 and V2V2 such that the sum of the weights of the edges from EE that have one endpoint in each set, plus the sum of the weights of the nodes that are in V1V1, is maximal. We proved that this problem, of quadratic nature, is easy to solve since it can be reformulated by a linear program (in real variables). Then we show how this result allows to efficiently solve a land allocation problem, by using standard 0–1 linear programming software. This problem suggested in [1] consists in determining the cells of a land area which must be harvested and the cells which must be left in old growth so that the weighted sum of the expected populations of three species is maximized. As is often the case in integer linear programming, several models are possible for this problem, and the experimental results show that the proposed approach is a substantial improvement with regard to other approaches. With this new approach, and in our experimental conditions, the considered land allocation problem can be easily solved with up to 2500 cells.
