Giải pháp LP nâng cao

Mặc dù công nghệ LP đã phát triển mạnh mẽ, nhưng một số trường hợp sử dụng yêu cầu các kỹ thuật tiên tiến hơn. Ví dụ: hiện có một số thuật toán và phương thức triển khai LP khác nhau, mỗi thuật toán có điểm mạnh và điểm yếu. Hơn nữa, sự bất ổn định về số có thể khiến các trình phân giải giảm tốc độ hoặc không giải được một số mô hình nhất định.

Hướng dẫn này giới thiệu các khái niệm và đưa ra ví dụ để giúp bạn đạt được hiệu suất và độ tin cậy cao nhất từ trình giải LP.

Khái niệm

Phần này trình bày các khái niệm chính để sử dụng trình phân giải LP nâng cao. Chúng tôi giả định rằng độc giả đã quen thuộc với khái niệm tính trùng lặp trong LP.

Nhóm thuật toán LP

Bạn có thể truy cập vào các lớp thuật toán sau đây của LP thông qua công cụ OR-Tools.

  1. Thuật toán Simplex là thuật toán LP thực tế đầu tiên và vẫn là thuật toán phổ biến nhất. Thuật toán di chuyển dọc theo các đỉnh (các điểm góc) của khu vực khả thi, liên tục cải thiện giá trị của hàm mục tiêu cho đến khi đạt được giải pháp tối ưu. Có hai loại thuật toán đơn giản:

    1. Primal đơn giản thực hiện các bước dọc theo các đỉnh của khu vực sơ cấp khả thi. Biến thể này đặc biệt hiệu quả trong việc giải quyết một chuỗi vấn đề LP với các hàm mục tiêu khác nhau, tức là trong đó khu vực gốc khả thi được cố định.
    2. Dual simplex thực hiện các bước dọc theo các đỉnh của khu vực khả thi kép. Biến thể này đặc biệt hiệu quả trong việc giải quyết một chuỗi bài toán LP, trong đó khu vực có khả năng kép được cố định, chẳng hạn như khi chỉ có giới hạn về các biến thay đổi. Vì lý do này, thuật toán kép đơn giản được sử dụng rộng rãi trong các trình phân giải MIP.

  2. Phương thức Barrier hoặc Internal-point (điểm nội bộ) là nhóm thuật toán thực tế thứ hai của LP. Phương pháp rào cản kết hợp các đảm bảo về mặt lý thuyết về việc hội tụ hiệu quả (thời gian đa thức) với hiệu suất đáng tin cậy trong thực tế. Chúng bổ sung cho thuật toán đơn giản khi thuật toán hoạt động kém; ví dụ: một số trình phân giải cung cấp chạy song song cả đơn giản và rào cản, trả về giải pháp từ thuật toán kết thúc trước.

  3. Phương thức bậc nhất là một bộ thuật toán chỉ sử dụng thông tin chuyển màu (tức là các đạo hàm bậc nhất) để định hướng các lần lặp. Giảm độ dốc là một ví dụ phổ biến. Các phương pháp này phổ biến trong phương pháp tối ưu hoá phi tuyến tính và công nghệ học máy. Đối với LP, các phương thức bậc nhất có thể mở rộng quy mô cho các vấn đề lớn hơn đơn giản và rào cản, đồng thời cũng có thể có yêu cầu nhỏ hơn về bộ nhớ. Mặt khác, các phương pháp này nhạy cảm hơn với các vấn đề về số và có thể gặp khó khăn để có được các giải pháp có độ chính xác cao.

Bảng dưới đây liệt kê các trình phân giải LP có trong công cụ OR-Tools và cho biết 3 bộ thuật toán nào được triển khai trong mỗi trình phân giải.

Trình giải toán Đơn giản Rào chắn Đơn đặt hàng đầu tiên
Kẹp X X
CPLEXL X X
Hiển thị nhanhG X
GLPK (Nhóm địa điểm toàn cầu) X X
Tiếng GurobiL X X
PDLPG (Ngăn chặn mất dữ liệu) X
XpressL X X

