Tôi đã tham gia thiết kế, phát triển và triển khai các mô hình nghiên cứu hoạt động [OR] và tối ưu hóa như Chương trình tuyến tính [LP], Chương trình tuyến tính số nguyên hỗn hợp [MILP] và Chương trình bậc hai [QP] trong hơn một thập kỷ. Trong bốn năm qua, tôi đã nhận ra tầm quan trọng của các giải pháp OR [i. e. , giải pháp phần mềm dựa trên các mô hình tối ưu hóa] để giải các loại chương trình này. Trước đây, chúng tôi thường lập mô hình vấn đề tối ưu hóa trong thế giới thực với các gói LP/MILP riêng lẻ như GAMS, AMPL, OPL hoặc các gói khác, sau đó giải quyết vấn đề đó bằng bộ giải tối ưu hóa [chẳng hạn như CPLEX, Gurobi, Mosek, Xpress, . ] và đưa ra kết quả tối ưu cho các nhà quản lý và ra quyết định. Do đó, các mô hình tối ưu hóa được thiết kế theo truyền thống để sử dụng trong các quyết định chiến lược/chiến thuật hơn là các quyết định vận hành
Tuy nhiên, ngày nay, nhiều người trong ngành muốn thường xuyên lập kế hoạch và đưa ra các quyết định tối ưu như một phần trong hoạt động hàng giờ, hàng ngày hoặc hàng tuần của họ. Những tiến bộ tính toán gần đây đã cung cấp cơ sở hạ tầng để chúng tôi kết hợp các mô hình tối ưu hóa trong các giải pháp phần mềm phân tích. Điều này có nghĩa là những người hành nghề OR ngày nay cần thiết kế, lập mô hình và triển khai các công cụ phần mềm mạnh mẽ dựa trên các mô hình LP/MILP. Họ cần sử dụng một ngôn ngữ lập trình như C ++, Java, C #, Python, v.v. cho mục đích đó
Một ngôn ngữ lập trình tốt và phổ biến được nhiều người trong cộng đồng OR và Khoa học dữ liệu khuyên dùng là Python. Nó dễ dàng, linh hoạt và mạnh mẽ, đồng thời có các thư viện tuyệt vời dành cho Học máy, Tối ưu hóa và Mô hình hóa thống kê. Trong blog này, tôi sẽ tập trung vào cách một người có thể sử dụng Python để viết các mô hình OR [LPs/MILPs]
Nhiều bộ giải tối ưu hóa [thương mại và mã nguồn mở] có giao diện Python để lập mô hình LP, MILP và QP. Ở đây tôi đã chọn CPLEX và Gurobi, vì chúng nằm trong số những bộ giải thương mại hàng đầu và PuLP, một gói mô hình nguồn mở mạnh mẽ trong Python. Tôi sẽ cung cấp hướng dẫn song song cho từng gói này và tôi hy vọng nó sẽ giúp bạn dễ dàng dịch mô hình của mình từ gói này sang gói khác. Ở đây, chúng tôi sử dụng
import docplex.mp.model as cpxopt_model = cpx.Model[name="MIP Model"]0 [API Python của Gurobi],
import docplex.mp.model as cpxopt_model = cpx.Model[name="MIP Model"]1 [gói Mô hình hóa CPLEX tối ưu hóa quyết định của IBM cho Python] và
import docplex.mp.model as cpxopt_model = cpx.Model[name="MIP Model"]2 [một trình tạo mô hình LP/MILP được viết bằng Python]. Với mục đích của bài đăng này, tôi sẽ cho rằng bạn đã quen thuộc với Python, tôi. e. , bạn biết cách cài đặt và sử dụng các gói Python và sử dụng các cấu trúc dữ liệu Python như danh sách, bộ dữ liệu và từ điển. Tôi cũng sẽ đảm nhận kiến thức cơ bản về lập trình tuyến tính, lập trình số nguyên hỗn hợp và tối ưu hóa có ràng buộc
Bây giờ, hãy đi sâu vào mô hình tối ưu hóa với Gurobi, CPLEX và PuLP. Tóm lại, một mô hình tối ưu hóa là một bài toán có một mục tiêu [hoặc một tập hợp các mục tiêu trong lập trình đa mục tiêu], một tập hợp các ràng buộc và một tập hợp các biến quyết định. Sau đây là một mô hình tối ưu hóa đơn giản
Mô hình tối ưu hóa
Trong ví dụ tối ưu hóa ở trên, n, m, a, c, l, u và b là các tham số đầu vào và được giả định là đã cho. Để viết mã Python, chúng tôi đặt các tham số này như sau
import randomn = 10
m = 5
set_I = range[1, n+1]
set_J = range[1, m+1]
c = {[i,j]: random.normalvariate[0,1] for i in set_I for j in set_J}
a = {[i,j]: random.normalvariate[0,5] for i in set_I for j in set_J}
l = {[i,j]: random.randint[0,10] for i in set_I for j in set_J}
u = {[i,j]: random.randint[10,20] for i in set_I for j in set_J}
b = {j: random.randint[0,30] for j in set_J}
Bây giờ là lúc triển khai mô hình OR của chúng ta bằng Python. Khi chúng tôi muốn mã hóa một mô hình tối ưu hóa, chúng tôi đặt một trình giữ chỗ cho mô hình đó [như một khung vẽ trống], sau đó thêm các phần tử của nó [các biến quyết định và các ràng buộc] vào đó. Đây là cách
- Gurobi
import gurobiby as grbopt_model = grb.Model[name="MIP Model"]
- CPLEX
import docplex.mp.model as cpxopt_model = cpx.Model[name="MIP Model"]
- bột giấy
import pulp as plpopt_model = plp.LpProblem[name="MIP Model"]
Sau bước này, chúng ta có một Model Object có tên là opt_model. Tiếp theo, chúng ta cần thêm các biến quyết định. Đó là tiêu chuẩn để lưu trữ các biến quyết định trong từ điển Python [hoặc Sê-ri Pandas] trong đó các khóa từ điển là các biến quyết định và các giá trị là các đối tượng biến quyết định. Một biến quyết định được xác định với ba thuộc tính chính. loại của nó [liên tục, nhị phân hoặc số nguyên], giới hạn dưới của nó [0 theo mặc định] và giới hạn trên của nó [theo mặc định là vô hạn]. Đối với ví dụ trên, chúng ta có thể định nghĩa các biến quyết định là
- Gurobi
# if x is Continuous
x_vars ={[i,j]:opt_model.addVar[vtype=grb.GRB.CONTINUOUS,
lb=l[i,j],
ub= u[i,j],
name="x_{0}_{1}".format[i,j]]
for i in set_I for j in set_J}# if x is Binary
x_vars = {[i,j]:opt_model.addVar[vtype=grb.GRB.BINARY,
name="x_{0}_{1}".format[i,j]]
for i in set_I for j in set_J}# if x is Integer
x_vars ={[i,j]:opt_model.addVar[vtype=grb.GRB.INTEGER,
lb=l[i,j],
ub= u[i,j],
name="x_{0}_{1}".format[i,j]]
for i in set_I for j in set_J}
- CPLEX
- bột giấy
# if x is Continuous
x_vars = {[i,j]:
plp.LpVariable[cat=plp.LpContinuous,
lowBound=l[i,j], upBound=u[i,j],
name="x_{0}_{1}".format[i,j]]
for i in set_I for j in set_J}# if x is Binary
x_vars = {[i,j]:
plp.LpVariable[cat=plp.LpBinary, name="x_{0}_{1}".format[i,j]]
for i in set_I for j in set_J}# if x is Integer
x_vars = {[i,j]:
plp.LpVariable[cat=plp.LpInteger,
lowBound=l[i,j], upBound= u[i,j],
name="x_{0}_{1}".format[i,j]]
for i in set_I for j in set_J}
Sau khi đặt các biến quyết định và thêm chúng vào mô hình của chúng tôi, đã đến lúc đặt các ràng buộc. Bất kỳ ràng buộc nào cũng có ba phần. vế trái [thường là sự kết hợp tuyến tính của các biến quyết định], vế phải [thường là giá trị số] và ý nghĩa [Nhỏ hơn hoặc bằng, Bằng hoặc Lớn hơn hoặc bằng]. Để thiết lập bất kỳ ràng buộc nào, chúng ta cần thiết lập từng phần
- Gurobi
import docplex.mp.model as cpxopt_model = cpx.Model[name="MIP Model"]0
- CPLEX
import docplex.mp.model as cpxopt_model = cpx.Model[name="MIP Model"]1
- bột giấy
import docplex.mp.model as cpxopt_model = cpx.Model[name="MIP Model"]2
Bước tiếp theo là xác định một mục tiêu, đó là một biểu thức tuyến tính. Đây là cách chúng ta có thể xác định một mục tiêu
- Gurobi
import gurobiby as grbopt_model = grb.Model[name="MIP Model"]0
- CPLEX
import gurobiby as grbopt_model = grb.Model[name="MIP Model"]1
- bột giấy
import gurobiby as grbopt_model = grb.Model[name="MIP Model"]2
Bây giờ chúng ta cần thêm một mục tiêu vào mô hình của mình
- Gurobi
import gurobiby as grbopt_model = grb.Model[name="MIP Model"]3
- CPLEX
import gurobiby as grbopt_model = grb.Model[name="MIP Model"]4
- bột giấy
import gurobiby as grbopt_model = grb.Model[name="MIP Model"]5
Cuối cùng, chúng tôi gọi bộ giải để giải mô hình tối ưu hóa của chúng tôi. Trong PuLP, bộ giải mặc định là CBC, nhưng nó cũng có thể hoạt động với các bộ giải khác. Đây là bước cuối cùng trong việc giải quyết mô hình của chúng tôi
- Gurobi
import gurobiby as grbopt_model = grb.Model[name="MIP Model"]6
- CPLEX
import gurobiby as grbopt_model = grb.Model[name="MIP Model"]7
- bột giấy
import gurobiby as grbopt_model = grb.Model[name="MIP Model"]8
Bây giờ chúng ta đã hoàn thành. Chúng ta chỉ cần lấy kết quả và xử lý hậu kỳ. Tôi thấy rằng gói Pandas là một thư viện xử lý dữ liệu tốt. Nếu bài toán được giải tối ưu ta có thể thu được và xử lý kết quả như sau
import gurobiby as grbopt_model = grb.Model[name="MIP Model"]9
Ở đây,
import docplex.mp.model as cpxopt_model = cpx.Model[name="MIP Model"]3 là một khung dữ liệu Pandas chứa các giá trị tối ưu của từng biến quyết định. Chúng tôi cũng có thể lưu các kết quả này trong tệp CSV như được hiển thị ở trên
Chúng tôi chỉ đề cập đến mô hình hóa cấp cao trong Python, nhưng tất cả các gói trên đều chứa các hàm và cấu trúc dữ liệu hữu ích cần được xem xét khi bạn viết mã sẵn sàng sản xuất. Ví dụ: trong Gurobi, bạn có thể thêm một tập hợp các biến cùng một lúc bằng cách sử dụng
import docplex.mp.model as cpxopt_model = cpx.Model[name="MIP Model"]4, trong khi ở CPLEX, đó là
import docplex.mp.model as cpxopt_model = cpx.Model[name="MIP Model"]5,
import docplex.mp.model as cpxopt_model = cpx.Model[name="MIP Model"]6 hoặc
import docplex.mp.model as cpxopt_model = cpx.Model[name="MIP Model"]7 và trong PuLP, điều đó có thể được thực hiện bằng
import docplex.mp.model as cpxopt_model = cpx.Model[name="MIP Model"]8
Nếu bạn thấy điều này hữu ích, có thể bạn sẽ thích xem bài đăng này về các mẹo và thủ thuật để cải thiện mô hình OR, một thử nghiệm gọn gàng nơi chúng tôi áp dụng tối ưu hóa cho máy học hoặc một số lưu ý về việc áp dụng Gurobi trong thế giới thực
_________________________________________________________________
Nếu bạn thích bài đăng trên blog này, hãy xem thêm công việc của chúng tôi, theo dõi chúng tôi trên phương tiện truyền thông xã hội [Twitter, LinkedIn và Facebook] hoặc tham gia với chúng tôi trong các hội thảo trực tuyến miễn phí hàng tháng của Học viện