Lifting two-integer knapsack inequalities |
| |
Authors: | A. Agra M.F. Constantino |
| |
Affiliation: | (1) Department of Mathematics, University of Aveiro, Campus Universitário de Santiago, 3810-193 Aveiro, Portugal;(2) DEIO and CIO, University of Lisbon, Edifício C6, Campo Grande, 1749-016 Lisboa, Portugal |
| |
Abstract: | In this paper we discuss the derivation of strong valid inequalities for (mixed) integer knapsack sets based on lifting of valid inequalities for basic knapsack sets with two integer variables (and one continuous variable). The basic polyhedra can be described in polynomial time. We use superadditive valid lifting functions in order to obtain sequence independent lifting. Most of these superadditive functions and valid inequalities are not obtained in polynomial time. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|