Pemrograman Linear Bilangan Bulat selama 50 Tahun Terakhir: Kemajuan Praktis Terbaru — Halaman Perlindungan Anubis Ditampilkan

• Alih-alih isi makalah, yang ditampilkan adalah halaman verifikasi bot Anubis, sehingga isi makalah sebenarnya tidak dapat langsung dilihat dari URL tersebut
• Halaman perlindungan menjelaskan bahwa web scraping agresif oleh perusahaan AI dapat menyebabkan downtime server dan terhalangnya akses ke resource
• Anubis meminta proof-of-work yang mirip Hashcash, dirancang agar bebannya kecil bagi pengguna perorangan tetapi biaya akumulatifnya besar untuk scraping massal
• Cara ini adalah solusi sementara; dalam jangka panjang fokusnya adalah mengidentifikasi headless browser melalui petunjuk seperti rendering font
• Karena membutuhkan fitur JavaScript terbaru, jika plugin seperti JShelter aktif, plugin tersebut harus dinonaktifkan untuk domain ini agar akses dapat dilakukan

---

Halaman perlindungan Anubis ditampilkan

• Judul halamannya adalah “Making sure you're not a bot!”, dan layar menampilkan status sedang menghitung
  • Tingkat kesulitan: 4
  • Kecepatan: 0kH/s
• Administrator server mengatur Anubis untuk melindungi server dari scraping agresif oleh perusahaan AI, sehingga halaman ini ditampilkan
• Scraping massal dapat menyebabkan downtime situs web, dan akibatnya semua pengguna bisa kehilangan akses ke resource

Metode proof-of-work dan pembatasan akses

• Anubis menggunakan metode proof-of-work dari keluarga Hashcash
  • Beban tambahan bagi pengguna individual dapat diabaikan
  • Untuk scraper massal, biaya akumulatifnya meningkat sehingga biaya scraping menjadi lebih tinggi
• Metode saat ini lebih mendekati solusi sementara
  • Tujuannya adalah mendapatkan waktu untuk mengidentifikasi headless browser melalui petunjuk seperti cara rendering font
  • Arahnya adalah tidak menampilkan halaman proof-of-work ketika kemungkinan besar pengguna tersebut sah
• Anubis membutuhkan fitur JavaScript terbaru
  • Plugin seperti JShelter dapat menonaktifkan fitur yang diperlukan
  • Untuk domain ini, JShelter atau plugin serupa harus dimatikan

[GN⁺]

Komentar Hacker News

• Saya ingin memahami gambaran besarnya mengapa solver integer linear programming (ILP) komersial seperti Gurobi jauh lebih baik daripada yang gratis/open source
  Saya penasaran apakah karena ILP pada dasarnya masalah yang terlalu sulit, sehingga solver terbaik berbentuk kumpulan heuristik skala besar untuk submasalah tertentu, dan di ranah publik umumnya belum ada strategi yang bagus

  • Alasan utamanya adalah mereka telah mengimplementasikan peningkatan kecepatan spesifik masalah melalui kerja sama yang sangat erat dengan pelanggan. Dan ini sudah mereka lakukan selama 10–20 tahun
    Dalam mixed-integer linear programming (MILP), heuristik untuk menemukan titik awal yang bagus bagi branch-and-bound dan memangkas tree secara efektif itu penting, begitu juga cutting plane khusus yang memotong solusi fraksional untuk memperbaiki nilai objektif dan integrality
    Ketika peneliti operations research menangani masalah tertentu, mereka sering bisa mengalahkan solver serbaguna seperti Gurobi dengan cukup mudah dengan menulis cutting plane dan heuristik sendiri. Perusahaan solver mempekerjakan tim PhD dan peneliti untuk terus melakukan pekerjaan ini, serta melacak peningkatan dan regresi menggunakan kumpulan masalah pelanggan
  • Solver komersial besar punya sumber daya dan pelanggan kolaboratif untuk menghabiskan banyak waktu menyesuaikan semua bagian proses penyelesaian dengan masalah nyata. Heuristik adalah salah satu bagiannya, dan ini juga mencakup mengenali submasalah atau aproksimasi yang lebih sederhana lalu memantulkannya kembali ke masalah keseluruhan
    Solver open source tampaknya terhambat oleh beberapa hal yang saling tumpang tindih. Hambatan masuk untuk pengembangan optimisasi mutakhir sangat tinggi, sehingga sejak awal hanya sedikit peneliti/developer yang bisa berkontribusi secara berarti baik di sisi matematika maupun pemrograman; jika punya kemampuan itu, jalur yang menghasilkan uang cenderung menjauhkan mereka dari kontribusi open source; dan karena sifat proyek open source, “pelanggan” kecil kemungkinannya mengembalikan contoh, data performa, dan profiling yang dibutuhkan untuk memperbaiki solver
    Ada pengecualian, tetapi berada di luar pengembangan solver komersial tradisional tidak otomatis berarti open source. Misalnya SNOPT yang dikembangkan di Stanford pun masih berlisensi komersial. Pekerjaan solver di akademia sering terjadi dalam konteks aplikasi tertentu seperti Clarabel, sehingga kelompok masalahnya cenderung menyempit
    Di bidang lain, perusahaan teknologi besar kadang melewati bottleneck dengan mengakuisisi proyek komersial yang sudah ada, atau mendanai proyek open source untuk menahan kompetitor. Di dunia solver ada contoh sempit seperti Ceres, tetapi kemungkinan besar investasi untuk membangun seluruh stack solver serbaguna dari nol dianggap terlalu besar
  • Solver komersial punya kumpulan teknik yang sangat besar, serta mekanisme deteksi pola yang bagus untuk mengenali teknik mana yang akan membantu masalah saat ini
    Jika Anda mengetahui struktur masalahnya, Anda bisa memanfaatkannya untuk melampaui performa solver komersial. Namun untuk masalah sembarang, kemungkinannya hampir tidak ada
  • Saya rasa pernyataan bahwa “solver adalah ansambel besar heuristik untuk submasalah tertentu” hampir secara jelas berlaku untuk masalah NP-hard seperti ILP yang setara dengan SAT
  • Intinya adalah skala dan kecepatan. Misalnya, sebagian besar perusahaan quant trading menjalankan optimisasi raksasa sesering mungkin. Solver open source sering kali bahkan tidak bisa menyelesaikan masalah seperti ini sama sekali. Misalnya karena exception kehabisan memori