G cho biết trình giải toán do Google phát triển. L cho biết trình giải quyết yêu cầu giấy phép do nhà phát triển bên thứ ba tương ứng cấp.

Xem phần Đề xuất để biết các đề xuất về trình phân giải và thuật toán nên sử dụng.

Giải quyết vấn đề thực sự có nghĩa là gì?

Để khai thác tối đa trình giải LP, bạn cần phải hiểu rõ khái niệm gì khi trình giải tuyên bố đã tìm ra giải pháp cho vấn đề LP. Phần này trình bày những thông tin cơ bản cần thiết để trả lời câu hỏi này, cụ thể là do tính không chính xác về mặt số học và tính không duy nhất của các nghiệm.

Dung sai

Trình phân giải LP hầu như luôn sử dụng số học dấu phẩy động, khiến các lời giải của chúng phải phụ thuộc vào độ chính xác số. Để tính đến vấn đề này và cải thiện hiệu suất bằng cách tránh tốn công sức vào các giải pháp đã đủ tốt, trình giải quyết chấp nhận các giải pháp và tuyên bố đã giải quyết được vấn đề khi các giải pháp này đáp ứng những điều kiện đạt đến một số dung sai nhất định.

Hãy xem xét bài toán lập trình tuyến tính

$$ \begin{align*} \min\quad & -2x_1 - x_2 \\ \text{s.t.}\quad& x_1 + x_2 \le 1\\ & x_1, x_2 \ge 0 \end{align*} $$

và bài toán kép tương ứng

$$ \begin{align*} \max\quad& y \\ \text{s.t.}\quad& -2 - y \ge 0\\ &-1 - y \ge 0 \\ &y \le 0 \end{align*} $$

Cặp bài toán này có nghiệm nguyên thuỷ tối ưu duy nhất là $ x_1 = 1, x_2 = 0 $ và nghiệm kép $ y = -2 $. Giải pháp nào có thể được trình giải toán chấp nhận là tối ưu? Để trả lời điều này, chúng tôi xác định các lượng tử sau:

  • Khoảng trống độ kép là mức chênh lệch giữa giá trị mục tiêu ban đầu và giá trị mục tiêu kép, trong trường hợp này là $ |(-2x_1 - x_2) - y| $.
  • Tính khả năng nguyên vẹn là vi phạm các giới hạn nguyên thuỷ, trong trường hợp này, $ (\max\{ (x_1+x_2) - 1, 0 \}, \max\{-x_1, 0\}, \max\{-x_2, 0\}) $.
  • Tính khả năng kép là các vi phạm của điều kiện ràng buộc kép, trong trường hợp này, $ (\max\{ 2 + y, 0 \}, \max\{ 1 + y, 0 \}, \max\{ y, 0 \}) $.

Trình giải toán khai báo một giải pháp là tối ưu nếu khoảng cách kép, tình trạng khả năng nguyên thuỷ và khả năng kép nhỏ hơn dung sai cho trước.1

Đáng chú ý là việc áp dụng dung sai sẽ khác nhau vì cả lý do tự nhiên và không đồng bộ giữa các trình phân giải và thuật toán. Ví dụ: khoảng cách kép trong thuật toán đơn giản chỉ được điều chỉnh bằng số liệu không chính xác, trong khi tính khả thi kép và nguyên tắc xuất hiện ngay cả trong số học chính xác. Một số phương pháp thực thi trực tiếp các ràng buộc giới hạn $ x_1 \ge 0, x_2 \ge 0, $ và $ y \le 0 $, trong khi các phương pháp khác xử lý các vi phạm giới hạn ràng buộc khác với vi phạm các ràng buộc tuyến tính như $x_1 + x_2 \le 1$. Đối với một số bộ giải, dung sai $silon là tuyệt đối; nghĩa là có một $ tham số $ \epsilon

