On the extremality of maximal dual feasible functions
Dual feasible functions have been used with notable success to compute fast lower bounds and valid inequalities for various combinatorial optimization problems. In this paper, we analyze the theoretical properties of some of the best (and more complex) functions proposed in the literature. Additiona...
| Main Author: | |
|---|---|
| Other Authors: | , |
| Format: | article |
| Language: | eng |
| Published: |
2012
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/1822/15191 |
| Country: | Portugal |
| Oai: | oai:repositorium.sdum.uminho.pt:1822/15191 |
| Summary: | Dual feasible functions have been used with notable success to compute fast lower bounds and valid inequalities for various combinatorial optimization problems. In this paper, we analyze the theoretical properties of some of the best (and more complex) functions proposed in the literature. Additionally, we report on new results for composed functions. In particular, we describe under which conditions all these functions are extremal. These results are important since they allow to improve the computation of both lower bounds and valid inequalities. |
|---|