Struktur contoh patologis untuk algoritma simpleks

Sejauh yang saya mengerti, semua tahu aturan pivot deterministik untuk algoritma simpleks memiliki input spesifik yang algoritma membutuhkan waktu eksponensial (atau setidaknya tidak polinomial) untuk menemukan yang optimal. Mari kita sebut contoh ini 'patologis' karena biasanya (yaitu pada sebagian besar input) algoritma simpleks berakhir dengan cepat. Saya ingat dari kursus pemrograman matematis saya bahwa contoh standar dari contoh patologis untuk aturan spesifik sangat terstruktur. Pertanyaan umum saya adalah apakah ini merupakan artefak dari contoh spesifik, atau fitur contoh patologis secara umum?

Hasil seperti analisis yang diperhalus dan algoritma waktu polinomial yang diperluas bergantung pada gangguan input --- menunjukkan bahwa contoh-contoh patologis sangat istimewa. Oleh karena itu intuisi bahwa contoh-contoh patologis sangat terstruktur tampaknya tidak terlalu jauh.

Apakah ada yang punya wawasan khusus tentang ini? Atau beberapa referensi untuk pekerjaan yang ada? Saya telah secara khusus tidak jelas tentang apa yang saya maksud dengan 'terstruktur' untuk mencoba menjadi seluas mungkin, tetapi saran tentang bagaimana lebih baik dijabarkan 'terstruktur' juga akan berguna. Setiap saran atau referensi sangat dihargai!

Amenta dan Ziegler membuktikan bahwa semua konstruksi yang dikenal saat ini dari instance eksponensial untuk simpleks mengikuti struktur tertentu yang mereka sebut "produk cacat":

Produk Cacat dan Bayangan Maksimal Polytopes oleh Amenta dan Ziegler

Namun, saya tidak berpikir ada alasan untuk percaya bahwa semua contoh buruk untuk simpleks memiliki struktur ini. Ini mungkin hanya artefak dari proses penelitian:

1. Klee dan Minty menemukan contoh waktu-eksponensial pertama.
2. Peneliti lain melihat dan teknik Klee dan Minty dan memperluasnya ke aturan pivot lainnya. Mereka secara alami mengambil jalan perlawanan paling sedikit dan mengikuti kubus Klee-Minty sedekat mungkin.
3. Begitu seseorang menemukan satu contoh buruk untuk aturan pivot, tidak ada insentif bagi orang untuk mencari lebih banyak. Hasilnya, semua contoh buruk yang kita tahu memiliki struktur yang serupa.