Các nhà nghiên cứu tiếp cận giới hạn tốc độ mới cho vấn đề quan trọng | Tạp chí Quanta

Bài toán nhân viên bán hàng du lịch là một trong những bài toán tính toán lâu đời nhất được biết đến. Nó yêu cầu lộ trình lý tưởng qua một danh sách các thành phố nhất định, giảm thiểu quãng đường. Mặc dù có vẻ đơn giản nhưng vấn đề lại nổi tiếng là khó khăn. Mặc dù bạn có thể sử dụng vũ lực để kiểm tra tất cả các tuyến đường có thể cho đến khi tìm ra con đường ngắn nhất, nhưng chiến lược như vậy sẽ không thể thực hiện được chỉ sau một số thành phố. Thay vào đó, bạn có thể áp dụng một mô hình toán học chặt chẽ được gọi là lập trình tuyến tính, mô hình này gần đúng bài toán dưới dạng một tập hợp các phương trình và kiểm tra một cách có phương pháp các kết hợp có thể có để tìm ra giải pháp tốt nhất.

Nhưng đôi khi, bạn cần tối ưu hóa các bài toán liên quan đến số nguyên. Kế hoạch tối ưu hóa nhà máy sản xuất 500.7 chiếc ghế dài có ích lợi gì? Để làm được điều này, các nhà nghiên cứu thường chuyển sang một biến thể của quy hoạch tuyến tính được gọi là lập trình tuyến tính số nguyên (IL P). Nó phổ biến trong các ứng dụng liên quan đến các quyết định riêng biệt, bao gồm lập kế hoạch sản xuất, lập kế hoạch cho phi hành đoàn hàng không và định tuyến phương tiện. “Về cơ bản, ILP là trụ cột của nghiên cứu hoạt động cả về lý thuyết và thực hành,” cho biết Santosh Vempala, một nhà khoa học máy tính tại Viện Công nghệ Georgia.

Kể từ lần đầu tiên họ xây dựng ILP hơn 60 năm trước, các nhà nghiên cứu đã phát hiện ra nhiều thuật toán khác nhau giải quyết các vấn đề ILP, nhưng tất cả chúng đều tương đối chậm về số bước cần thiết. Phiên bản tốt nhất mà họ có thể nghĩ ra - một loại 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 vấn đề (chẳng hạn như liệu nhân viên bán hàng có ghé thăm thành phố hay không) chỉ có thể giả sử các giá trị nhị phân (không hoặc 1). Trong trường hợp này, ILP có thời gian chạy tăng theo cấp số nhân theo số lượng biến, còn được gọi là thứ nguyên. (Nếu chỉ có một biến, chỉ cần hai bước để kiểm tra mọi kết hợp có thể có và giải quyết vấn đề; hai biến có nghĩa là bốn bước, ba biến có nghĩa là tám bước, v.v.)

Thật không may, khi các biến có giá trị vượt quá 1 và XNUMX, thời gian chạy của thuật toán sẽ lâu hơn nhiều. Các nhà nghiên cứu từ lâu đã tự hỏi liệu họ có thể tiến gần hơn đến lý tưởng tầm thường hay không. Tiến độ diễn ra chậm chạp, với ghi được thiết lập vào những năm 1980 và chỉ tăng dần cải tiến được thực hiện kể từ đó.

Nhưng gần đây công việc by Victor Reis, hiện đang ở Viện Nghiên cứu Cao cấp, và Thomas Rothvoss, tại Đại học Washington, đã đạt được bước nhảy vọt về thời gian chạy lớn nhất trong nhiều thập kỷ. Bằng cách kết hợp các công cụ hình học để hạn chế các giải pháp khả thi, họ đã tạo ra một thuật toán mới, nhanh hơn để giải ILP trong thời gian gần như giống như trường hợp nhị phân tầm thường. Kết quả đã nhận được giải thưởng bài viết hay nhất năm 2023 Cơ sở khoa học máy tính hội nghị.

“Thuật toán mới này cực kỳ thú vị,” cho biết Noah Stephens-Davidowitz, một nhà toán học và nhà khoa học máy tính tại Đại học Cornell. “Nó đại diện cho sự cải tiến [lớn] đầu tiên đối với bộ giải ILP trong gần 40 năm.”

ILP hoạt động bằng cách chuyển một bài toán đã cho thành một tập hợp các phương trình tuyến tính thỏa mãn một số bất đẳng thức. Các phương trình cụ thể được xây dựng dựa trên chi tiết của bài toán ban đầu. Nhưng mặc dù những chi tiết này có thể khác nhau, nhưng bản chất cơ bản của các vấn đề ILP vẫn giống nhau, mang lại cho các nhà nghiên cứu một cách duy nhất để giải quyết vô số vấn đề.