Để biết ví dụ về ảnh hưởng của dung sai, hãy xem xét dung sai tuyệt đối $ \epsilon = \frac{1}{2} $ được áp dụng cho cặp nguyên tố-kép ở trên. Nghiệm $ x_1 = 1,5, x_2 = 0, y = -3 $ không có khoảng cách kép và tất cả các khả năng đều nhỏ hơn hoặc bằng $ \epsilon $, do đó, trình giải toán có thể khai báo giải pháp này là "tối ưu". Tuy nhiên, giá trị mục tiêu (-3) khác 1 so với giá trị mục tiêu tối ưu thực sự là -2. Các giá trị mặc định thường thấy của $ \epsilon $ là từ $10^{-6}$ đến $10^{-8}$. Điều này khiến các ví dụ cực kỳ hiếm gặp nhưng không thể thực hiện được.

Loại giải pháp

Các bài tập LP có thể có nhiều giải pháp tối ưu, thậm chí còn nhiều giải pháp hơn khi tính đến dung sai. Chúng tôi thảo luận ngắn gọn về tính chất của các giải pháp do 3 dòng thuật toán LP trả về được trình bày ở trên.

Thuật toán Simplex luôn trả về các đỉnh hoặc điểm góc của vùng khả thi. Các giải pháp này được ưu tiên hơn trong một số trường hợp vì chúng có xu hướng thưa thớt hơn.

Phương pháp rào cản và phương pháp bậc nhất thường không trả về đỉnh. (Lý thuyết cung cấp thêm các đặc điểm nằm ngoài phạm vi của hướng dẫn này.)

Vì các lý do trước đây và vì các giải pháp đỉnh có các thuộc tính hấp dẫn, nên theo mặc định, trình phân giải thường áp dụng quy trình ghép chéo để chuyển sang một đỉnh tối ưu từ giải pháp do thuật toán rào cản tìm thấy. Tính năng kết hợp hiện không được cung cấp cho các giải pháp được tìm thấy bằng phương thức thứ nhất.

Đề xuất

Chúng tôi đưa ra các đề xuất sau đây về việc sử dụng trình phân giải LP nâng cao.

Mở rộng quy mô dữ liệu bài toán

Trình giải quyết có thể gặp phải tình trạng hội tụ chậm hoặc lỗi trên các mô hình do các vấn đề về số. Những vấn đề như vậy có thể phát sinh vì nhiều lý do; sau đây là ví dụ.

Các hằng số số rất nhỏ hoặc lớn thường xuất hiện trong các mô hình LP. Mở rộng ví dụ ở trên, nếu \(x_1\) và \(x_2\) đại diện cho phần khách hàng được chỉ định cho "nhà cung cấp 1" hoặc "nhà cung cấp 2" và nếu muốn tối đa hóa lợi ích từ việc phục vụ những khách hàng này, chúng ta có thể viết hàm mục tiêu sau,

$$ \min -c_1x_1 - c_2x_2 $$

trong đó:

  • $ c_1 $ là lợi ích từ việc chỉ định khách hàng cho nhà cung cấp 1
  • $ c_2 $ là lợi ích từ việc chỉ định khách hàng cho nhà cung cấp 2

Tệp kép đáp ứng các điều kiện ràng buộc sau đây sẽ được xem là khả thi với dung sai tuyệt đối $ \epsilon $:

  • $ y \le -c_1 + \epsilon $,
  • $ y \le -c_2 + \epsilon $.

Nếu đơn vị lợi ích $ c_1 $ và $ c_2 $ là các giá trị phân số nhỏ diễn ra cùng quy mô với $ \epsilon $, thì điều kiện khả thi kép sẽ trở nên khá yếu, do đó một nguyên tố sơ cấp rất tối ưu có thể được khai báo là tối ưu.

