A heuristic method to find a quick feasible solution based on the ratio programming

M. N. Yarahmadi, S. A. MirHassani () and F. Hooshmand
Additional contact information
M. N. Yarahmadi: Amirkabir University of Technology (Tehran Polytechnic)
S. A. MirHassani: Amirkabir University of Technology (Tehran Polytechnic)
F. Hooshmand: Amirkabir University of Technology (Tehran Polytechnic)

Operational Research, 2023, vol. 23, issue 3, No 3, 19 pages

Abstract: Abstract The feasibility pump is a successful rounding-based heuristic to find a feasible solution to mixed-integer programming (MIP) problems. This paper presents a novel method to find a high-quality feasible solution to 0–1 MIPs in a reasonable time. This method is based on a ratio programming model, which we refer to as a feasible-finder model (FFM). It proves that the optimal solution to FFM is feasible for the original MIP problem. An efficient ratio programming method is adopted to solve FFM by solving a sequence of linear programming problems. Then, to improve the quality of the feasible solution, a quality-controlling cut is generated and added in each iteration. Computational results over instances of CORAL and MIPLIB confirm the effectiveness of our method.

Keywords: Integer feasible solution; Feasibility pump; Ratio programming; Bisection strategy (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s12351-023-00777-7 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

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:spr:operea:v:23:y:2023:i:3:d:10.1007_s12351-023-00777-7

Ordering information: This journal article can be ordered from
https://www.springer ... search/journal/12351

DOI: 10.1007/s12351-023-00777-7

Access Statistics for this article

Operational Research is currently edited by Nikolaos F. Matsatsinis, John Psarras and Constantin Zopounidis

More articles in Operational Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().