Graph Problems with Knapsack Constraints

Graphs are widely used models to represent the structure of real-world objects such as road networks and pipeline grids, but also capture the logical relationships in very different entities from electronic circuits to social networks. Numerical values are frequently assigned to the vertices and edges of a graph to represent distances, costs, profits or capacities. Typical optimization problems on graphs considered in this project will be spanning trees connecting all vertices and Steiner tree problems; the assignment problem (bipartite complete matching); independent set (in a conflict graph); the orienteering problem (related to the travelling salesperson problem); and maximum cliques. While all these problems are motivated by their obvious application scenarios, it turns out that most real-world problems cannot be modeled by these well understood standard graph problems but require additional constraints. The most obvious and highly plausible extension of standard graph problems is the addition of a linear side constraint with an upper bound reflecting a resource or budget constraint. Such a constraint is the defining element of the knapsack problem, which is the most basic discrete optimization problem. The resulting combination gives rise to the general knapsack constrained graph problem, which is the focus of this project. Many standard graph problems are computationally difficult (in the sense of theoretical computer science). Others become so only by the addition of the knapsack constraint. As a first objective, we will identify properties of the underlying graph that define the boundary between efficiently (i.e. polynomially) solvable and intractable problems. For those cases where polynomial algorithms cannot exist we will develop approximation algorithms and study the theoretical limits of approximability. As a second objective we want to exploit the structural similarities between different problems within the scope of our framework and thus develop more generally applicable approximation approaches. In particular, we will investigate graph classes that allow tree-type decompositions such as graphs of bounded treewidth and chordal graphs and use these decompositions for the design of approximation algorithms. Moreover, we will consider planar graphs and construct approximation algorithms based on the separator theorem and the decomposition into outerplanar subgraphs. The structure of the knapsack constrained graph problem suggests the application of Lagrangian relaxation for the design of exact algorithms. After relaxing the knapsack constraint a subproblem arises that is closely related to the underlying standard graph problem. As third objective of the project we will investigate the complexity of this subproblem and compare, in a more general setting, different search strategies for the solution to the Lagrangian dual problem, depending on the difficulty of each subproblem. This should provide valuable guidelines in the future for other researchers who design specialized algorithms in generic branch and bound schemes.

This project combined two interesting core elements of combinatorial optimization: On one hand many real-world situations can be modelled by means of graphs. A graph consists of nodes representing objects or places of the real world and of edges which join pairs of nodes and represent a certain relation between the joined objects. On the other hand, many practical decision scenarios are subject to a limited budget or other constrained resources. These kind of restrictions are known as knapsack constraints, in analogy to the weight constraint encountered when packing items into a knapsack. In this research project we dealt with a number of fundamental graph problems with additional knapsack constraints. Our aim was the development of approximative solution procedures which compute solutions within a given maximum deviation from the unknown optimal solutions. We also proved complexity results ruling out the existence of such procedures for certain problem classes. Whether a given problem can be solved by approximation or not usually depends on structural properties of the underlying graph. For a large number of well-known graph classes we were able to provide classifications of this kind and where possible to construct these approximation algorithms. Thus, we contributed valuable insights into possibilities and limitations of solution algorithms for prominent graph problems.A major focus of our project was put on the quadratic knapsack problem where interdependencies between single decisions are a main component. The structure of these connections is usually represented by a graph. Depending on properties of these graphs we derived numerous new approximation algorithms and theoretical complexity results which led to a number of successful publications. A real-world application of the quadratic knapsack problem was encountered during the development of a decision support system for marketing managers, where it is crucial for the computation of an optimal marketing mix.A second key aspect was the knapsack problem with pairwise conflicts, where certain decisions are mutually excluded. These exclusions are represented by a conflict graph. This problem is equivalent to a well-known graph problem, namely the weighted independent set problem, with an additional budget constraint. We were able to develop approximation algorithms for several fairly general graph classes. We also constructed general generic algorithms applicable in particular for various graph decomposition methods but also for more general superclasses of planar graphs.