Điều đó không có nghĩa là đây là công việc dễ dàng. Mãi đến năm 1983 nhà toán học Hendrik Lenstra chứng minh rằng bài toán tổng quát thậm chí còn có thể giải được, cung cấp thuật toán đầu tiên có thể giải được điều đó. Lenstra nghĩ về ILP về mặt hình học. Đầu tiên, ông biến các bất đẳng thức ở trung tâm của ILP thành một dạng lồi, giống như bất kỳ đa giác đều nào. Hình dạng này thể hiện các ràng buộc của từng vấn đề mà bạn đang giải quyết, cho dù đó là sản xuất ghế dài hay lập lịch trình hàng không, do đó, phần bên trong của hình dạng này tương ứng với tất cả các giá trị có thể có để giải quyết các bất đẳng thức và do đó giải quyết được vấn đề. Lenstra gọi hình dạng này là vật lồi. Kích thước của bài toán ảnh hưởng đến kích thước của hình này: Với hai biến, nó có dạng đa giác phẳng; trong ba chiều nó là một Platonic rắn, Và như vậy.

Tiếp theo, Lenstra tưởng tượng tất cả các số nguyên là một tập hợp vô hạn các điểm lưới, được biết đến trong toán học là một mạng tinh thể. Phiên bản hai chiều trông giống như một biển các chấm và ở dạng ba chiều, nó trông giống như các điểm nối các dầm thép trong tòa nhà. Kích thước của mạng cũng phụ thuộc vào kích thước của một bài toán nhất định.

Để giải một bài toán ILP cho trước, Lenstra chỉ ra rằng bạn chỉ cần tìm nơi các nghiệm khả thi đáp ứng tập hợp các số nguyên: tại giao điểm của vật lồi và mạng tinh thể. Và anh ấy đã nghĩ ra một thuật toán có thể tìm kiếm không gian này một cách thấu đáo — nhưng để có hiệu quả, đôi khi nó phải chia vấn đề thành những phần có kích thước nhỏ hơn, thêm nhiều bước vào thời gian chạy.

Trong những năm tiếp theo, một số nhà nghiên cứu đã khám phá cách làm cho thuật toán này chạy nhanh hơn. Năm 1988, Ravi Kannan và László Lovász đưa ra một khái niệm gọi là bán kính bao phủ, mượn từ việc nghiên cứu mã sửa lỗi, để giúp vật lồi và mạng giao nhau hiệu quả hơn. Đại khái, bán kính bao phủ đảm bảo rằng vật lồi luôn chứa ít nhất một điểm nguyên, bất kể bạn đặt nó ở đâu trên mạng. Do đó, kích thước của bán kính bao phủ cũng quyết định mức độ hiệu quả mà bạn có thể giải quyết vấn đề ILP.

Vì vậy, tất cả đều phụ thuộc vào việc xác định kích thước của bán kính bao phủ lý tưởng. Thật không may, bản thân điều này đã chứng tỏ là một vấn đề khó, và điều tốt nhất mà Kannan và Lovász có thể làm là thu hẹp một giá trị có thể có bằng cách tìm kiếm các giới hạn trên và dưới. Họ chỉ ra rằng giới hạn trên - kích thước tối đa của bán kính bao phủ - tăng tuyến tính với kích thước. Tốc độ này khá nhanh nhưng không đủ để tăng tốc đáng kể thời gian chạy ILP. Trong 30 năm tiếp theo, các nhà nghiên cứu khác chỉ có thể làm tốt hơn một chút.

Điều cuối cùng đã giúp Reis và Rothvoss vượt qua là một kết quả toán học không liên quan mà chỉ tập trung hoàn toàn vào mạng tinh thể. Năm 2016, Oded Regev và Stephens-Davidowitz cho thấy, trên thực tế, có bao nhiêu điểm mạng có thể vừa với một hình dạng cụ thể. Reis và Rothvoss áp dụng điều này cho các hình dạng khác, cho phép họ ước tính tốt hơn số lượng điểm mạng có trong bán kính bao phủ ILP, hạ thấp giới hạn trên. Regev nói: “Bước đột phá mới nhất đến từ việc nhận ra rằng bạn thực sự có thể tạo ra các loại hình dạng khác.

Giới hạn trên được thắt chặt mới này là một cải tiến vượt bậc, cho phép Reis và Rothvoss đạt được tốc độ tăng tốc đáng kể của thuật toán ILP tổng thể. Công việc của họ mang lại thời gian chạy (log n)^O(n), Nơi n là số lượng biến và O (n)có nghĩa là nó tỷ lệ tuyến tính với n. (Biểu thức này được coi là “gần giống” với thời gian thực hiện của bài toán nhị phân.)

“Đó là một chiến thắng ở sự giao thoa giữa toán học, khoa học máy tính và hình học,” nói Daniel Dadush của viện nghiên cứu quốc gia CWI ở Hà Lan, người đã giúp đi tiên phong trong thuật toán mà Reis và Rothvoss sử dụng để đo thời gian chạy ILP.

Hiện tại, thuật toán mới chưa thực sự được sử dụng để giải quyết bất kỳ vấn đề hậu cần nào vì sẽ mất quá nhiều công sức để cập nhật các chương trình ngày nay để sử dụng nó. Nhưng đối với Rothvoss, điều đó không còn quan trọng nữa. “Đó là sự hiểu biết lý thuyết về một vấn đề có những ứng dụng cơ bản,” ông nói.

Về việc liệu hiệu quả tính toán của ILP có thể được cải thiện hơn nữa hay không, các nhà nghiên cứu vẫn hy vọng rằng họ sẽ tiếp tục đạt được thời gian chạy lý tưởng - nhưng không sớm như vậy. “Điều đó đòi hỏi một ý tưởng mới về cơ bản,” Vempala nói.