A very fast method for guaranteed generation of one facet for 0-1 knapsack polyhedron
Author(s):
Article Type:
Research/Original Article (دارای رتبه معتبر)
Abstract:
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.
Keywords:
Language:
English
Published:
Scientia Iranica, Volume:31 Issue: 6, Mar-Apr 2024
Pages:
535 to 539
magiran.com/p2711426
دانلود و مطالعه متن این مقاله با یکی از روشهای زیر امکان پذیر است:
اشتراک شخصی
با عضویت و پرداخت آنلاین حق اشتراک یکساله به مبلغ 1,390,000ريال میتوانید 70 عنوان مطلب دانلود کنید!
اشتراک سازمانی
به کتابخانه دانشگاه یا محل کار خود پیشنهاد کنید تا اشتراک سازمانی این پایگاه را برای دسترسی نامحدود همه کاربران به متن مطالب تهیه نمایند!
توجه!
- حق عضویت دریافتی صرف حمایت از نشریات عضو و نگهداری، تکمیل و توسعه مگیران میشود.
- پرداخت حق اشتراک و دانلود مقالات اجازه بازنشر آن در سایر رسانههای چاپی و دیجیتال را به کاربر نمیدهد.
In order to view content subscription is required
Personal subscription
Subscribe magiran.com for 70 € euros via PayPal and download 70 articles during a year.
Organization subscription
Please contact us to subscribe your university or library for unlimited access!