การโปรแกรมเชิงเส้นจำนวนเต็มในช่วง 50 ปีที่ผ่านมา: ความก้าวหน้าเชิงปฏิบัติล่าสุด — แสดงหน้าป้องกันของ Anubis

 (inria.hal.science)
1 คะแนน โดย GN⁺ 2025-06-16 | 1 ความคิดเห็น | แชร์ทาง WhatsApp
  • แทนที่จะแสดงเนื้อหาบทความวิชาการ กลับแสดง หน้าตรวจสอบบอตของ Anubis ทำให้ไม่สามารถดูเนื้อหาบทความจริงได้โดยตรงจาก URL ดังกล่าว
  • หน้าป้องกันแจ้งว่า การเว็บสแครปแบบก้าวร้าว ของบริษัท AI อาจนำไปสู่การหยุดทำงานของเซิร์ฟเวอร์และการปิดกั้นการเข้าถึงทรัพยากร
  • Anubis ต้องการ proof of work ที่คล้ายกับ Hashcash ซึ่งออกแบบมาให้ผู้ใช้รายบุคคลมีภาระน้อย แต่ทำให้การสแครปจำนวนมากมีต้นทุนสะสมสูงขึ้น
  • วิธีนี้เป็นทางออกชั่วคราว และในระยะยาวจะมุ่งเน้นการระบุ headless browser จากสัญญาณอย่างการเรนเดอร์ฟอนต์
  • เนื่องจากต้องใช้ฟีเจอร์ JavaScript รุ่นใหม่ หากเปิดปลั๊กอินอย่าง JShelter ไว้ ต้องปิดการใช้งานสำหรับโดเมนนั้นจึงจะเข้าถึงได้

แสดงหน้าป้องกันของ Anubis

  • ชื่อหน้าคือ “Making sure you're not a bot!” และบนหน้าจอแสดงสถานะ กำลังคำนวณ
    • ระดับความยากคือ 4
    • ความเร็วคือ 0kH/s
  • ผู้ดูแลเซิร์ฟเวอร์ตั้งค่า Anubis เพื่อปกป้องเซิร์ฟเวอร์จากการสแครปแบบก้าวร้าวของบริษัท AI จึงทำให้หน้านี้ปรากฏขึ้น
  • การสแครปจำนวนมากอาจทำให้เว็บไซต์หยุดทำงาน และส่งผลให้ผู้ใช้ทุกคนไม่สามารถเข้าถึงทรัพยากรได้

วิธี proof of work และข้อจำกัดในการเข้าถึง

  • Anubis ใช้วิธี proof of work ในตระกูลเดียวกับ Hashcash
    • ภาระเพิ่มเติมที่เกิดกับผู้ใช้แต่ละรายอยู่ในระดับที่แทบไม่ต้องกังวล
    • สำหรับสแครปเปอร์จำนวนมาก ต้นทุนสะสมจะเพิ่มขึ้น ทำให้ค่าใช้จ่ายในการสแครปสูงขึ้น
  • วิธีที่ใช้อยู่ในปัจจุบันค่อนข้างเป็น ทางออกชั่วคราว
    • เป้าหมายคือการซื้อเวลาเพื่อระบุ headless browser จากสัญญาณอย่างวิธีเรนเดอร์ฟอนต์
    • แนวทางคือไม่แสดงหน้า proof of work ในกรณีที่มีแนวโน้มสูงว่าเป็นผู้ใช้ที่ถูกต้องตามปกติ
  • Anubis ต้องใช้ฟีเจอร์ JavaScript รุ่นใหม่
    • ปลั๊กอินอย่าง JShelter อาจปิดการใช้งานฟีเจอร์ที่จำเป็น
    • สำหรับโดเมนนี้ ต้องปิด JShelter หรือปลั๊กอินลักษณะคล้ายกัน

บทความที่เกี่ยวข้อง

