参考:python运筹优化(一):Cplex for python使用简介
下面是一个简单的优化模型:
$$ min sum_{i=1}^{n} sum_{j=1}^{m} c_{ij} x_{ij} $$
$$s.t.$$
$$sum_{i=1}^{n} a_{ij}x_{ij} le b_j qquad forall j$$
$$x_{ij} ge l_{ij} qquad forall i,j$$
$$ x_{ij} le u_{ij} qquad forall i,j$$
在上述优化例子中,n、m、a、c、l、u、b为输入参数,假设为给定。为了编写Python代码,我们将这些参数设置如下:
有10*5个决策变量$x_{ij}$,10行5列
# 初始化变量的值 import random n = 10 m = 5 set_I = range(1, n+1) set_J = range(1, m+1)
后面的部分
# 初始化已知量 # 通过 random 生成随机数 # 都是以 字典 的形式来生成的 # 按照公式中需要的数据一一生成 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}
1. 导入运筹优化库
# 导入运筹优化库 import docplex.mp.model as cpx opt_model = cpx.Model(name="MIP Model")
2. 定义决策变量
在这一步之后,我们有一个名为opt_model的模型对象。接下来,我们需要添加决策变量。在Python字典(或panda系列)中存储决策变量是标准的,其中字典键是决策变量,值是决策变量对象。一个决策变量由三个主要属性定义:它的类型(连续、二进制或整数)、它的下界(默认为0)和上界(默认为无穷大)。对于上面的例子,我们可以将决策变量定义为:
# 如果 x 是连续的话,按照下面的定义 x_vars_c = {(i, j): opt_model.continuous_var(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}
不同的定义方式,针对上面的问题,下面两个只是参考
# 如果 x 是二进制 x_vars_b = {(i, j): opt_model.binary_var(name="x_{0}_{1}".format(i, j)) for i in set_I for j in set_J} # 如果 x 是整数 x_vars = {(i, j): opt_model.integer_var(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}
3. 约束条件
在设置决策变量并将它们添加到我们的模型之后,就到了设置约束的时候了。任何约束都有三个部分:左手边(通常是决策变量的线性组合)、右手边(通常是数值)和意义(小于或等于、等于、大于或等于)。要设置任何约束,我们需要设置每个部分:
$$sum_{i=1}^{n} a_{ij}x_{ij} le b_j qquad forall j$$
# <= constraints, 小于等于 # 也是写成了字典的形式 # 这样可以方便后面查看调用 # 实际上使用 opt_model.add_constraint 就可以将其加入到模型内部了 constraints = {j: opt_model.add_constraint( ct=opt_model.sum(a[i,j] * x_vars_c[i,j] for i in set_I) <= b[j], ctname="constraint_{0}".format(j)) for j in set_J}
下面两个作为参考
# >= constraints, 大约等于 constraints = {j: opt_model.add_constraint( ct=opt_model.sum(a[i,j] * x_vars_c[i,j] for i in set_I) >= b[j], ctname="constraint_{0}".format(j)) for j in set_J} # == constraints, 等于 constraints = {j: opt_model.add_constraint( ct=opt_model.sum(a[i,j] * x_vars_c[i,j] for i in set_I) == b[j], ctname="constraint_{0}".format(j)) for j in set_J}
下面是另外两个边界的约束条件
$$x_{ij} ge l_{ij} qquad forall i,j$$
constraints_l = {(i, j): opt_model.add_constraint( ct=x_vars_c[i,j] >= l[i,j], ctname="constraint_l_{0}_{1}".format(i,j)) for i in set_I for j in set_J}
$$ x_{ij} le u_{ij} qquad forall i,j$$
constraints_u = {(i, j): opt_model.add_constraint( ct=x_vars_c[i,j] <= u[i,j], ctname="constraint_u_{0}_{1}".format(i,j)) for i in set_I for j in set_J}
4. 目标函数
下一步是定义一个目标,它是一个线性表达式。我们可以这样定义目标:
$$ min sum_{i=1}^{n} sum_{j=1}^{m} c_{ij} x_{ij} $$
# 两层循环 # 然后将所有的数据相加 objective = opt_model.sum(x_vars_c[i,j] * c[i,j] for i in set_I for j in set_J) # for maximization opt_model.maximize(objective)
作为参考的
# for minimization opt_model.minimize(objective)
5. 求解模型
# solving with local cplex opt_model.solve()
作为参考的
# solving with cplex cloud opt_model.solve(url="your_cplex_cloud_url", key="your_api_key")
6. 获得结果
现在我们完成了。我们只需要得到结果并进行后期处理。panda包是一个很好的数据处理库。如果问题得到最优解,我们可以得到和处理结果如下:
# 可以直接打印结果 opt_model.print_solution()
输出结果
objective: 216.829 x_1_1=2.000 x_1_2=11.000 x_1_3=6.000 x_1_4=17.000 x_1_5=12.000 x_2_2=5.000 x_2_3=17.000 x_2_4=12.000 x_2_5=8.000 x_3_1=12.000 x_3_2=5.000 x_3_3=14.000 x_3_4=10.000 x_3_5=8.000 x_4_1=2.000 x_4_3=4.000 x_4_4=14.000 x_4_5=2.000 x_5_2=16.321 x_5_3=5.000 x_5_4=1.000 x_5_5=19.000 x_6_1=12.000 x_6_2=9.000 x_6_3=5.000 x_6_4=11.000 x_6_5=10.000 x_7_1=5.000 x_7_2=3.000 x_7_3=1.000 x_7_4=19.000 x_7_5=13.895 x_8_1=13.000 x_8_2=17.000 x_8_3=10.000 x_8_4=10.000 x_8_5=4.000 x_9_1=18.000 x_9_2=2.000 x_9_3=5.000 x_9_4=10.000 x_9_5=16.000 x_10_1=19.000 x_10_2=4.000 x_10_3=18.000 x_10_4=10.000 x_10_5=5.000
通过 pandas.DataFrame 显示
# 合并在一起的效果 import pandas as pd # 将 x_var_c 变量加入到 dataframe 里面 opt_df = pd.DataFrame.from_dict(x_vars_c, orient="index", columns = ["variable_object"]) opt_index = pd.MultiIndex.from_tuples(opt_df.index, names=["colums_i", "colums_j"]) # 生成了新的索引 opt_df.reset_index(inplace=True) # CPLEX # variable_object 显示的是 x_1_1,实际上是一个 object,因此可以调用响应的函数 # 对于整个列进行操作 # 获取每个对象的最优结果 opt_df["solution_value"] = opt_df["variable_object"].apply(lambda item: item.solution_value) opt_df.drop(columns=["variable_object"], inplace=True) opt_df.to_csv("./optimazation_solution.csv")
这里,opt_df是一个包含每个决策变量$x_{ij}$的最优值的panda dataframe。我们还可以将这些结果保存到CSV文件中,如上所示。
我们只讨论了Python中的高级建模,但是上面的所有包都包含有用的函数和数据结构,在编写准备生产的代码时应该考虑这些函数和数据结构。例如,在gu中,可以使用opt_model.addVars()一次性添加一组变量,而在CPLEX中是opt_model.continuous_var_dict()、opt_model.binary_var_dict()或opt_model.integer_var_dict(),在PuLP中可以使用plp.LpVariable.dicts()。
7. 代码合并在一起,去掉多余的部分
# 初始化变量的值 import random n = 10 m = 5 set_I = range(1, n+1) set_J = range(1, m+1) # 通过 random 生成随机数,都是以 字典 的形式来生成的,按照公式中需要的数据一一生成 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} # 导入运筹优化库 import docplex.mp.model as cpx opt_model = cpx.Model(name="MIP Model") # 如果 x 是连续的话,按照下面的定义 x_vars = {(i, j): opt_model.continuous_var(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} # 3个constraints,约束条件 for j in set_J: opt_model.add_constraint(ct=opt_model.sum(a[i,j] * x_vars[i,j] for i in set_I) <= b[j]) for i in set_I: for j in set_J: opt_model.add_constraint(ct=x_vars[i,j] >= l[i,j]) opt_model.add_constraint(ct=x_vars[i,j] <= u[i,j]) # 两层循环,然后将所有的数据相加 objective = opt_model.sum(x_vars[i,j] * c[i,j] for i in set_I for j in set_J) # for maximization opt_model.maximize(objective) # solving with local cplex opt_model.solve() # 可以直接打印结果 opt_model.print_solution()