Solving a cut problem in bipartite graphs by linear programming: Application to a forest management problem

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.