Abstract | ||
---|---|---|
Dual-feasible functions are valuable tools that can be used to compute both lower bounds for different combinatorial problems
and valid inequalities for integer programs. Several families of functions have been used in the literature. Some of them
were defined explicitly, and others not. One of the main objectives of this paper is to survey these functions, and to state
results concerning their quality. We clearly identify dominant subsets of functions, i.e. those which may lead to better bounds or stronger cuts. We also describe different frameworks that can be used to create
dual-feasible functions. With these frameworks, one can get a dominant function based on other ones. Two new families of dual-feasible
functions obtained by applying these methods are proposed in this paper.
We also performed a computational comparison on the relative strength of the functions presented in this paper for deriving
lower bounds for the bin-packing problem and valid cutting planes for the pattern minimization problem. Extensive experiments
on instances generated using methods described in the literature are reported. In many cases, the lower bounds are improved,
and the linear relaxations are strengthened. |
Year | DOI | Venue |
---|---|---|
2010 | 10.1007/s10479-008-0453-8 | Annals OR |
Keywords | Field | DocType |
Maximal Function,Valid Inequality,Integer Hull,Superadditive Function,Strong Valid Inequality | Integer,Superadditivity,Discrete mathematics,Mathematical optimization,Maximal function,Mathematics | Journal |
Volume | Issue | ISSN |
179 | 1 | 0254-5330 |
Citations | PageRank | References |
29 | 1.01 | 18 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
François Clautiaux | 1 | 248 | 17.16 |
Cláudio Alves | 2 | 184 | 16.29 |
José M. Valério De Carvalho | 3 | 168 | 14.06 |