使用COPT求解混合整数线性规划-Toy模板网

这篇具有很好参考价值的文章主要介绍了使用COPT求解混合整数线性规划。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

一、使用Copt求解模型步骤

1.模型的引入

使用 from copt import * 引入模型

import coptpy as cp

2.创建求解环境

env = Envr()

创建优化模型，返回一个Model对象

mdl=env.ccreateModel("name")

3.添加决策变量

添加一个决策变量：mdl.addVar(lb=0.0, ub=COPT.INFINITY, obj=0.0, vtype=COPT.CONTINUOUS, name="", column=None)

Lb：

变量的下界。可选参量，默认为0.0。

Ub：

变量的上界。可选参量，默认为 COPT.INFINITY 。

Obj：

变量的目标函数系数。可选参量，默认为0.0。

Vtype：

变量类型。可选参量，默认为 COPT.CONTINUOUS ，可取值详见变量类型。

决策变量的类型用vtype决定。

COPT.CONTINUOUS（连续变量）

COPT.BINARY（二进制变量）

COPT.INTEGER(整数变量)

Name：

变量的名字。可选参量，默认为 "" ，由求解器内部自动生成。

Column：

变量对应的列。可选参量，默认为 None 。

添加一组变量到模型中。并返回一个tupledic类对象。 mdl.addVars(*indices, lb=0.0, ub=COPT.INFINITY, obj=0.0, vtype=COPT.CONTINUOUS, nameprefix="C")

*indices

变量的下标。

变量的下界。可选参量，默认为0.0。

变量的上界。可选参量，默认为 COPT.INFINITY 。

obj

变量的目标函数系数。可选参量，默认为0.0。

vtype

变量的类型。可选参量，默认为 COPT.CONTINUOUS ，可取值详见变量类型。

nameprefix

变量的名称前缀。可选参量，默认为 "C"，其实际名称结合变量的下标自动生成。

例：

添加一组下标为i,j,k,n，名称为c的二进制变量

arcosC = tuplelist([(i, j, k, n) for i in P_0 for j in P_0 for k in K for n in N])

c = mdl.addVars(arcosC,vtype=COPT.BINARY,nameprefix='C')

4.添加目标函数

mdl.setObjective(expr, sense=None)

expr

目标函数的表达式。可取值为常数、Var类对象、 LinExpr类对象和 QuadExpr类对象。

sense

目标函数的优化方向。可选参量，默认为 None ，表示不改动模型的优化方向。模型的当前优化方向通过属性 ObjSense 查看。

sense=COPT.MAXIMIZE(优化方向为最大化)

sense= COPT.MINIMIZE(优化方向为最小化)

例：

添加式子为：minZ=e+i,s,jyijs ∀k∈K,n∈N 混合整数线性规划模型,算法,python 的目标函数

TK = e + cp.quicksum(y[i, j, s] for i in P_1 for j in P_1 for s in S)

mdl.setObjective(TK,COPT.MINIMIZE)

5.添加约束条件

mdl.addConstr(lhs, sense=None, rhs=None, name="")添加一个线性约束

lhs

线性约束的左端项或约束构建器。

sense

线性约束的类型。可选参量，默认为 None 。

约束类型判断线性约束左边与右边的关系

约束类型为等于

Sense=COPT.EQUAL

约束类型为小于等于

Sense=COPT.LESS_EQUAL

rhs

线性约束的右端项。可选参量，默认为 None 。可取值为常数、 Var类对象或 LinExpr类对象。

name

线性约束的名称。可选参量，默认为 ""，由求解器内部自动生成。

mdl.addConstrs(generator, nameprefix="C") 添加一组线性约束

generator

整数或表达式生成器。

Nameprefix

线性约束的名称前缀。可选参量，默认为 "C"，其实际名称结合线性约束的下标自动生成。

例：添加式为：{i∈P0}cijkn+{i∈P1, s∈S}aisjkn≤{i∈P1, s∈S,j∈P0}aisjkn , ∀ j∈P0, k∈K,n∈N 混合整数线性规划模型,算法,python 的约束条件。

mdl.addConstrs(cp.quicksum(c[i, j, k, n] for i in P_0 ) +cp.quicksum(a[i, j, s, k, n] for i in P_1 for s in S ) <=cp.quicksum(a[i, j, s, k, n] for i in P_1 for s in S for j in P_0 ) for j in P_0 for k in K for n in N)

cp.quicksum(data) 描述:快速构建表达式，返回一个 LinExpr类对象。

生成表达式待加

6.求解

求解时间限制：

mdl.param.timelimit = time

求解

mdl.solve()

二、使用python求解一个混合整数线性规划模型代码实例

n=10 # 设置航点数为10

flypoint=[x for x in range(2,n+2)] #除起点外需要被旅行的航点数
point=[0]+[1]+flypoint
startpoint=[0]+[1] #有两个航点是起点

import numpy as np
rnd=np.random
rnd.seed(0)

rnd.seed(0)
loc_x=rnd.rand(len(point))*200 #随机生成航点的横坐标
loc_y=rnd.rand(len(point))*100 #随机生成航点的纵坐标


arcos={(i,j) for i in point for j in point if i!=j} #表示旅行者从航点i到航点j
distancia={(i,j):np.hypot(loc_x[i]-loc_x[j],loc_y[i]-loc_y[j])
           for i in point for j in point if i!=j}  #计算航点之间的距离

import coptpy as cp
from coptpy import *

# Create COPT environment
env = Envr()

# create model
mdl = env.createModel("MIP example")


x=mdl.addVars(arcos,vtype=COPT.BINARY,nameprefix='x') #一个名为x的二元变量
s=mdl.addVars(flypoint,vtype=COPT.CONTINUOUS,nameprefix='s') #一个名为s的连续变量

mdl.setObjective(cp.quicksum(x[i,j]*distancia[i,j] for i,j in arcos),COPT.MINIMIZE) #目标函数，最小化旅行距离
obj=mdl.getObjective()
print(obj)


#约束条件
mdl.addConstrs(cp.quicksum(x[i,j] for j in flypoint if (i,j) in x.keys() )==1 for i in startpoint)
mdl.addConstrs(cp.quicksum(x[i,j] for i in flypoint if (i,j) in x.keys() )==1 for j in startpoint)
mdl.addConstrs(cp.quicksum(x[i,j] for i in point if (i,j) in x.keys() )==1 for j in flypoint)
mdl.addConstrs(cp.quicksum(x[j,i] for i in point if (j,i) in x.keys() )==1 for j in flypoint)
mdl.addConstrs(s[i]-(n+1)*x[i,j] >=s[j]-n for i in flypoint for j in flypoint  if (i,j) in x.keys())

mdl.param.timelimit = 60
mdl.solve()