|
|
|
|
a very fast method for guaranteed generation of one facet for 0-1 knapsack polyhedron
|
|
|
|
|
|
|
|
نویسنده
|
kianfar f. ,kianfar k. ,rafiee m.
|
|
منبع
|
scientia iranica - 2024 - دوره : 31 - شماره : 6-E - صفحه:535 -539
|
|
چکیده
|
The 0-1 knapsack polyhedron as the most basic relaxation of a 0-1 integer program has attracted attention of many researchers over the years.we present a very fast method that is guaranteed to generate one facet for the 0-1 knapsack polyhedron. unlike lifting of cover inequlities, our method does not require an initial minimal cover or a predetermined lifting sequencing, and its worst-case complexity is linear in number of variables. therefore, it is suitable for incorporation into mixed interger programming(mip) solvers, in order to generate, with negligible computational burden, one strong cut based on any 0-1 knapsack relaxation of a general mip.
|
|
کلیدواژه
|
0-1 interger programming ,facet ,knapsack problem
|
|
آدرس
|
sharif university of technology, department of industrial engineering, iran, texas and university, college station, department of industrial and systems engineering, usa, sharif university of technology, department of industrial engineering, iran
|
|
پست الکترونیکی
|
rafiee@sharif.edu
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Authors
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|