• Saya samar-samar ingat pernah membuat alat alokasi sumber daya dengan library mixed-integer linear programming “ILOG” milik IBM. Saya menyadari bahwa jika masalah yang sama yang kami selesaikan dalam 5 menit dibuat 20 tahun sebelumnya, mungkin sampai sekarang masih berjalan
  Kalau saya ingat benar, daya komputasi murni naik sekitar 1000 kali, dan algoritmanya juga membaik pada tingkat yang serupa, sehingga totalnya menjadi sekitar satu juta kali lebih baik
  Ini layak direnungkan saat memprediksi masa depan. Sebagai catatan, “sumber daya” itu adalah berlian

• Saya penasaran bagaimana hal seperti ini benar-benar digunakan. Saat mengimplementasikan optimisasi numerik, saya membayangkan sering gagal karena masalah yang umum dalam pendekatan berbasis data, misalnya kepercayaan dan data buruk, lalu pada akhirnya seseorang yang penting memutuskan apa yang harus dilakukan berdasarkan intuisi

  • Di tempat kerja, kami memakai solver di seluruh stack. Ada solver untuk menjadwalkan baterai rumah tangga dan mobil listrik secara optimal, solver untuk menjadwalkan portofolio ratusan ribu rumah seperti itu secara optimal, dan solver untuk memperdagangkan portofolio tersebut secara optimal
    Harga spot listrik Uni Eropa ditentukan setiap hari oleh satu eksekusi solver raksasa. Cari Euphemia; ada tulisan-tulisan tentang cara kerjanya
    Sebagian besar bidang yang punya tujuan jelas untuk dioptimalkan dan uang nyata yang dipertaruhkan penuh dengan solver
  • Di perusahaan FMCG, ini benar-benar dipakai untuk hal-hal seperti ini. Perencanaan perjalanan tenaga penjualan dan pengiriman, penjadwalan sumber daya mesin, tenaga kerja, dan material untuk produksi, serta optimisasi tingkat persediaan di gudang dan pusat distribusi
    Bagian persediaan belum sepenuhnya otomatis karena peramalan permintaan sulit
  • Baca saja studi kasus
    Studi kasus Gurobi: https://www.gurobi.com/case_studies/
    Beberapa studi kasus CPLEX: https://www.ibm.com/products/ilog-cplex-optimization-studio/...
    Studi kasus Hexaly, sebelumnya LocalSolver: https://www.hexaly.com/customers

