Matching problems with knapsack side constraints. A computational study
[For the entire collection see Zbl 0746.00072.] Some methods for solving matching problems with knapsack side constraints are discussed and by this some numerical aspects of practical applications of matchings are illustrated. Let \(G=(V,E)\) be a graph, \(c: E\to\mathbb{R}_{\geq 0}\) a cost function, \(\mathfrak M\) the set of all perfect matchings \(X\) of \(G\), \(x\) its incidence vector \(x\in\{0,1\}^{| E|}\), \(S\) a \(m\times| E|\)-matrix and \(t\in \mathbb{R}^ m\), \(m\in\mathbb{N}\). Then the matching problem with side constraints (MPS) can be formulated as a linear program as follows: \(v(\text{MPS})=\min\{c(X)\mid X\in{\mathfrak M},Sx\leq t\}\). The authors investigate the case where \((MPS)\) is complicated by knapsack- constraints. In general two linear programs can be stated which are immediate relaxations of (MPS); the first of them can be interpreted as an assignment problem with additional linear constraints and the second is the so-called LP-relaxation of (MPS). The construction of the optimal basis of this LP-relaxation is indicated. But in combinatorial optimization especially relaxations and Lagrangean decompositions are used on which the approximate solutions of the weighted matching problem in the present publication are based. And so it is shown that by dualizing the constraints Lagrangean relaxations and Lagrangean decompositions can be obtained. Firstly these relaxations for (MPS) with respect to their relative quality and their complexity are analysed in detail. Then the solution methodologies to optimize Lagrangean functions and their properties are shortly described (application of ``subgradient methods); by this the class of a single knapsack side constraint case is treated additionally, and further a method for bounding the duality gap for (MPS) is described basing on a fundamental property of the set of perfect matchings in \(G\). Generally the procedure of this optimization terminates with a lower bound and the best feasible matching, but the costs exceed the lower bound. Therefore two improvement techniques are discussed which will reduce this ``duality-gap by generating better feasible matchings. Finally by comparison of the results of computational experiments to investigate the efficiency of the relaxation and decomposition method for this class of problems they show that for (MPS) the Lagrangean relaxation seems to be the better method from a numerical point of view. The low CPU-time and the quality of the combined relaxation and \(k\)-best approach indicates that this is an effective method for solving matching problems with knapsack side constraints.
- Matching problems with generalized upper bound side constraints
- Solving matching problems with linear programming
- Matching: A well-solved class of integer linear programs
- Solving various weighted matching problems with constraints
- Lagrangean relaxation for a lower bound to a set partitioning problem with side constraints: Properties and algorithms
This page was built for publication: Matching problems with knapsack side constraints. A computational study
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4026988)
