Title: New redundant constraints for Klee-Minty problem

Authors: Bib Paruhum Silalahi

Addresses: Department of Mathematics, IPB University, Jl. Meranti, Kampus IPB, Dramaga, Bogor, 16680, Indonesia

Abstract: Interior-point method (IPM) is a class of methods which has polynomial time for iteration complexity in solving linear optimisation problems. The iteration complexity upper bound of IPM can be stated as O(√N ln N), where N is the number of inequalities. In this paper, we prove that the new redundant constraints of the form: −ρy_k-1 − y_k ≤ d_k may cause the central path visits small neighbourhood of the vertices of the Klee-Minty cube. Our case has smaller number of redundant inequalities compared to best previous results, but of the same order: O(n2²ⁿ ). In our case the central path goes to at least 2ⁿ⁻¹ + 1 of the vertices (half of the vertices + 1).

Keywords: interior-point method? IPM? Klee-Minty problem? lower bound? new redundant constraints.

DOI: 10.1504/IJMMNO.2021.118392

International Journal of Mathematical Modelling and Numerical Optimisation, 2021 Vol.11 No.4, pp.385 - 397

Received: 05 May 2020
Accepted: 18 Nov 2020
Published online: 25 Oct 2021 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article