Anti-Cycling Pivot Rules in Linear Optimization

Abstract

Pivot algorithms for solving linear optimization problems traverse the set of basic solutions or bases of the inequality system describing the model, searching for a feasible solution, or an optimal feasible solution if the model also contains a cost function to be minimized or maximized. Feasibility preserving pivot algorithms for solving linear optimization problems, often called simplex-type methods, preserve primal feasibility while trying to achieve dual feasibility or vice versa. Monotonic Build Up algorithm of Anstreicher and Terlaky is a simplex-type algorithm with interesting properties. We develop a pivot algorithm with similar properties for solving the feasibility problem of linear optimization in particular. To guarantee finiteness of our Monotonic Build Up simplex algorithm we incorporate s-monotone index selection rules into the general framework of the algorithm which are to be utilized whenever there is competition among the basic variables to leave the basis and among the nonbasic variables to enter the basis. We also use a specialized recursive procedure for handling strongly degenerate bases. We prove finiteness of the algorithm and analyze its computational complexity under some assumptions. As opposed to simplex-type methods criss-cross pivot algorithm preserves neither primal nor dual feasibility. We use criss-cross algorithm together with s-monotone index selection rules to solve feasibility problem of oriented matroids and and also prove its finiteness.

ÖZ: Dogrusal optimizasyon problemlerini çözmek için pivot algoritmaları, modeli ˘ açıklayan e¸sitsizlik sisteminin baz çözümleri veya bazları arasında gezinerek uygun bir çözüm ararlar. Model aynı zamanda minimize veya maksimize edilmesi gereken bir maliyet fonksiyonu içeriyorsa bu kez en uygun çözümü ararlar. Genellikle simpleks tipinde yöntemler olarak adlandırılan dogrusal optimizasyon problemlerini ˘ çözmek için fizibiliteyi koruyan pivot algoritmaları, dual fizibilite elde etmeye çalı¸sırken primal fizibiliteyi korur (primal simpleks) veya bunun tersi de geçerlidir (dual simpleks). Anstreicher ve Terlaky’nin Monotonic Build Up (monoton in¸sa) algoritması ilginç özelliklere sahip simpleks tipi bir algoritmadır. Özellikle dogrusal ˘ optimizasyonun fizibilite problemini çözmek için benzer özelliklere sahip bir pivot algoritması geli¸stirdik. Monoton in¸sa simpleks algoritmamızın sonlulugunu garanti ˘ etmek için, temel degi¸skenler arasında bazdan ayrılmak ve temel olmayan de ˘ gi¸skenler ˘ arasında baza girmek için rekabet oldugunda kullanılacak olan s-monoton dizin seçim ˘ kurallarını algoritmanın genel çerçevesine dahil ederek tanımladık. Ayrıca, güçlü bir ¸sekilde dejenere olmu¸s bazları i¸slemek için özel bir özyinelemeli prosedür geli¸stirdik. Algoritmanın sonlulugunu kanıtladık ve hesaplama karma¸sıklı ˘ gını bazı varsayımlar ˘ altında analiz ettik. Simpleks tipi yöntemlerin aksine, criss-cross pivot algoritması ne primal ne de dual fizibiliteyi korur. Yönlendirilmi¸s matroidlerin fizibilite problemini çözmek ve sonlulugunu kanıtlamak için s-monoton indeks seçim kuralları ile birlikte ˘ criss-cross algoritmasını kullanıyoruz.