Mặt khác, nếu các đơn vị lợi ích là "microdollars" (1 000 000 microdollars = 1 đô la), thì kết quả là các giá trị tuyệt đối rất lớn sẽ yêu cầu độ chính xác rất cao trong giải pháp, có thể cao một cách bất hợp lý do giới hạn của số dấu phẩy động. Các trình giải toán có thể không hội tụ nếu bài toán được xây dựng theo cách này. Trong quá trình xây dựng một bài toán có sẵn, các nhà lập mô hình nâng cao nên cân nhắc xem dữ liệu bài toán có được điều chỉnh theo tỷ lệ phù hợp với khả năng giải quyết của họ hay không.

Ngoài việc tránh các lỗi số, bạn cũng có thể điều chỉnh dung sai để đạt hiệu suất tốt hơn. Các phương thức Simplex và rào cản không quá nhạy cảm với dung sai nhưng đôi khi có thể hưởng lợi từ dung sai lớn hơn nếu tiến trình được quan sát thấy chững lại ở cuối quá trình giải. Mặt khác, các phương thức bậc nhất thường nhạy cảm hơn nhiều. Người dùng phương thức bậc nhất có thể hưởng lợi từ các giải pháp nhanh hơn bằng cách giảm dung sai, trong trường hợp bối cảnh cho phép.

Đối với dung sai của Glop, hãy xem primal_feasibility_tolerance, dual_feasibility_tolerance và solution_feasibility_tolerance trong GlopParameters. Xin lưu ý rằng primal_feasibility_tolerance và dual_feasibility_tolerance được sử dụng trong thuật toán, trong khi solution_feasibility_tolerance được kiểm tra sau khi giải quyết để gắn cờ các vấn đề số. Đối với tính năng Ngăn chặn mất dữ liệu (PDLP), hãy xem eps_optimal_absolute và eps_optimal_relative.

Để đọc thêm về các loại vấn đề này, hãy xem Hướng dẫn về các vấn đề số của Gurobi. Mặc dù các nguyên tắc được viết cho người dùng Gurobi, nhưng nhiều nguyên tắc trong số đó vẫn được áp dụng chung.

Lựa chọn trình giải và thuật toán

Chúng tôi bắt đầu bằng một ví dụ về tác động lớn của việc lựa chọn trình phân giải và thuật toán, sau đó trình bày hướng dẫn chọn trình phân giải LP.

Sự khác biệt trong thực tế

Chúng tôi minh hoạ sự thay đổi về hiệu suất giữa các thuật toán LP và trình phân giải bằng cách so sánh thời gian giải quyết trên một số thực thể mà Hanans Mittelmann sử dụng để đo điểm chuẩn trình phân giải LP. Các thực thể này được chọn rõ ràng để cho thấy các điểm cực đoan của hiệu suất tương đối và không nhất thiết phải đại diện cho hành vi thông thường.

Các phương pháp cơ bản và đơn giản kép của Glop được so sánh với phương pháp rào cản của Gurobi (có và không chéo, giúp tìm ra giải pháp đỉnh) và PDLP (phương thức bậc nhất) với độ chính xác cao và thấp. Bảng dưới đây báo cáo giải quyết thời gian tính bằng giây, với giới hạn là 20 phút (1200 giây).

