Zadeh's rule

In mathematical optimization, Zadeh's rule (also known as the least-entered rule) is an algorithmic refinement of the simplex method for linear optimization.

The rule was proposed around 1980 by Norman Zadeh (son of Lotfi A. Zadeh), and has entered the folklore of convex optimization since then.^[1]

Zadeh offered a reward of $1,000 to anyone who can show that the rule admits polynomially many iterations or to prove that there is a family of linear programs on which the pivoting rule requires subexponentially many iterations to find the optimum.^[2]

Algorithm

Zadeh's rule belongs to the family of history-based improvement rules which, during a run of the simplex algorithm, retain supplementary data in addition to the current basis of the linear program.

In particular, the rule chooses among all improving variables one which has entered the basis least often, intuitively ensuring that variables that might yield a substantive improvement in the long run but only a small improvement in a single step will be applied after a linear number of steps.

The supplementary data structure in Zadeh's algorithm can therefore be modeled as an occurrence record, mapping all variables to natural numbers, monitoring how often a particular variable has entered the basis. In every iteration, the algorithm then selects an improving variable that is minimal with respect to the retained occurrence record.

Note that the rule does not explicitly specify which particular improving variable should enter the basis in case of a tie.

Superpolynomial lower bound

Zadeh's rule has been shown to have at least super-polynomial time complexity in the worse-case by constructing a family of Markov decision processes on which the policy iteration algorithm requires a super-polynomial number of steps.^[3]^[4]

Running the simplex algorithm with Zadeh's rule on the induced linear program then yields a super-polynomial lower bound.

The result was presented at the "Efficiency of the Simplex Method: Quo vadis Hirsch conjecture?" IPAM workshop in 2011 by Oliver Friedmann.^[5] Zadeh, although not working in academia anymore at that time, attended the Workshop and honored his original proposal.^[6]

Exponential lower bound

Friedmann's original result has since been strengthened by the construction of an exponential instance for Zadeh's rule.^[7]

Notes

