### Abstract

Original language | English |
---|---|

Pages (from-to) | 481-511 |

Journal | Mathematical Programming |

Volume | 133 |

Issue number | 1 |

Publication status | Published - 2012 |

### Fingerprint

### Cite this

*Mathematical Programming*,

*133*(1), 481-511.

}

*Mathematical Programming*, vol. 133, no. 1, pp. 481-511.

**Clique-based facets for the precedence constrained knapsack problem.** / Bley, A.; Boland, N.; Fricke, C.; Froyland, G.; Sotirov, R.

Research output: Contribution to journal › Article › Scientific › peer-review

TY - JOUR

T1 - Clique-based facets for the precedence constrained knapsack problem

AU - Bley, A.

AU - Boland, N.

AU - Fricke, C.

AU - Froyland, G.

AU - Sotirov, R.

PY - 2012

Y1 - 2012

N2 - We consider a knapsack problem with precedence constraints imposed on pairs of items, known as the precedence constrained knapsack problem (PCKP). This problem has applications in manufacturing and mining, and also appears as a subproblem in decomposition techniques for network design and related problems. We present a new approach for determining facets of the PCKP polyhedron based on clique inequalities. A comparison with existing techniques, that lift knapsack cover inequalities for the PCKP, is also presented. It is shown that the clique-based approach generates facets that cannot be found through the existing cover-based approaches, and that the addition of clique-based inequalities for the PCKP can be computationally beneficial.

AB - We consider a knapsack problem with precedence constraints imposed on pairs of items, known as the precedence constrained knapsack problem (PCKP). This problem has applications in manufacturing and mining, and also appears as a subproblem in decomposition techniques for network design and related problems. We present a new approach for determining facets of the PCKP polyhedron based on clique inequalities. A comparison with existing techniques, that lift knapsack cover inequalities for the PCKP, is also presented. It is shown that the clique-based approach generates facets that cannot be found through the existing cover-based approaches, and that the addition of clique-based inequalities for the PCKP can be computationally beneficial.

M3 - Article

VL - 133

SP - 481

EP - 511

JO - Mathematical Programming

JF - Mathematical Programming

SN - 0025-5610

IS - 1

ER -