Thực thể Hiệu ứng glop
(đơn giản) nguyên bản		 Chế độ xem nhanh
Đơn giản kép		 Rào chắn Gurobi
kết hợp với xe cắt ngang		 Rào chắn Gurobi
không có Cây chắn		 PDLP
có độ chính xác cao		 PDLP
có độ chính xác thấp
ex10 >1200 >1200 79.7 63.5 8.2 2.7
nug08-3 >1200 252.8 144,6 3.2 1.1 0,9
savsched1 >1200 >1200 156.0 22,6 46.4 32.4
wide15 >1200 20,8 >1200 >1200 916,4 56.3
năng lượng xây dựng 178.4 267.5 12,8 12.3 >1200 157.2
Thuỵ Điển 12.1 520.6 15.2 16.4 >1200 >1200
Phiên bản Solver OR-Tools 9.3 OR-Tools 9.3 Đồng Gurobi 9.0 Đồng Gurobi 9.0 OR-Tools 9.3 OR-Tools 9.3
solver_specific_parameters (mặc định) use_dual_simplex: true Method 2, Threads 1 Method 2, Crossover 0, Threads 1 termination_criteria { eps_optimal_absolute: 1e-8 eps_optimal_relative: 1e-8 } termination_criteria { eps_optimal_absolute: 1e-4 eps_optimal_relative: 1e-4 }

Từ những kết quả này, chúng tôi kết luận như sau.

  • Hiệu suất tương đối của các thuật toán và trình giải có thể khác nhau theo thứ tự độ lớn trên một thực thể.
  • Không có thuật toán và trình giải toán duy nhất nào tốt hơn các thuật toán khác.
  • Sự kết hợp (được bật theo mặc định) giúp tăng thời gian xử lý, đôi khi đáng kể.
  • PDLP có thể xử lý độ chính xác thấp đôi khi nhanh hơn gấp 10 lần so với độ chính xác cao.

Hướng dẫn ngắn gọn về cách chọn trình giải LP

Vì không có thuật toán hoặc trình phân giải LP nào là tốt nhất, nên bạn nên thực hiện các bước sau để khám phá dữ liệu phù hợp nhất cho trường hợp sử dụng của mình. Bắt đầu với bước đầu tiên và chuyển sang bước tiếp theo nếu hiệu suất không đủ.

  1. Hãy thử dùng Glop. Lý do: Glop là phương thức triển khai nội bộ của Google cho các phương thức đơn giản và nguyên gốc. Glop là nguồn mở và đáng tin cậy cho tải công việc phát hành công khai của Google.
    • Nếu cấu hình mặc định (primal Simplex) không hoạt động tốt, hãy thử chuyển sang đơn giản kép bằng cách sử dụng use_dual_simplex: true.
  2. Nếu có giấy phép, hãy dùng thử một trình giải toán thương mại (CPLEX, Gurobi hoặc Xpress). Thử nghiệm với phương pháp đơn giản và rào cản. Lý do: Những trình phân giải này theo tiêu chuẩn ngành và được tối ưu hoá cao. Ngoài ra, các phương thức rào cản bổ sung cho các thuật toán đơn giản do Glop cung cấp.
    • Nếu sử dụng thanh chắn, hãy tắt tính năng "giao thoa" nếu bạn không cần giải pháp đỉnh.
  3. Hãy thử tính năng PDLP. Điều chỉnh dung sai hội tụ cho ứng dụng của bạn. Lý do: PDLP được thiết kế cho những vấn đề lớn nhất, khi phương thức đơn giản và rào cản đạt đến giới hạn bộ nhớ hoặc quá chậm. PDLP hoạt động hiệu quả nhất khi một giải pháp gần đúng nhưng nhanh chóng được ưu tiên cho một giải pháp chính xác nhưng chậm.
  4. Nếu đã đi được đến bước này thì giờ bạn đã là người dùng LP nâng cao! Vui lòng xem các tuỳ chọn hỗ trợ của phần OR-Tools để được trợ giúp thêm.

  1. Thông tin này thường phức tạp hơn thế. Trình giải quyết thường kiểm tra các điều kiện này trên một phiên bản bài toán đã được biến đổi/đơn giản hoá, được gọi là vấn đề đã được giải quyết. Trong một số trường hợp, giải pháp cho vấn đề đã giải quyết có thể không phải là giải pháp cho vấn đề đầu vào. Trường hợp này có thể dẫn đến các trạng thái bất thường như OptimalInfeas của CPLEX hoặc IMPRECISE của Glop.↩