Research output: Working paper
Research output: Working paper
}
TY - UNPB
T1 - Computing good allocations for combinatorial optimization games
AU - Caprara, Alberto
AU - Letchford, Adam N.
N1 - This was eventually published as: A. Caprara & A.N. Letchford (2010) New techniques for cost sharing in combinatorial optimization games. Math. Program., 124(1-2), 93-118.
PY - 2005
Y1 - 2005
N2 - Much of the literature on cooperative games associated with combinatorial optimization problems is concerned with finding necessary or sufficient conditions under which the core is non-empty. In this paper however we are concerned with a rather different question, which may be of more use in practice: how to find partial cost allocations with high value. This question is addressed from both theoretical and algorithmic viewpoints. We begin by defining a very general class of games, called Integer Minimization (IM) games, and show that it includes many well-known combinatorial optimization games as special cases. We then show that finding the optimal allocation is strongly NP-hard for many IM games of interest. This gives the motivation for seeking general techniques for computing 'good' (though not necessarily optimal) allocations. We give three such techniques, based on column generation, row generation, or both. To illustrate the power of these techniques, we apply them to various travelling salesman and vehicle routing games.
AB - Much of the literature on cooperative games associated with combinatorial optimization problems is concerned with finding necessary or sufficient conditions under which the core is non-empty. In this paper however we are concerned with a rather different question, which may be of more use in practice: how to find partial cost allocations with high value. This question is addressed from both theoretical and algorithmic viewpoints. We begin by defining a very general class of games, called Integer Minimization (IM) games, and show that it includes many well-known combinatorial optimization games as special cases. We then show that finding the optimal allocation is strongly NP-hard for many IM games of interest. This gives the motivation for seeking general techniques for computing 'good' (though not necessarily optimal) allocations. We give three such techniques, based on column generation, row generation, or both. To illustrate the power of these techniques, we apply them to various travelling salesman and vehicle routing games.
KW - combinatorial optimization games
KW - travelling salesman problem
KW - vehicle routing
M3 - Working paper
T3 - Management Science Working Paper Series
BT - Computing good allocations for combinatorial optimization games
PB - The Department of Management Science
CY - Lancaster University
ER -