Các nhà nghiên cứu phát hiện cách xử lý lập trình tuyến tính nguyên nhanh hơn
(quantamagazine.org)- Trong các bài toán tối ưu hóa cần quyết định theo đơn vị nguyên như lập kế hoạch sản xuất, bố trí phi hành đoàn và định tuyến phương tiện, Victor Reis và Thomas Rothvoss đã đề xuất một thuật toán mới giúp rút ngắn đáng kể thời gian chạy của ILP
- ILP khó hơn lập trình tuyến tính thông thường, và vì gần như không có cải thiện mang tính kỷ lục nào kể từ thập niên 1980, kết quả lần này được xem là bước tiến lớn đầu tiên sau nhiều thập kỷ
- Cách tiếp cận mới kết hợp các công cụ hình học để xử lý giao giữa mạng điểm và vật thể lồi, qua đó thu hẹp mạnh hơn phạm vi các nghiệm nguyên khả dĩ
- Trọng tâm là tận dụng kết quả năm 2016 liên quan đến các điểm mạng để hạ cận trên của covering radius, nhờ đó thời gian chạy giảm xuống mức ((\log n)^{O(n)})
- Dù chưa được áp dụng trực tiếp vào các hệ thống logistics thực tế, kết quả này gần chạm tới giới hạn tốc độ lý thuyết của ILP và cho thấy định hướng dài hạn để cải thiện các solver trong thực tiễn
Vì sao ràng buộc số nguyên khiến tối ưu hóa trở nên khó hơn
- Bài toán người bán hàng du lịch là một bài toán tính toán cổ điển nhằm tìm đường đi ngắn nhất qua nhiều thành phố, và nếu kiểm tra mọi lộ trình khả dĩ thì chỉ cần số thành phố tăng lên một chút cũng sẽ trở nên quá sức
- Lập trình tuyến tính là một mô hình toán học dùng phương trình và bất đẳng thức để xử lý có hệ thống các tổ hợp khả dĩ
- Trong các bài toán tối ưu hóa thực tế, đáp án dạng số thập phân thường không hữu ích
- Trong kế hoạch tối ưu hóa nhà máy, đáp án yêu cầu sản xuất 500,7 chiếc sofa rất khó dùng làm quyết định thực tế
- Lập trình tuyến tính nguyên (ILP) là một biến thể của lập trình tuyến tính có thêm ràng buộc số nguyên như vậy, và được dùng rộng rãi trong các bài toán quyết định rời rạc như lập kế hoạch sản xuất, lịch làm việc của phi hành đoàn hàng không và định tuyến phương tiện
- Santosh Vempala xem ILP là công cụ cốt lõi của nghiên cứu tác nghiệp cả về lý thuyết lẫn thực tiễn
Giới hạn tốc độ chỉ cải thiện chậm kể từ thập niên 1980
- Kể từ khi được hình thức hóa hơn 60 năm trước, ILP đã có nhiều thuật toán được đề xuất, nhưng xét theo số bước cần thiết thì vẫn còn tương đối chậm
- Mốc tham chiếu đơn giản nhất là trường hợp biến nhị phân, nơi mỗi biến chỉ có thể nhận giá trị 0 hoặc 1
- 1 biến có 2 tổ hợp khả dĩ
- 2 biến có 4 tổ hợp
- 3 biến có 8 tổ hợp
- Nói chung, thời gian chạy tăng theo hàm mũ theo số biến, tức số chiều
- Nếu biến có thể nhận các giá trị nguyên rộng hơn ngoài 0 và 1 thì thời gian chạy còn dài hơn nhiều
- Trong thời gian dài, các nhà nghiên cứu đã tìm cách đưa ILP tổng quát đến gần hơn với tốc độ của trường hợp nhị phân đơn giản này
- Sau kỷ lục của thập niên 1980, chỉ có các cải thiện dần dần nối tiếp nhau
Cách diễn giải hình học do Lenstra mở ra
- Năm 1983, Hendrik Lenstra chứng minh rằng bài toán ILP tổng quát là giải được và đồng thời đưa ra thuật toán đầu tiên cho nó
- Lenstra chuyển ILP thành một bài toán hình học
- Các bất đẳng thức của ILP được biểu diễn thành một hình dạng lồi, tức vật thể lồi (convex body)
- Bên trong hình đó tương ứng với mọi giá trị khả dĩ có thể thỏa mãn các bất đẳng thức
- Bài toán với 2 biến trở thành một đa giác trên mặt phẳng, còn bài toán với 3 biến trở thành một khối 3 chiều, và số chiều tăng lên theo số biến
- Về mặt toán học, mọi số nguyên đều có thể xem là các điểm của một mạng điểm (lattice)
- Trong 2 chiều, nó trông như một biển các điểm
- Trong 3 chiều, nó giống cấu trúc các nút giao của khung thép công trình
- Rốt cuộc, giải ILP trở thành bài toán tìm giao giữa vật thể lồi và mạng điểm, tức xác định vị trí mà nghiệm khả dĩ gặp các điểm nguyên
- Thuật toán của Lenstra có thể khám phá không gian này, nhưng để đạt hiệu quả đôi khi phải chia bài toán thành các mảnh có số chiều thấp hơn, và quá trình đó làm tăng thời gian chạy
Covering radius tạo ra nút thắt suốt 30 năm
- Năm 1988, Ravi Kannan và László Lovász cố gắng xử lý giao giữa vật thể lồi và mạng điểm hiệu quả hơn bằng khái niệm covering radius lấy từ nghiên cứu mã sửa lỗi
- Covering radius liên quan đến kích thước đủ để bảo đảm rằng dù đặt vật thể lồi ở đâu trên mạng điểm thì nó vẫn chứa ít nhất một điểm nguyên
- Độ lớn của giá trị này quyết định mức hiệu quả khi giải bài toán ILP
- Việc xác định chính kích thước covering radius lý tưởng vốn đã là một bài toán khó
- Kannan và Lovász đã thu hẹp khoảng giá trị khả dĩ bằng cận trên và cận dưới, đồng thời chỉ ra rằng cận trên tăng tuyến tính theo số chiều
- Chừng đó vẫn chưa đủ để rút ngắn mạnh thời gian chạy của ILP, và trong 30 năm sau đó mức cải thiện vẫn bị hạn chế
Thuật toán mới của Reis và Rothvoss
- Victor Reis và Thomas Rothvoss đã tạo ra bước đột phá bằng cách tận dụng một kết quả toán học riêng biệt tập trung vào mạng điểm
- Năm 2016, Oded Regev và Noah Stephens-Davidowitz chỉ ra có thể có bao nhiêu điểm mạng nằm trong một số hình dạng nhất định
- Reis và Rothvoss áp dụng kết quả đó cho các hình dạng khác để ước lượng tốt hơn số điểm mạng nằm trong covering radius của ILP
- Nhờ ước lượng này, cận trên đã được hạ xuống, và tổng thời gian chạy của thuật toán ILP giảm đáng kể
- Thời gian chạy mới là ((\log n)^{O(n)}), trong đó (n) là số biến và (O(n)) tỉ lệ tuyến tính theo (n)
- Biểu thức này được xem là “gần như” cùng mức với thời gian chạy của bài toán biến nhị phân
Khoảng cách giữa thành tựu lý thuyết và ứng dụng thực tế
- Noah Stephens-Davidowitz xem thuật toán mới là cải tiến lớn đầu tiên của solver ILP trong gần 40 năm
- Daniel Dadush đánh giá đây là thành quả xuất hiện từ giao điểm giữa toán học, khoa học máy tính và hình học
- Thuật toán mới vẫn chưa được dùng để giải các bài toán logistics thực tế
- Việc cập nhật các chương trình hiện tại để phù hợp với cách làm này sẽ đòi hỏi rất nhiều công sức
- Rothvoss cho rằng trọng tâm của kết quả lần này nằm ở hiểu biết lý thuyết về một bài toán có các ứng dụng nền tảng
- Dù vẫn còn khả năng nâng cao thêm hiệu quả tính toán của ILP, Vempala cho rằng để tiến gần hơn tới thời gian chạy lý tưởng sẽ cần những ý tưởng mới mang tính căn bản
1 bình luận
Ý kiến trên Hacker News
Việc hạ thấp cận trên thuật toán cho một bài toán NP-đầy đủ cốt lõi luôn rất thú vị, nhưng điều đó không nhất thiết có nghĩa là bài toán ấy sẽ được giải nhanh hơn trong triển khai thực tế
Các solver quy hoạch nguyên hỗn hợp (MIP) dùng kết hợp nhiều thuật toán và rất nhiều heuristic; việc tích lũy cả một thư viện heuristic và chiến lược là lý do then chốt khiến cải tiến của các solver MIP vượt trước định luật Moore
Theo https://www.math.uwaterloo.ca/~hwolkowi/henry/teaching/f16/6..., trong giai đoạn 1990–2014, cải tiến phần cứng mang lại mức tăng 6500 lần, còn cải tiến phần mềm đóng góp mức tăng hiệu năng 870000 lần
Bài báo này cũng có thể là một mảnh ghép giúp tiếp tục cải thiện hiệu năng solver MIP, nhưng không có gì bảo đảm điều đó
Tôi không hiểu lắm lời giải thích rằng lý do thuật toán mới chưa được dùng để giải các bài toán logistics là vì “cần quá nhiều công sức để cập nhật các chương trình ngày nay”
Hầu hết các mô hình theo miền, với bài toán lớn thì gọi các solver Gurobi, CPLEX, FICO, còn với bài toán nhỏ thì dùng solver mã nguồn mở như SCIP
Có thể trao đổi mô hình giữa các solver này bằng định dạng MPS chuẩn; công thức hóa bài toán không thay đổi, chỉ cần cách giải bên trong solver thay đổi là được, không phải sao?
Nếu ý là cần một triển khai mới, thì lợi ích mà thế giới nhận được khi triển khai xong có lẽ cũng sẽ rất lớn
Những công cụ này là sản phẩm kỹ thuật cực kỳ phức tạp, tích lũy các cải tiến từng bước trong nhiều thập kỷ, nên chỉ riêng việc tìm ra cách tích hợp phát hiện mới này vào các engine như vậy có lẽ cũng cần nỗ lực nghiên cứu đáng kể
Đúng là có các cách chuẩn để trao đổi công thức hóa bài toán bằng những định dạng như MPS, và hiện nay có vẻ các ngôn ngữ mô hình hóa đại số như AMPL còn được dùng nhiều hơn, nhưng những định dạng đó chỉ cung cấp một công thức toán học chuẩn
Phần giải thực tế thì rất đặc thù theo từng solver, với cấu trúc dữ liệu, thuật toán và kỹ thuật heuristic riêng
Chúng không thể hoán đổi cho nhau, cũng không được công khai một cách có chủ ý, và bạn không thể chen vài con số bên ngoài vào giữa quy trình nếu không có mã solver và hiểu biết về toàn bộ quá trình
Tôi chỉ muốn làm rõ hiểu lầm đó
Nếu có thể thì người ta sẽ tránh tự triển khai bằng những thứ như vậy
Dù vậy, điều đó không làm thay đổi việc đây là một kết quả xuất sắc
Từ góc nhìn độ phức tạp tính toán lý thuyết, các thuật toán tốt nhất cho “quy hoạch tuyến tính nguyên” [2] dựa trên lattice và có độ phức tạp big-O trong trường hợp xấu nhất là tốt nhất
Nhưng các triển khai hiện nay thường (1) cần số học hữu tỉ kích thước tùy ý như gmplib [3], rất tốn bộ nhớ và thực tế cũng chậm, và (2) cần bước giảm lattice kiểu LLL [4] nhưng không tận dụng được độ thưa của ma trận
Kết quả là các thuật toán này thường không vừa bộ nhớ, nên với các bài toán ma trận lớn hơn 1000x1000 thì còn không khởi động được, và ngay cả khi vừa bộ nhớ thì cũng quá chậm
Thay vào đó, các solver quy hoạch nguyên trong thực tế dựa trên branch and bound, một thuật toán quay lui tương tự thứ dùng trong giải SAT, và ở mỗi vòng lặp sẽ giải một bài toán “quy hoạch tuyến tính” thu được bằng cách biến tất cả biến trong bài toán gốc thành biến liên tục
Mỗi bài toán quy hoạch tuyến tính có thể được giải bằng các thuật toán thời gian đa thức như phương pháp điểm trong, nhưng trong thực tế người ta dùng phương pháp đơn hình, vốn có thời gian mũ trong trường hợp xấu nhất
Lý do là các bài toán quy hoạch tuyến tính cần giải rất giống nhau, và phương pháp đơn hình tận dụng điều đó rất tốt trong thực tế
Ngoài ra, các thuật toán liên quan tận dụng mạnh độ thưa của vector và ma trận
Vì thế có người giải được các bài toán quy hoạch nguyên có hàng triệu biến chỉ trong vài ngày, thậm chí vài giờ
Những người triển khai solver không theo đuổi độ phức tạp lý thuyết tuyệt đối tốt nhất; có thể nói lý thuyết và thực tiễn của tối ưu hóa rời rạc đã phần nào tách ra
Dẫu vậy, bài báo của Reis & Rothvoss [1] là một công trình toán học sâu sắc, và tự thân nó rất ấn tượng với những ai quan tâm đến toán rời rạc
Nó đã giải quyết một phỏng đoán 10 năm tuổi của Dadush, và được trình bày tại FOCS vào tháng 11 năm ngoái, một trong hai hội nghị hàng đầu về lý thuyết khoa học máy tính
Tính hữu dụng trực tiếp không phải là điểm chính, và trong các dịp không chính thức, các tác giả có lẽ cũng sẽ thừa nhận như vậy
Tất nhiên trong hồ sơ xin tài trợ nghiên cứu họ sẽ nói khác, nhưng đó là một phần của cuộc chơi
Điều đó không có nghĩa là nó vô dụng; chỉ riêng việc thúc đẩy tri thức toán học đã rất có giá trị, và vài thế hệ nhà nghiên cứu sau có thể dựa trên những ý tưởng này để tạo ra các thuật toán thực dụng, đẩy ranh giới tiên tiến của solver lên cao hơn
Rốt cuộc, tất cả các thuật toán này đều có thời gian mũ trong trường hợp xấu nhất
Trong lý thuyết, người ta sẽ cố giảm một chút đa thức nằm trong số mũ của độ phức tạp trường hợp xấu nhất, nhưng người làm thực tế thường muốn giải một bài toán tối ưu hóa lớn cụ thể, chứ không phải một họ bài toán có kích thước n ngày càng tăng
Điều quan trọng không phải tốc độ tăng của đường xu hướng thời gian giải, mà là có giải được một instance lớn trước mặt hay không; và instance đó thường có cấu trúc khiến nó không rơi vào trường hợp xấu nhất của cùng kích thước
Vì vậy các lựa chọn kỹ thuật cũng khác đi
[1] https://arxiv.org/abs/2303.14605
[2] min { c^T x : A x >= b, x in R^n, some components of x in Z }
[3] https://gmplib.org/
[4] https://www.math.leidenuniv.nl/~hwl/PUBLICATIONS/1982f/art.p...
Phần tóm tắt hữu ích hơn: https://arxiv.org/abs/2303.14605
Nội dung là họ đã có được thuật toán ngẫu nhiên thời gian (log(2n))^O(n) để giải quy hoạch nguyên với n biến
Tức là công trình này là một kết quả lý thuyết, dựa trên việc phân tích cấu trúc của các thể lồi trong R^n và cách phủ chúng bằng lưới nguyên, qua đó đề xuất một thuật toán thời gian hàm mũ tốt hơn kết quả tốt nhất trước đây
Phần lớn các tác vụ ILP thực tế dùng heuristic và phương pháp nhánh-cận, đồng thời tận dụng cấu trúc đặc biệt của từng mô hình bài toán cụ thể
Chưa rõ nghiên cứu này có giúp ích cho một trong hai hướng đó hay không, và nếu không có ai đó ở những nơi như Gurobi giải thích thì chỉ đọc bài báo có lẽ khó mà đánh giá được
Chỉ là góp ý nhỏ, nhưng tiêu đề nên ghi rõ là quy hoạch tuyến tính nguyên
Vì ở đây phần “nguyên” tạo ra khác biệt lớn hơn nhiều
Với quy hoạch tuyến tính, các thuật toán thời gian đa thức đã được biết đến từ nhiều thập kỷ trước, còn quy hoạch tuyến tính nguyên là NP-khó
Quy hoạch tuyến tính liên tục cũng khó
Không phải theo nghĩa NP-khó, mà là để xây dựng các LP solver hiện đại hiệu quả thì cần rất nhiều yếu tố về thuật toán và kỹ thuật
Chỉ riêng tính toán số đã đủ phức tạp rồi
Và nhiều solver quy hoạch tuyến tính nguyên dựa trên solver quy hoạch tuyến tính liên tục
Nếu là kỹ sư phần mềm quan tâm đến machine learning hoặc thuật toán thì quy hoạch tuyến tính rất đáng học
Có một lượng vấn đề đáng ngạc nhiên có thể được mô hình hóa thành tối ưu hóa tuyến tính
Ví dụ, hồi đại học tôi từng nói chuyện với một người bạn học kỹ thuật công nghiệp về số lần hoán đổi tối thiểu trung bình cần thiết để đặt các bi-a vào những vị trí bắt đầu hợp lệ trong tam giác xếp bi
Cả hai đều viết chương trình giải bằng lấy mẫu Monte Carlo; lời giải của tôi dùng BFS trên không gian trạng thái đồ thị, còn lời giải của bạn tôi dùng quy hoạch tuyến tính
Có lẽ cách của bạn tôi hiệu quả hơn
Ví dụ có cây khung nhỏ nhất, ghép cặp trong đồ thị hai phía hoặc đồ thị tổng quát, luồng mạng, giao matroid, luồng dưới mô-đun, v.v.
Nghiệm đỉnh của một số LP cũng có những tính chất thú vị có thể dùng khi thiết kế thuật toán xấp xỉ cho các bài toán NP-đầy đủ
Ví dụ, có thể chứng minh rằng trong nghiệm đỉnh của bài toán Steiner forest luôn tồn tại một biến có giá trị ít nhất 1/2, nên nếu lặp lại việc làm tròn biến và giải lại LP thì ta thu được thuật toán xấp xỉ 2
Hồi tôi học cao học, đó là thuật toán xấp xỉ 2 duy nhất cho bài toán này
Một điểm thú vị nữa là chỉ cần có separation oracle thời gian đa thức thì vẫn có thể giải LP ngay cả khi số ràng buộc là hàm mũ
Thật sự rất thú vị và đáng để giới thiệu
Hiện nay trong lĩnh vực vận trù học cũng đã có nhiều phần giao nhau đến đáng ngạc nhiên, nhưng tôi sốc vì có quá nhiều sinh viên tốt nghiệp kỹ thuật công nghiệp không lập trình cho ra hồn
Thật sự rất đáng tiếc
Tôi nhớ là vì thường chỉ có thể giao dịch các khoản tiền nguyên theo đơn vị cent, nên phần nguyên khá quan trọng
Bài viết ngắn nhưng hay
Tôi chưa xem sâu phần toán, nhưng preprint có vẻ là bản này: https://arxiv.org/pdf/2303.14605.pdf
Có vẻ họ không trực tiếp xét nhóm không gian theo cách khái quát hóa và đơn giản hóa “không gian” bài toán bằng cách giảm đối xứng hoặc lặp lại, nhưng sẽ rất thú vị nếu xem liệu cấu trúc như vậy có thể áp dụng được không
Là người dùng phần mềm áp dụng nhóm không gian và mô tả các ô Voronoi quanh một điểm hoặc một tập điểm phân bố trong đó, tôi quen với cách các hiệu ứng lan truyền một cách “rợn người” [1]
Tôi không phải nhà toán học, chỉ là kiến trúc sư, nên lĩnh vực này vượt quá năng lực của tôi, nhưng với tư cách người đang xem xét các đường đi xuyên qua cấu trúc tổ ong được sinh ra, kết quả này đáng để tìm hiểu thêm
[0] https://arxiv.org/pdf/2303.14605.pdf
[1] Nếu bạn biết nhà toán học nào có thể hợp tác về việc như thế này thì mong hãy liên hệ
Đây là công việc đang tiếp diễn, và như đã nói, về mặt toán học thì vượt quá năng lực của tôi, nhưng tôi đã gặp một số tính chất thú vị đáng để chuyên gia thực thụ xem xét sâu hơn
Liên quan đến bài toán người bán hàng, có một trích dẫn trong cuốn sách mới nhất của Sapolsky, Determined: A Science of Life without Free Will, khá thú vị
Không rõ nó liên quan đến lập trình viên phần mềm đến mức nào, nhưng rất cuốn hút
Khi một con kiến tìm thức ăn bằng cách kiểm tra tám địa điểm, lý tưởng là nó chỉ nên ghé mỗi nơi một lần và chọn lộ trình ngắn nhất trong 5.040 lộ trình khả dĩ, tức 7!
Đây là một dạng của bài toán người bán hàng nổi tiếng mà các nhà toán học đã vật lộn suốt nhiều thế kỷ mà vẫn chưa tìm được lời giải tổng quát
Một chiến lược là vét cạn: xem xét và so sánh mọi lộ trình khả dĩ rồi chọn lộ trình tốt nhất, nhưng chỉ cần có 10 điểm cần ghé thì số cách đã vượt quá 360.000, còn 15 điểm thì vượt quá 80 tỷ
Thế nhưng, nếu thả khoảng 10.000 con kiến trong một quần thể thông thường vào bài toán tám điểm thức ăn, thì dù không con kiến nào biết gì hơn ngoài tuyến đường nó đã đi và hai quy tắc, chúng vẫn tìm được một lời giải gần tối ưu trong số 5.040 khả năng nhanh hơn vét cạn rất nhiều
Cách này hoạt động tốt đến mức các nhà khoa học máy tính cũng dùng “kiến ảo” để giải những bài toán như vậy, và hiện nay nó được gọi là trí tuệ bầy đàn
Và phản ứng tiêu chuẩn là “các thuật toán máy tính rất đơn giản cũng làm được như vậy”
Trong bài toán người bán hàng, nếu xét khoảng cách Euclid, tức mỗi nút có tọa độ cố định và chi phí tuyến đường là khoảng cách Euclid giữa hai điểm, thì cũng có thể đưa ra thuật toán thời gian đa thức để tìm một lộ trình nằm trong hệ số ε của nghiệm tối ưu
Tuy nhiên, theo ε thì nó có độ phức tạp theo hàm mũ
Phần lời nói đầu cũng có một tuyên bố miễn trừ rất hay
“Cá nhân chúng tôi tin rằng tài liệu trong lĩnh vực này nên có ít thú có túi hơn và nhiều toán học hơn, và với tư cách cộng đồng, chúng ta nên vượt qua giai đoạn đầy ắp ẩn dụ này, tương tự như cách hóa học đã thoát khỏi thuật giả kim. Tuy nhiên, danh sách này không đưa ra bất kỳ khẳng định nào về chất lượng khoa học của các bài báo được liệt kê.”
[1]: https://fcampelo.github.io/EC-Bestiary/
Đây là thuật toán mô phỏng hành vi của đàn kiến như vậy
Như những người khác đã nói, nó tốt cho việc tìm nghiệm tối ưu cục bộ, giống như tìm kiếm tabu, mô phỏng tôi luyện và thuật toán di truyền
Với hầu hết mục tiêu kinh doanh, như ví dụ “sản xuất sofa” trong bài viết, như vậy là đủ
Nhưng nó khác với việc tìm “lời giải tổng quát”
Việc Sapolsky so sánh chuyện chúng ta không giỏi tìm “lời giải tổng quát” với khả năng kiến tìm nghiệm tối ưu cục bộ có vẻ hơi dễ gây hiểu lầm
Nó không có nghĩa là dạng tổng quát của bài toán không phải NP-khó, mà nghĩa là nếu bổ sung thêm thông tin, ta có thể xấp xỉ một nghiệm đủ tốt hoặc khiến việc tìm kiếm tối ưu trở nên xử lý được
Góc nhìn này đặc biệt nổi bật trong cuộc “cách mạng” AI đầu tiên, khi cách xem AI như các bài toán tìm kiếm được bổ trợ bằng tri thức con người từng rất thịnh hành
“Trí tuệ bầy đàn” mà cuốn sách muốn nói có phải là cái này không?
Nhiều bài toán tối ưu hóa rời rạc có thể được chuyển thành quy hoạch tuyến tính
Giống như SAT solver, đây là một công cụ cực kỳ mạnh nếu biết đến nó
Với tư cách lập trình viên, đó là một trong những khoảnh khắc kiểu “sao đến giờ mình mới bỏ lỡ thứ này nhỉ?”
Đây là một kết quả tuyệt vời, nhưng có lẽ sẽ không thực dụng
Tương tự như trong quy hoạch tuyến tính, phương pháp điểm trong có độ phức tạp lý thuyết tốt hơn phương pháp đơn hình, nhưng trong thực tế phương pháp đơn hình được tinh chỉnh tốt gần như luôn thắng
Có “lý do” nào được chấp nhận rộng rãi cho việc phương pháp điểm trong trên thực tế thường chậm hơn không?
Đi xuyên qua phần bên trong có vẻ như sẽ tiếp cận nghiệm tốt nhanh hơn so với bị ràng buộc ở biên, nhưng có lẽ trong không gian nhiều chiều sự khác biệt đó kém quan trọng hơn
Cách diễn đạt ở đây hơi gây rối
Có câu: “phiên bản tốt nhất mà họ nghĩ ra, một kiểu giới hạn tốc độ, xuất phát từ trường hợp tầm thường trong đó các biến của bài toán chỉ có thể nhận giá trị nhị phân, tức 0 hoặc 1, như việc người bán hàng có ghé thăm một thành phố hay không”; vậy là họ đang gọi một bài toán NP-đầy đủ là trường hợp tầm thường sao?
Theo tôi biết, mọi ILP đều có thể được quy về 01-ILP và ngược lại
Ngoài ra, đoạn “đáng tiếc là khi các biến nhận giá trị vượt ngoài 0 và 1, thời gian chạy của thuật toán dài hơn nhiều. Từ lâu các nhà nghiên cứu đã tự hỏi liệu có thể tiến gần hơn đến lý tưởng tầm thường này hay không” khiến tôi thắc mắc nghiên cứu này là một solver cải thiện cận dưới của 01-ILP, hay là một thuật toán kéo ranh giới giữa 01-ILP và ILP tổng quát lại gần nhau hơn