A Decentralized Heuristic for Multiple-Choice Combinatorial Optimization Problems

摘要

1 Introduction In 0-1 multiple-choice combinatorial optimization problems, multiple sets or classes of elements are given, from which each exactly one element has to be chosen to form a solution. The goal is to find a solution that minimizes (or maximizes) a given objective function. Such problems are typically NP-hard in the weak sense, so that they can be solved in polynomial time using dynamic programming [4]. By exploiting the specific structure of a given problem, even linear time can be achieved. For example, the well-known multiple-choice knapsack problem can easily be solved using the core concept [6]. But such methods cannot be applied to all problems of this class for two reasons: First, a core may be difficult to find, as it is the case in some (multiple-choice) subsetsum problems [7]. Second, and more importantly, the problem may have to be solved in a decentralized way, so that global knowledge is not available. This is especially the case in distributed systems with autonomous actors. For example, such a system may not support gathering global knowledge due to its openness, or the cost for doing this may be very high. Also, the collection of global knowledge at certain stages of an algorithm (i.e. at startup) leads to synchronization points, which are undesirable in many cases. Finally, such actions may violate privacy considerations. Typical application fields for these kinds of problems are distributed resource allocation, wireless sensor networks, media streaming in bandwith-contrained environments, logistics and decentralized energy management.