^ Zadeh, Norman (1980). "What is the worst case behaviour of the simplex algorithm?". Technical Report, Department of Operations Research, Stanford.
^ Ziegler, Günter (2004). "Typical and extremal linear programs". The Sharpest Cut (MPS-Siam Series on Optimization: 217–230. doi:10.1137/1.9780898718805.ch14. ISBN 978-0-89871-552-1.
^ Friedmann, Oliver (2011). "A subexponential lower bound for Zadeh's pivoting rule for solving linear programs and games". Proceedings of the 15th International Conference on Integer Programming and Combinatorial Optimization (IPCO). pp. 192–206.
^ Disser, Y.; Hopp, A.V. (2019). "On Friedmann's Subexponential Lower Bound for Zadeh's Pivot Rule". Proceedings of the 20th Conference on Integer Programming and Combinatorial Optimization (IPCO). pp. 168–180.
^ "Efficiency of the Simplex Method: Quo vadis Hirsch conjecture?". 13 May 2014.
^ "Günter Ziegler: 1000$ from Beverly Hills for a Math Problem. (IPAM remote blogging.)". 20 January 2011.
^ Disser, Yann; Friedmann, Oliver; Hopp, Alexander V. (2022). "An exponential lower bound for Zadeh's pivot rule". Mathematical Programming.

Read other articles:

Hijos de Rivera

Hijos de Rivera, S.A.Pabrik Estrella Galicia di A Grela, A Coruña.JenisSociedad AnónimaIndustriMinumanDidirikanA Coruña, Galisia (01 Januari 1906 (1906-01-01))PendiriJosé María Rivera CorralKantorpusatA Coruña, SpanyolTokohkunciIgnacio Rivera, Direktur JenderalProdukBir dan minuman ringanJasaDistribusiSitus webwww.corporacionhijosderivera.com Hijos de Rivera, S.A. adalah sebuah pabrik bir asal Spanyol yang didirikan pada tahun 1906 di A Coruña, Galisia. Produk utama perusahaan ini...

Les Fourberies de Scapin

Pour les articles homonymes, voir Les Fourberies de Scapin (homonymie). Les Fourberies de Scapin Frontispice de la première édition de 1671. Auteur Molière Genre Comédie Nb. d'actes Trois actes en prose Lieu de parution Paris Date de création en français 24 mai 1671 Lieu de création en français Paris Compagnie théâtrale Théâtre du Palais Royal Metteur en scène Molière modifier Frontispice de l'édition de 1682. Les Fourberies de Scapin est une comédie de Molière en troi...

Strada statale 113 Settentrionale Sicula

Strada statale 113Settentrionale SiculaLocalizzazioneStato Italia Regioni Sicilia Province Messina Palermo Trapani DatiClassificazioneStrada statale InizioMessina FineTrapani Lunghezza377,00[1] km Provvedimento di istituzioneLegge 17 maggio 1928, n. 1094 GestoreANAS Manuale La strada statale 113 Settentrionale Sicula (SS 113) è una strada statale italiana che si snoda lungo la costa settentrionale della Sicilia, andando da Messina a Trapani, passando per Palermo. ...

Jacques Maritain

French Catholic philosopher (1882–1973) This article includes a list of general references, but it lacks sufficient corresponding inline citations. Please help to improve this article by introducing more precise citations. (November 2010) (Learn how and when to remove this template message) Jacques MaritainOblSBMaritain in the 1930sBorn(1882-11-18)18 November 1882Paris, FranceDied28 April 1973(1973-04-28) (aged 90)Toulouse, FranceAlma materUniversity of ParisNotable work Art and S...

Sussac

Peta infrastruktur dan tata guna lahan di Komune Sussac. = Kawasan perkotaan = Lahan subur = Padang rumput = Lahan pertanaman campuran = Hutan = Vegetasi perdu = Lahan basah = Anak sungaiSussac merupakan sebuah komune di departemen Haute-Vienne di Prancis. Lihat pula Komune di departemen Haute-Vienne Referensi INSEE lbsKomune di departemen Haute-Vienne Aixe-sur-Vienne Ambazac Arnac-la-Poste Augne Aureil Azat-le-Ris Balledent La Bazeuge Beaumont-...

Package tracking

Process during package sorting and delivery Tracking packages with stationary bar code reader in a warehouse sorting operation Package tracking or package logging is the process of localizing shipping containers, mail and parcel post at different points of time during sorting, warehousing, and package delivery to verify their provenance and to predict and aid delivery. Package tracking developed historically because it provided customers information about the route of a package and the antici...

Cape Makkovik Air Station

General Surveillance Gap Filler Radar station Cape Makkovik Air Station Part of Pinetree LineLabrador, Canada Coordinates55°13′30″N 059°08′45″W / 55.22500°N 59.14583°W / 55.22500; -59.14583 (Cape Makkovik AS N-28A)TypeRadar StationCodeN-28ASite informationControlled byAerospace Defense CommandSite historyBuilt1957Built byUnited States Air ForceIn use1957-1961 Cape Makkovikclass=notpageimage| Location of Cape Makkovik Air Station, Labr...

Чайки

У этого термина существуют и другие значения, см. Чайки (значения). Чайки Доминиканская чайкаЗападная чайкаКалифорнийская чайкаМорская чайка Научная классификация Домен:ЭукариотыЦарство:ЖивотныеПодцарство:ЭуметазоиБез ранга:Двусторонне-симметричныеБез ранга:Вторич...

Richard Linklater

American film director, producer and screenwriter (born 1960) Richard LinklaterLinklater in 2015BornRichard Stuart Linklater (1960-07-30) July 30, 1960 (age 63)Houston, Texas, U.S.Occupation(s)Director, producer, writerYears active1985–present[1]Notable workBoyhood, Dazed and Confused, Before trilogy, School of Rock, Waking Life, SlackerSpouseChristina HarrisonChildren3, including LoreleiWebsitedetourfilm.com Richard Stuart Linklater (/ˈlɪŋkleɪtər/; born July 30, 1960...

拉米兹·阿利雅

拉米兹·阿利雅Ramiz Alia第1任阿尔巴尼亚總統任期1991年4月30日—1992年4月9日继任萨利·贝里沙阿尔巴尼亚人民议会主席团主席任期1982年11月22日—1991年4月30日前任哈奇·列希继任转任总统阿尔巴尼亚劳动党第一书记任期1985年4月13日—1991年5月4日前任恩维尔·霍查继任无（政党解散）个人资料出生(1925-10-18)1925年10月18日阿尔巴尼亚斯库台逝世2011年10月17日(2011歲—10—17)（85�...

Valayapathi (film)

1952 Indian filmValayapathiTheatrical release posterDirected byT. R. SundaramMasthanWritten byBharathidasanStory byModern Theatres Story Dept.Produced byT. R. SundaramStarringG. MuthukrishnanSowcar JanakiT. A. JayalakshmiK. K. PerumalCinematographyM. MasthanEdited byL. BaluMusic byS. DakshinamurthiProductioncompanyModern TheatresRelease date 17 October 1952 (1952-10-17) CountryIndiaLanguageTamil Valayapathi is a 1952 Indian Tamil-language film, directed and produced by T. R. S...

2020年夏季奧林匹克運動會波蘭代表團

2020年夏季奥林匹克运动会波兰代表團波兰国旗IOC編碼POLNOC波蘭奧林匹克委員會網站olimpijski.pl（英文）（波兰文）2020年夏季奥林匹克运动会（東京）2021年7月23日至8月8日（受2019冠状病毒病疫情影响推迟，但仍保留原定名称）運動員206參賽項目24个大项旗手开幕式：帕维尔·科热尼奥夫斯基（游泳）和马娅·沃什乔夫斯卡（自行车）[1]闭幕式：卡罗利娜·纳亚（皮划艇）&#...

Stephen J. Yates

Stephen J. Yates Presiden Radio Free AsiaMasa jabatanDesember 2020 – 22 Januari 2021Ditunjuk olehMichael PackPendahuluBay FangPenggantiBay FangKetua Partai Republik IdahoMasa jabatanAgustus 2014 – Juli 2017PendahuluBarry PetersonPenggantiJonathan Parker Informasi pribadiLahir1968/1969 (umur 54–55)[1]Partai politikRepublikPendidikanUniversitas Maryland, College Park (Sarjana)Universitas Johns Hopkins (Magistrat)Sunting kotak info • L • B Steph...

أوسيلوت

هذه المقالة تحتاج للمزيد من الوصلات للمقالات الأخرى للمساعدة في ترابط مقالات الموسوعة. فضلًا ساعد في تحسين هذه المقالة بإضافة وصلات إلى المقالات المتعلقة بها الموجودة في النص الحالي. (نوفمبر 2021) هذه المقالة يتيمة إذ تصل إليها مقالات أخرى قليلة جدًا. فضلًا، ساعد بإضافة وصلة...

St Leonard's Forest

Forest in the United Kingdom This article includes a list of general references, but it lacks sufficient corresponding inline citations. Please help to improve this article by introducing more precise citations. (May 2009) (Learn how and when to remove this message) St Leonard's ForestBluebells in St Leonard's Forest in 2009GeographyLocationWest Sussex, EnglandElevation40 metres (130 ft) to 145 metres (476 ft)Area12 sq mi (31 km2)AdministrationGoverning bodyM...

Perahu dan Danau

Artikel ini tidak memiliki referensi atau sumber tepercaya sehingga isinya tidak bisa dipastikan. Tolong bantu perbaiki artikel ini dengan menambahkan referensi yang layak. Tulisan tanpa sumber dapat dipertanyakan dan dihapus sewaktu-waktu.Cari sumber: Perahu dan Danau – berita · surat kabar · buku · cendekiawan · JSTOR Artikel ini perlu dikembangkan agar dapat memenuhi kriteria sebagai entri Wikipedia.Bantulah untuk mengembangkan artikel ini. Jika tid...

موسيقى الولايات المتحدة

موسيقى الولايات المتحدةمعلومات عامةالبلد الولايات المتحدة أصول الأسلوب music of North America (en) تعديل - تعديل مصدري - تعديل ويكي بيانات تعكس موسيقى الولايات المتحدة التعدد العرقي لسكانها من خلال مجموعة متنوعة من الأنماط الموسيقية، فهي عبارة عن مزيج من الموسيقا التي تأثرت فيما ...

2004 Iranian seizure of Royal Navy personnel

2004 Iranian seizure of Royal Navy personnelTwo British patrol boats just after their capture as shown by Iranian TVDate21 June 2004LocationPersian GulfResult British naval personnel arrested3 patrol boats seizedBelligerents British Royal Navy Navy of the Army of the Guardians of the Islamic Revolution Iranian Border Guard Command Map of the Persian Gulf. On 21 June 2004, in the Shatt al-Arab (Arvand Rud in Persian) waterway,[1] six Royal Marines and two Royal Navy sailors were captu...

طمينة (أكلة)

طمينةمعلومات عامةاسم آخر زريرة، تقنتةالمنشأ الجزائربلد المطبخ مطبخ جزائريالترتيب حلوى المكونات الرئيسية سميد، عسل، زبدة دقيق القمحتعديل - تعديل مصدري - تعديل ويكي بيانات طمينة (أو زرير) هي حلوى جزائرية تقليدية، تصنع بالسميد (الدقيق ) او (القمح المطحون مع المكسرات والحمص و ...

爆釣バーハンター

爆釣バーハンタージャンル釣りゲーム対応機種ニンテンドー3DS 開発元バンダイナムコエンターテインメントインティ・クリエイツ発売元バンダイメディアダウンロードプレイ人数 1人発売日 2018年3月17日デバイス爆釣バーロッド漫画作者鈴木サバ缶出版社小学館掲載誌コロコロコミックレーベルてんとう虫コミックス発表号 2018年4月号 - 2019年6月号発�...