A heuristic with tie breaking for certain 0–1 integer programming models

G. Edward Fox and Gary D. Scudder

Naval Research Logistics Quarterly, 1985, vol. 32, issue 4, 613-623

Abstract: A heuristic for 0–1 integer programming is proposed that features a specific rule for breaking ties that occur when attempting to determine a variable to set to 1 during a given iteration. It is tested on a large number of small‐ to moderate‐sized randomly generated generalized set‐packing models. Solutions are compared to those obtained using an existing well‐regarded heuristic and to solutions to the linear programming relaxations. Results indicate that the proposed heuristic outperforms the existing heuristic except for models in which the number of constraints is large relative to the number of variables. In this case, it performs on par with the existing heuristic. Results also indicate that use of a specific rule for tie breaking can be very effective, especially for low‐density models in which the number of variables is large relative to the number of constraints.

Date: 1985
References: Add references at CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
https://doi.org/10.1002/nav.3800320408

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wly:navlog:v:32:y:1985:i:4:p:613-623

Access Statistics for this article

More articles in Naval Research Logistics Quarterly from John Wiley & Sons
Bibliographic data for series maintained by Wiley Content Delivery ().