1 ความคิดเห็น

 
GN⁺ 2025-06-16
ความคิดเห็นบน Hacker News

  • อยากรู้ภาพรวมว่าทำไม ตัวแก้ปัญหาการโปรแกรมเชิงเส้นจำนวนเต็ม (ILP solver) เชิงพาณิชย์อย่าง Gurobi ถึงดีกว่าของฟรี/โอเพนซอร์สมาก
    สงสัยว่าเพราะ ILP เป็นปัญหาที่ยากโดยเนื้อแท้มาก จนตัวแก้ที่ดีที่สุดมีลักษณะเป็นการรวมฮิวริสติกสำหรับปัญหาย่อยเฉพาะจำนวนมากไว้ด้วยกัน และในพื้นที่สาธารณะยังไม่มีกลยุทธ์ทั่วไปที่ดีใช่หรือไม่

    • เหตุผลหลักคือพวกเขาทำงานร่วมกับลูกค้าอย่างใกล้ชิดมาก และนำ การปรับปรุงความเร็วเฉพาะปัญหา มาใช้มาโดยตลอด แล้วทำแบบนี้มา 10–20 ปีแล้ว
      ในการโปรแกรมเชิงเส้นจำนวนเต็มผสม (MILP) สิ่งสำคัญคือฮิวริสติกสำหรับหาจุดเริ่มต้นที่ดีของวิธี branch-and-bound และตัดกิ่งของต้นไม้ได้อย่างมีประสิทธิภาพ รวมถึง cutting plane แบบปรับแต่งเฉพาะที่ตัดคำตอบเศษส่วนออกเพื่อปรับปรุงค่าฟังก์ชันวัตถุประสงค์และความเป็นจำนวนเต็ม
      เมื่อนักวิจัยด้านวิจัยดำเนินงานหยิบปัญหาเฉพาะขึ้นมา ก็มักเขียน cutting plane และฮิวริสติกเองจนเอาชนะตัวแก้ทั่วไปอย่าง Gurobi ได้ค่อนข้างง่าย บริษัททำ solver จ้างทีมปริญญาเอกและนักวิจัยมาทำงานนี้อย่างต่อเนื่อง และติดตามการปรับปรุงกับ regression ด้วยชุดปัญหาของลูกค้า
    • ตัวแก้เชิงพาณิชย์รายใหญ่มี ทรัพยากรและลูกค้าที่ร่วมมือด้วย ให้ทุ่มเวลามากกับการปรับทุกอย่างในกระบวนการแก้ให้เข้ากับปัญหาจริง ฮิวริสติกก็เป็นส่วนหนึ่งของเรื่องนี้ และยังรวมถึงการตรวจจับปัญหาย่อยที่ง่ายกว่าหรือการประมาณ แล้วนำกลับมาสะท้อนในปัญหาทั้งหมดด้วย
      ตัวแก้โอเพนซอร์สดูเหมือนจะถูกหลายปัจจัยฉุดรั้งพร้อมกัน กำแพงในการเข้าสู่การพัฒนา optimization สมัยใหม่สูงมาก จึงมีนักวิจัย/นักพัฒนาที่มีส่วนร่วมได้อย่างมีความหมายทั้งด้านคณิตศาสตร์และการเขียนโปรแกรมตั้งแต่แรกไม่มาก และถ้ามีความสามารถแบบนั้น เส้นทางที่ทำเงินได้ก็มักพาออกห่างจากการมีส่วนร่วมกับโอเพนซอร์ส อีกทั้งด้วยธรรมชาติของโปรเจกต์โอเพนซอร์ส “ลูกค้า” มีโอกาสต่ำที่จะส่งตัวอย่าง ข้อมูลประสิทธิภาพ และการทำ profiling ที่จำเป็นต่อการปรับปรุง solver กลับมาให้
      มีข้อยกเว้นอยู่บ้าง แต่การอยู่นอกการพัฒนาตัวแก้เชิงพาณิชย์แบบดั้งเดิมไม่ได้แปลว่าเป็นโอเพนซอร์สทันที ตัวอย่างเช่น SNOPT ที่พัฒนาที่ Stanford ก็ยังใช้ไลเซนส์เชิงพาณิชย์อยู่ งาน solver ในแวดวงวิชาการมักเกิดขึ้นในบริบทการใช้งานเฉพาะอย่าง Clarabel ทำให้กลุ่มปัญหามีแนวโน้มแคบลง
      ในสาขาอื่น บริษัทเทคโนโลยีขนาดใหญ่บางครั้งก็ข้ามคอขวดได้ด้วยการซื้อโปรเจกต์เชิงพาณิชย์เดิม หรือให้ทุนโปรเจกต์โอเพนซอร์สเพื่อคานคู่แข่ง ในวงการ solver ก็มีตัวอย่างที่แคบอย่าง Ceres แต่เป็นไปได้สูงว่าการลงทุนพัฒนา solver stack อเนกประสงค์ทั้งหมดตั้งแต่ต้นถูกมองว่าใหญ่เกินไป
    • ตัวแก้เชิงพาณิชย์มี ชุดเทคนิค ขนาดใหญ่ และมีกลไกตรวจจับแพตเทิร์นที่ดีว่าปัญหาปัจจุบันจะได้ประโยชน์จากเทคนิคใด
      ถ้าคุณรู้โครงสร้างของปัญหา ก็อาจใช้สิ่งนั้นเพื่อทำผลงานให้เหนือกว่าตัวแก้เชิงพาณิชย์ได้ แต่ถ้าเป็นปัญหาใด ๆ ทั่วไป โอกาสแทบไม่มี
    • คิดว่าคำว่า “solver เป็น ensemble ขนาดใหญ่ของฮิวริสติกสำหรับปัญหาย่อยเฉพาะ” น่าจะใช้ได้แทบจะโดยชัดเจนกับปัญหา NP-hard ที่เทียบเท่า SAT อย่าง ILP ไม่ใช่หรือ
    • แก่นของเรื่องคือ ขนาดและความเร็ว ตัวอย่างเช่น บริษัท quant trading ส่วนใหญ่รัน optimization ขนาดใหญ่ให้บ่อยที่สุดเท่าที่ทำได้ ตัวแก้โอเพนซอร์สมักแก้ปัญหาแบบนี้ไม่ได้เลยด้วยซ้ำ เช่นเกิดข้อยกเว้นหน่วยความจำไม่พอ

  • จำได้เลือน ๆ ว่าเคยสร้างเครื่องมือจัดสรรทรัพยากรด้วยไลบรารี การโปรแกรมเชิงเส้นจำนวนเต็มผสม “ILOG” ของ IBM แล้วตระหนักว่า ถ้าปัญหาเดียวกับที่เราแก้ได้ใน 5 นาทีถูกสร้างขึ้นเมื่อ 20 ปีก่อน มันคงยังรันอยู่จนถึงตอนนี้
    เท่าที่จำได้ พลังประมวลผลดิบเพิ่มขึ้นประมาณ 1,000 เท่า และอัลกอริทึมก็ดีขึ้นในระดับใกล้เคียงกัน รวมแล้วดีขึ้นราวหนึ่งล้านเท่า
    เป็นเรื่องที่น่าคิดเวลาเราคาดการณ์อนาคต อ้อ “ทรัพยากร” ที่ว่านั้นคือเพชร

  • สงสัยว่าของแบบนี้ถูกใช้งานจริงอย่างไร พอคิดถึงการทำ numerical optimization ก็นึกถึงภาพว่ามันมักล้มเหลวเพราะปัญหาที่พบได้บ่อยในแนวทางขับเคลื่อนด้วยข้อมูล เช่น ความเชื่อมั่นและข้อมูลแย่ แล้วสุดท้ายก็มีคนสำคัญสักคนตัดสินใจด้วยสัญชาตญาณว่าจะทำอย่างไร

    • ที่ทำงานใช้ solver ทั่วทั้งสแต็ก มี solver สำหรับจัดตารางการใช้งานแบตเตอรี่ในบ้านและรถ EV ให้เหมาะที่สุด, solver สำหรับจัดตารางบ้านแบบนั้นหลายแสนหลังเป็นพอร์ตโฟลิโอให้เหมาะที่สุด, และ solver สำหรับเทรดพอร์ตโฟลิโอนั้นให้เหมาะที่สุด
      ราคาสปอตไฟฟ้าใน EU ถูกกำหนดทุกวันด้วยการรัน solver ขนาดยักษ์หนึ่งครั้ง ลองค้นหา Euphemia จะมีบทความอธิบายวิธีทำงาน
      สาขาส่วนใหญ่ที่มีเป้าหมายให้ optimize ชัดเจนและมีเงินจริงเกี่ยวข้อง ล้วนเต็มไปด้วย solver
    • ในบริษัท FMCG เขาใช้สิ่งนี้จริง ๆ เช่น การวางแผนการเดินทางของพนักงานขายและการจัดส่ง, การจัดตารางทรัพยากรเครื่องจักร·แรงงาน·วัสดุสำหรับการผลิต, และการปรับระดับสินค้าคงคลังในศูนย์กระจายสินค้าคลังสินค้าให้เหมาะสม
      ฝั่งสินค้าคงคลังยังไม่ได้อัตโนมัติเต็มที่ เพราะการคาดการณ์อุปสงค์ทำได้ยาก
    • อ่านกรณีศึกษาได้
      กรณีศึกษาของ Gurobi: https://www.gurobi.com/case_studies/
      กรณีศึกษาบางส่วนของ CPLEX: https://www.ibm.com/products/ilog-cplex-optimization-studio/...
      กรณีศึกษาของ Hexaly ซึ่งเดิมคือ LocalSolver: https://www.hexaly.com/customers

  • ได้ยินว่า Gurobi ค่อนข้างแพง สงสัยว่ามีใครแชร์ ข้อมูลราคา ได้บ้างไหม

    • ข้อมูลราคาเป็นความลับเลยแชร์ไม่ได้ แต่ถ้าแค่อยากลองเล่นกับ MIP ก็ไม่จำเป็นต้องซื้อ solver สามตัวใหญ่ที่แพงมากอย่าง XPRESS, Gurobi, CPLEX โดยปกตินักศึกษาจะใช้ได้ฟรี
      มี MIP solver ที่ดีอย่างน้อยสองตัวที่เป็นโอเพนซอร์สหรือฟรีสำหรับการใช้งานไม่ใช่เชิงพาณิชย์
      https://highs.dev/
      https://www.scipopt.org/
    • เท่าที่ได้ยินมา แน่นอนว่ายืนยันไม่ได้ ระดับราคามีอยู่จริง ๆ แค่ระดับเดียวคือ “ติดต่อเรา” แล้วตอนนั้นเขาจะประเมินว่าคุณทำเงินได้เท่าไร จากนั้นขอส่วนแบ่งบางส่วน
    • ไม่เข้าใจว่าทำไมถึงคิดว่าเป็นความลับที่ถูกปิดบังลึกขนาดนั้น ตามไลเซนส์จำกัดจำนวนคอร์ ราคาคร่าว ๆ อยู่ที่ 10,000 ดอลลาร์ ต่อ seat
    • ถูกกว่าการตัดสินใจผิด ๆ แบบช้ามาก solver ฟรีอย่าง GLPK ใช้ได้ดีกับปัญหาเล็ก ๆ แต่ปัญหาทางธุรกิจจำนวนมากแทบจะแก้ไม่ทันเวลาที่ต้องการ ถ้าไม่จ่ายเงินให้ solver พรีเมียม Gurobi คือเจ้าที่ดีที่สุดในกลุ่มนั้น
    • ครั้งสุดท้ายที่ตรวจสอบเมื่อประมาณ 10 ปีก่อน ไลเซนส์เต็มสำหรับผู้ใช้หลายคนบนเซิร์ฟเวอร์อยู่ที่ราว 100,000 ดอลลาร์ จำข้อจำกัดจำนวน seat หรือจำนวนเซิร์ฟเวอร์ที่แน่ชัดไม่ได้
      อยากเสริมว่าสำหรับหลายคนในอุตสาหกรรม มันคุ้มค่าราคานั้นอย่างมาก

  • ผมจำได้ว่าเคย implement ไฮเปอร์เพลนตัดของ Gomory เวอร์ชันหนึ่งใน Maple เพื่อใช้เรียนรู้ช่วงทศวรรษ 1990 ไม่ได้ทำไว้ใช้งานจริง ดูเหมือนว่าสาขานี้จะพัฒนาไปมาก
    “ถ้าในช่วงต้นทศวรรษ 1990 การแก้ LP ต้องใช้เวลารันสองเดือน ทุกวันนี้ใช้เวลาไม่ถึง 1 วินาที เมื่อไม่นานมานี้ Bixby เปรียบเทียบประสิทธิภาพแบบไม่ขึ้นกับเครื่องของ MILP solver สองตัวคือ CPLEX และ Gurobi ระหว่างปี 1990 ถึง 2020 และรายงานว่าความเร็วเพิ่มขึ้นเกือบ 4×10^6 เท่า”

  • รู้สึกว่าแนวทางที่อิง แมชชีนเลิร์นนิง/ปัญญาประดิษฐ์ สำหรับปัญหาแบบนี้ยังค่อนข้างขาดแคลน เคยเห็นงานวิจัยด้าน reinforcement learning/graph neural network ที่พยายามแก้ปัญหาเล็ก ๆ อยู่มาก แต่สุดท้ายหลายครั้งก็ดูเหมือนว่าทางที่ดีที่สุดคือซื้อไลเซนส์ Gurobi มาใช้
    ช่วงหลังผมทำ scheduling optimization ที่ใกล้เคียงกับ job-shop scheduling อยู่ แม้จะมีตัวอย่างที่ใช้ reinforcement learning แต่ก็ดูยังไม่เพียงพอ เลยต้องพึ่ง evolutionary algorithm เพื่อให้ได้คำตอบที่พอสมเหตุสมผลสำหรับปัญหาขนาดใหญ่
    ถ้าสามารถ formulate ปัญหาได้ดี ก็ไม่แน่ใจว่าแนวทางแบบ operations research จะมีประสิทธิภาพกว่าเสมอหรือไม่

    • แล้วแต่ปัญหา security-constrained unit commitment คือปัญหาการตัดสินใจว่าจะเปิดโรงไฟฟ้าใดเมื่อไร ซึ่งซับซ้อนอย่างไม่น่าเชื่อ แต่ MILP solver อย่าง Gurobi สามารถหาคำตอบที่เหมาะที่สุดระดับ global ได้เร็วภายในช่วง MIP gap
      คุณอาจสร้าง genetic algorithm ได้ แต่ไม่มีหลักประกันว่าจะให้คำตอบที่ไม่ติดอยู่ใน local minimum และยังต้องสมมติด้วยว่าสามารถทำให้รันได้เร็ว neural network ก็น่าจะยังแย่กว่าค่าที่เหมาะที่สุดเช่นกัน
    • SAT เป็นปัญหา ปัญญาประดิษฐ์เชิงสัญลักษณ์ (GOFAI) แบบมาตรฐาน และแน่นอนว่าสามารถเขียน SAT solver ด้วยภาษาโปรแกรมสายแมชชีนเลิร์นนิงได้ ในแง่นั้น ผมคิดว่าแนวทางแมชชีนเลิร์นนิง/ปัญญาประดิษฐ์ค่อนข้างนำมาใช้ได้

  • “ตั้งแต่ปี 1988 ถึง 2004 ฮาร์ดแวร์เร็วขึ้น 1600 เท่า และ LP solver เร็วขึ้น 3300 เท่า ทำให้ปัจจัยการเพิ่มความเร็วสะสมเกิน 5 × 10^6 และนั่นก็เมื่อ 20 ปีก่อนแล้ว!”
    “ผู้เขียนสังเกตเห็นว่า MILP solver เชิงพาณิชย์มีความเร็วเพิ่มขึ้น 1000 เท่าระหว่างปี 2001 ถึง 2020 โดย 50 เท่ามาจากอัลกอริทึม และ 20 เท่ามาจากคอมพิวเตอร์ที่เร็วขึ้น”
    สงสัยว่าจะรวบรวม ปัจจัยการเพิ่มความเร็ว แบบนี้ตามสาขาย่อยของคอมพิวติง แล้วแยกส่วนได้ไหมว่าส่วนไหนมาจากการปรับปรุงอัลกอริทึมและส่วนไหนมาจากคอมพิวเตอร์ที่เร็วขึ้น
    ในวงการคอมไพเลอร์มี “กฎของ Proebsting” อยู่ เป็นกฎที่ว่าความก้าวหน้าของคอมไพเลอร์ทำให้ประสิทธิภาพการประมวลผลเพิ่มขึ้นเป็นสองเท่าทุก 18 ปี

  • น่าจะเติม [pdf] [2024] ไว้ในชื่อเรื่อง