A very fast method for guaranteed generation of one facet for 0-1 knapsack polyhedron

Q: How can I download an article?

To download an article from SID, first log in to the site, search for the article title, and click on the 'Download Article' option.

Q: How can I download an ISI article?

To download an ISI article on SID, enter the keyword or article title in the search bar, view the relevant results, click on the desired article, and select the 'Download Article' option.

Q: How can I access the SID database?

To access the SID database, visit SID.ir, create an account, and log in to access scientific resources.

Q: Is downloading articles from SID free?

Some articles on SID are available for free, while others require payment. Details are specified on the article's page.

Kianfar F.; Kianfar K.; Rafiee M.

مرکز اطلاعات علمی Scientific Information Database (SID) - Trusted Source for Research and Academic Resources

Journal Paper

Paper Information

Journal: Scientia Iranica Year:2024 | Volume:31 | Issue:6 Page(s): 535-539

Download Full-Text

View:

Download:

Cites:

Information Journal Paper

Title

A very fast method for guaranteed generation of one facet for 0-1 knapsack polyhedron

Author(s)

Kianfar F. | Kianfar K. | Rafiee M. | Issue Writer Certificate

Keywords

0-1 interger programming

facet

knapsack problem

Abstract

The 0{1 knapsack polyhedron as the most basic relaxation of a 0{1 integer program has attracted the 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 inequities, our method does not require an initial minimal cover or a predetermined lifting sequencing, and its worst-case complexity is linear in some variables. Therefore, with minimal computational burden, it can be used to generate a potentially strong valid inequality based on any 0{1 relaxation of a general (Mixed) Integer Program (M)IP. Such valid inequalities can be added to the (M)IP problem prior to solving, or given their low computational cost, can be generated during solving the (M)IP, checked to see if they separate the incumbent fractional solution, and added to the problem if they do

Multimedia

No record.

Cites

No record.

References

No record.

Cite

Related Journal Papers

No record.

Related Seminar Papers

No record.

Related Plans