Implementation of Presolving and Interior-Point Algorithm for Linear & Mixed Integer Programming: SOFTWARE

Ndayikengurutse Adrien () and Huang Siming ()
Additional contact information
Ndayikengurutse Adrien: School of Management Science and Engineering, Institute of Science and Development, Chinese Academy of Sciences, Beijing, 100190, China
Huang Siming: Chinese Academy of Sciences, Beijing, 100190, China

Journal of Systems Science and Information, 2020, vol. 8, issue 3, 195-223

Abstract: Linear and mixed integer programming are very popular and important methods to make efficient scientific management decision. With large size of real application data, the use of linear-mixed integer programming is facing problems with more complexity; therefore, preprocessing techniques become very important. Preprocessing aims to check and delete redundant information from the problem formulation. It is a collection of techniques that reduce the size of the problem and try to strengthen the formulation. Fast and effective preprocessing techniques are very important and essential for solving linear or mixed integer programming instances. In this paper, we demonstrate a set of techniques to presolve linear and mixed integer programming problems. Experiment results showed that when preprocessing is well done, then it becomes easier for the solver; we implemented interior-point algorithm for computational experiment. However, preprocessing is not enough to reduce the size and total nonzero elements from the constraints matrix. Moreover, we also demonstrate the impact of minimum degree reordering on the speed and storage requirements of a matrix operation. All techniques mentioned above are presented in a multifunctional software to facilitate users.

Keywords: linear programming; mixed-integer programming; preprocessing; minimum degree reordering; interior-point algorithm; software (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://doi.org/10.21078/JSSI-2020-195-29 (text/html)

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:bpj:jossai:v:8:y:2020:i:3:p:195-223:n:1

DOI: 10.21078/JSSI-2020-195-29

Access Statistics for this article

Journal of Systems Science and Information is currently edited by Shouyang Wang

More articles in Journal of Systems Science and Information from De Gruyter
Bibliographic data for series maintained by Peter Golla ().