• Saya dengar Gurobi cukup mahal. Saya penasaran apakah ada yang bisa membagikan informasi harga

  • Informasi harga bersifat rahasia jadi saya tidak bisa membagikannya, tetapi kalau Anda hanya ingin bermain-main dengan MIP, Anda tidak perlu membeli tiga solver yang sangat mahal: XPRESS, Gurobi, CPLEX. Biasanya gratis untuk mahasiswa
    Ada setidaknya dua solver MIP yang cukup bagus yang open source atau gratis untuk penggunaan nonkomersial
    https://highs.dev/
    https://www.scipopt.org/
  • Dari yang saya dengar, tentu saja tidak bisa saya verifikasi, tingkat harganya pada dasarnya hanya satu: “hubungi kami”, lalu mereka mencari tahu berapa banyak uang yang Anda hasilkan dan meminta sebagian darinya
  • Saya tidak mengerti mengapa orang menganggapnya rahasia yang begitu disembunyikan. Untuk lisensi dengan batasan core, kira-kira 10 ribu dolar per seat
  • Jauh lebih murah daripada mengambil keputusan yang salah secara lambat. Solver gratis seperti GLPK baik-baik saja untuk masalah kecil, tetapi banyak masalah bisnis hampir tidak bisa diselesaikan dalam waktu yang dibutuhkan kecuali Anda membayar solver premium. Gurobi adalah yang terbaik di antaranya
  • Terakhir kali saya mengeceknya sekitar 10 tahun lalu, lisensi penuh untuk beberapa pengguna di server sekitar 100 ribu dolar. Saya tidak ingat batas jumlah seat atau server persisnya
    Saya ingin menambahkan bahwa bagi banyak orang di industri, harganya sangat sepadan

• Saya ingat pernah mengimplementasikan semacam versi hyperplane pemotong Gomory di Maple untuk belajar pada 1990-an. Bukan untuk penggunaan nyata. Sepertinya bidang ini sudah banyak berkembang
  “Jika pada awal 1990-an dibutuhkan waktu eksekusi dua bulan untuk menyelesaikan LP, hari ini tidak sampai 1 detik. Baru-baru ini Bixby membandingkan kinerja independen-mesin dari dua solver MILP, CPLEX dan Gurobi, dari 1990 hingga 2020, dan melaporkan peningkatan kecepatan hampir 4×10^6 kali”

• Rasanya pendekatan berbasis machine learning/kecerdasan buatan untuk masalah seperti ini masih cukup kurang. Saya sering melihat makalah tentang reinforcement learning/graph neural network untuk menyelesaikan masalah kecil, tetapi pada akhirnya sering kali membeli lisensi Gurobi dan menjalankannya terlihat seperti pilihan terbaik
  Belakangan saya mengerjakan optimisasi penjadwalan yang mirip dengan job-shop scheduling; memang ada contoh yang memakai reinforcement learning, tetapi rasanya belum memadai. Untuk mendapatkan solusi yang masuk akal pada masalah besar, saya akhirnya bergantung pada algoritma evolusioner
  Kalau masalahnya bisa diformulasikan dengan baik, entah apakah pendekatan riset operasi selalu lebih efisien

  • Tergantung masalahnya. Security-constrained unit commitment adalah masalah menentukan pembangkit listrik mana yang harus dinyalakan dan kapan; kompleksitasnya sulit dipercaya, tetapi solver MILP seperti Gurobi dapat dengan cepat menemukan solusi optimal global dalam rentang gap MIP
    Bisa saja membuat algoritma genetika, tetapi tidak ada jaminan bahwa jawabannya tidak terjebak di minimum lokal. Juga perlu asumsi bahwa algoritma itu bisa dibuat berjalan cepat. Neural network juga kemungkinan akan kalah optimal
  • SAT adalah masalah kecerdasan buatan simbolik (GOFAI) yang standar, dan tentu saja solver SAT bisa ditulis dengan bahasa pemrograman keluarga machine learning. Dalam arti itu, menurut saya pendekatan machine learning/kecerdasan buatan cukup dapat diterapkan

• “Dari 1988 hingga 2004, hardware menjadi 1600 kali lebih cepat, dan solver LP menjadi 3300 kali lebih cepat, sehingga faktor peningkatan kecepatan kumulatifnya melampaui 5 × 10^6. Itu pun sudah 20 tahun lalu!”
  “Para penulis mengamati peningkatan kecepatan 1000 kali pada solver MILP komersial antara 2001 dan 2020. Dari jumlah itu, 50 kali berasal dari algoritma, dan 20 kali dari komputer yang lebih cepat”
  Saya penasaran apakah kita bisa mengumpulkan faktor peningkatan kecepatan seperti ini untuk tiap subbidang komputasi, lalu memecah kontribusinya antara peningkatan algoritma dan komputer yang lebih cepat
  Di bidang compiler ada “Hukum Proebsting”. Hukum ini menyatakan bahwa kemajuan compiler menggandakan performa komputasi setiap 18 tahun

• Akan bagus jika judulnya diberi [pdf] [2024]

  • Cukup tempelkan tautan makalahnya: https://inria.hal.science/hal-04776866v1/document
  • Tautannya bukan mengarah ke PDF, melainkan ke abstrak