富联新闻
News
开源运筹学优化工具包或开源代码有什么可以推荐的吗?
目前在新三板上市的智慧物业公司实习,虽然求职时面试图像算法岗位,但目前公司图像算法需求没那么急,目前被分配到新零售部做外卖配送算法,没有任何经验。现在状态是初始的运筹学模型建立出来了,但如同Gurobi,CPlex等付费工具包公司没有经费购买,需要自己重头编写代码或者找开源代码,各位运筹学大佬有什么建议,需要如何入手?
Python中有很多优秀的运筹学和优化库,包括以下几个:
- PuLP:线性规划库,使用Python语言编写,简单易用。
- CVXPY:使用Python进行凸优化,可用于线性和非线性规划,半正定规划等问题。
- scipy.optimize:SciPy中的优化模块,包括线性规划和非线性规划等算法。
- Gurobi:商用优化软件,提供Python API。
- Pyomo:Python建模语言,可用于线性规划,非线性规划,混合整数规划等问题。
- OR-Tools:Google出品的优化库,可用于线性规划、约束优化、车辆路径规划等问题。
- Optuna:用于超参数优化的库,可用于自动化机器学习和深度学习模型调参。
- PySCIPOpt:Python界面的SCIP优化器,可用于混合整数规划、二次规划等问题。
- DEAP:进化算法库,可用于优化问题,如遗传算法、粒子群算法等。
- Platypus:Python框架,用于多目标优化问题,可用于遗传算法、NSGA-II等。
- CPLEX:商用优化软件,提供Python API,可用于线性规划、混合整数规划等问题。。
- MOSEK:商用优化软件,可用于线性规划、二次规划、混合整数规划等问题。
- SCIP:可用于解决线性规划、混合整数规划等问题。
1.对于外卖配送业务,可以多关注下美团公布的技术方案https://me.mbd.baidu.com/r/YjV2ZyPi3m?f=cp&u=1455d12ce01f6ac5
2.路线规划是配送业务的核心模块之一(我猜你应该是对这块进行了数学建模?)。对于这个模块,不推荐使用精确求解的方式去做(因为当问题规模大了后常规时间内算不出较优解)。比较合适的方案是用启发式算法:
1)如果你的路径规划问题可以抽象成标准的vrp问题,那么可以使用or-tools、jsprit等开源求解器;
2)如果约束、目标、场景比较复杂时,建议考虑使用禁忌搜索、遗传算法、模拟退火、大规模邻域搜索等算法(相应的开源项目有scikit-opt等)
运筹商用求解器是一种用于解决运筹学和优化问题的软件工具。这些求解器被广泛应用于各种领域,包括物流管理、生产计划、资源分配、交通规划、金融建模等等。它们可以帮助用户找到问题的最佳解决方案,通常是在满足一系列约束条件的情况下最大化或最小化某个目标函数。
以下是一些常见的商用运筹求解器:
IBM CPLEX: CPLEX是一种高度优化的求解器,用于线性规划、整数规划、混合整数规划、二次规划等问题。它被广泛用于供应链管理和生产计划等领域。
Gurobi: Gurobi是另一个用于线性规划、整数规划和混合整数规划的强大求解器。它具有高性能和用户友好的界面,适用于各种应用领域。
Microsoft Solver Foundation: 这是微软的一个优化框架,可以用于解决各种优化问题,包括线性规划、非线性规划、整数规划等。
FICO Xpress: Xpress是一款多用途求解器,支持线性规划、整数规划、混合整数规划、二次规划、非线性规划等各种问题。
LINDO/LINDO API: LINDO是一个用于线性和非线性规划的求解器,它还提供了LINDO API,可以集成到自定义应用程序中。
MOSEK: MOSEK是一个用于线性、二次和混合整数规划的求解器,重点是高性能和可扩展性。
AMPL: AMPL是一个建模语言,可以与多个求解器集成,包括上述提到的一些。它允许用户使用自己的模型来解决优化问题。
运筹学开源求解器是免费提供的软件工具,用于解决各种运筹学和优化问题。这些求解器通常是由社区驱动的项目,具有广泛的用户支持和开发者社区。以下是一些常见的开源运筹学求解器:
PuLP: PuLP是一个Python库,用于线性规划、整数规划和混合整数规划。它提供了一个易于使用的建模语言,可以与多个商业和开源求解器集成。
GLPK (GNU Linear Programming Kit): GLPK是一个用于线性和整数规划的免费求解器,是GNU项目的一部分。它提供了一个命令行界面和多种编程语言的接口。
COIN-OR: COIN-OR是一个包含多个优化工具和库的开源项目。其中包括Cbc(整数规划求解器)、Clp(线性规划求解器)和Ipopt(非线性规划求解器)等。
SCIP (Solving Constraint Integer Programs): SCIP是一个用于整数规划和混合整数规划的高性能求解器。它提供了一个灵活的插件架构,可以用于解决各种组合优化问题。
SymPy: SymPy是一个Python库,用于符号计算,包括代数方程和微积分问题。虽然它不是专门用于数学规划的求解器,但它可以用于分析和符号求解优化问题的数学模型。
OptaPlanner: OptaPlanner是一个Java库,用于解决排程和规划问题。它广泛用于任务分配、员工排班、资源分配等领域。
这些开源求解器提供了一个低成本或免费的选项,可用于解决各种规模的优化问题。选择哪个求解器取决于您的编程语言偏好、问题类型和性能需求。许多商业应用程序和研究项目也使用开源求解器作为其优化引擎的一部分。
Python有多个运筹学求解器可供选择,这些求解器提供了丰富的优化工具和库,可以用于解决各种优化问题。以下是适用于Python的一些常见运筹学求解器:
- PuLP: PuLP是一个流行的Python库,用于线性规划、整数规划和混合整数规划。它提供了一个易于使用的建模语言,可以与多个商业和开源求解器集成,包括CBC、GLPK、CPLEX和Gurobi等。
- Pyomo: Pyomo是一个Python建模和优化工具包,支持线性规划、整数规划、混合整数规划、非线性规划等。它具有灵活性,可以与多个求解器集成,包括商业和开源求解器。
- SciPy.optimize: SciPy是Python的科学计算库,其中包含了一些用于优化的模块,例如
scipy.optimize.linprog
用于线性规划,scipy.optimize.minimize
用于非线性规划。虽然不如专门的求解器强大,但对于一些简单的问题来说足够了。 - CVXPY: CVXPY是一个Python库,用于凸优化问题的建模和求解。它专注于凸优化,可以处理线性规划、二次规划、半正定规划等问题。
- Optuna: Optuna是一个用于超参数优化的Python库,可以用于优化机器学习模型的参数。它基于贝叶斯优化算法,适用于黑盒优化问题。
- Gekko: Gekko是一个用于动态优化和非线性模型预测控制的Python库。它可以处理动态系统建模和多变量非线性优化问题。
- SymPy: SymPy是一个Python库,用于符号计算,可用于代数方程和微积分问题。虽然不是专门的优化库,但可以用于分析和符号求解优化问题的数学模型。
- DEAP: DEAP是一个用于进化算法的Python库,适用于解决复杂的优化问题,例如遗传算法和进化策略。
这些库提供了不同类型和复杂度的优化工具,可以根据您的需求选择合适的工具。如果需要处理大规模问题或需要高性能的求解器,您可能还需要考虑与商业求解器(如CPLEX、Gurobi)的集成,这些求解器通常提供更快速和高效的解决方案。
CPLEX和Gurobi都是领先的商业数学优化求解器,它们被广泛用于解决线性规划、整数规划、混合整数规划、二次规划等各种优化问题。以下是它们的一些对比方面:
性能:CPLEX 和 Gurobi 都以高性能而闻名,通常能够处理大规模和复杂的优化问题。它们都针对多核处理器进行了优化,以提供快速的求解能力。对于某些问题,性能优劣可能会有所不同,具体取决于问题的特性以及如何配置和调整求解器参数。在某些情况下,Gurobi在性能方面稍微领先。
用户界面:CPLEX和Gurobi都提供了用户友好的界面,可以通过命令行、Python、MATLAB等多种方式与其交互。Gurobi在Python中的接口被广泛认为更加灵活和容易使用,这在Python生态系统中特别有吸引力。
许可费用:许可费用是选择求解器时需要考虑的一个因素。通常情况下,Gurobi的许可费用较低,这对于小型团队和个人研究者来说可能更加经济实惠。CPLEX的许可费用通常较高,但IBM也提供了学术和研究许可,使其在教育和研究领域更具吸引力。
支持和文档:CPLEX和Gurobi都有强大的用户支持和文档。它们提供了丰富的文档、示例和论坛,以帮助用户解决问题和优化建模。
平台支持:两者都支持多个操作系统,包括Windows、Linux和macOS。Gurobi还支持一些其他平台,如Raspberry Pi。
功能和扩展性:两者都支持多种优化问题类型,包括线性规划、整数规划、混合整数规划、二次规划等。Gurobi在某些方面具有更多的高级功能,如优化嵌套子问题、并行求解等。
选择? 使用CPLEX还是Gurobi通常取决于您的具体需求、预算以及与特定求解器的经验。对于大多数用户来说,两者都是强大的工具,可以解决各种优化问题,而且它们之间的性能差异通常不太明显。如果您更关注性能和Python集成,可以考虑使用Gurobi。如果您在教育或研究领域工作,可以考虑使用CPLEX的学术许可。
要在Python中集成Gurobi求解器,您需要按照以下步骤操作:
安装Gurobi Python接口:
首先,确保您已经安装了Gurobi求解器,并且已经获得了有效的Gurobi许可证。然后,安装Gurobi的Python接口,您可以使用pip执行以下命令:pip install gurobipy
导入Gurobi模块:
在Python脚本或Jupyter Notebook中导入Gurobi模块:import gurobipy as gp
创建优化模型:
创建一个Gurobi优化模型对象,然后可以向该模型添加变量、约束和目标函数。例如:# 创建一个模型对象 model=gp.Model("MyModel") # 添加变量 x=model.addVar(vtype=gp.GRB.CONTINUOUS, name="x") y=model.addVar(vtype=gp.GRB.CONTINUOUS, name="y") # 设置目标函数 model.setObjective(2 * x + y, sense=gp.GRB.MAXIMIZE) # 添加约束 model.addConstr(x + 2 * y <=4, name="c1") model.addConstr(x - y <=1, name="c2")
求解优化问题:
使用Gurobi的optimize()
方法来求解优化问题:
pythonCopy codemodel.optimize()
获取结果:
您可以获取最优解、目标函数值等信息:
pythonCopy codeif model.status==gp.GRB.OPTIMAL: print("最优解:") print(f"x={x.x}") print(f"y={y.x}") print(f"目标函数值={model.objVal}") else: print("未找到最优解")
目标最小化 ?
满足 和 约束
#include <iostream>
#include <cppad/ipopt/solve.hpp>
using namespace std;
namespace{
using CppAD::AD;
class FG_eval{
public:
typedef CPPAD_TESTVECTOR(AD<double>) ADvector;
void operator()(ADvector& fg, const ADvector& x)
{
assert(fg.size()==3);
assert(x.size()==2);
// 目标函数
fg[0]=2 * x[0]+ 3 * x[1];
// 约束条件
fg[1]=x[0]+ x[1]- 3.0;
fg[2]=2.0 * x[0]- x[1]- 4.0;
return;
}
};
}
int main()
{
cout << "Linear Programming Example" << endl;
bool ok=true;
size_t i;
typedef CPPAD_TESTVECTOR(double) Dvector;
size_t nx=2; // 决策变量的数量
size_t ng=2; // 约束条件的数量
Dvector x0(nx); // 决策变量的初始条件
x0[0]=1.0;
x0[1]=1.0;
// 决策变量的上下界
Dvector xl(nx), xu(nx);
for(i=0; i < nx; i++)
{
xl[i]=0.0; // x_i >=0
xu[i]=1e19; // 无上界
}
Dvector gl(ng), gu(ng);
gl[0]=3.0; gu[0]=1e19; // x1 + x2 >=3
gl[1]=-1e19; gu[1]=4.0; // 2x1 - x2 <=4
// 求解器需要一个评估目标函数和约束的对象
FG_eval fg_eval;
// 选项
string options;
options +="Integer print_level 0\
";
options +="String sb yes\
";
options +="Integer max_iter 10\
";
options +="Numeric tol 1e-6\
";
options +="String derivative_test second-order\
";
options +="Numeric point_perturbation_radius 0.\
";
// 存储最终解的对象
CppAD::ipopt::solve_result<Dvector> solution;
// 使用Ipopt求解器
CppAD::ipopt::solve<Dvector, FG_eval>(options, x0, xl, xu, gl, gu, fg_eval, solution);
// 输出最优解
cout << "Optimal objective value: " << solution.obj_value << endl;
cout << "Optimal decision variables: ";
for (size_t i=0; i < nx; ++i){
cout << solution.x[i]<< " ";
}
cout << endl;
return 0;
}
头文件,用于使用 CppAD 和 Ipopt 库
#include <cppad/ipopt/solve.hpp>
定义仿函数,用于计算目标函数和约束
namespace{//这里的 namespace 用于限定 FG_eval 类的作用域。
using CppAD::AD;
class FG_eval{
public:
//CPPAD_TESTVECTOR 是 CppAD 中定义的一个宏,用于创建 AD 向量。
typedef CPPAD_TESTVECTOR(AD<double>) ADvector;
//operator() 函数实现了仿函数的功能,计算目标函数和约束。在这里,目标函数和约束的数量都是 3 个。
void operator()(ADvector& fg, const ADvector& x)
{
//assert 语句用于确保 fg 向量和 x 向量的大小分别为 3 和 4。
assert(fg.size()==3);
assert(x.size()==4);
//将决策变量从 x 向量中提取出来,分别赋值给 x1、x2、x3 和 x4
AD<double> x1=x[0];
AD<double> x2=x[1];
AD<double> x3=x[2];
AD<double> x4=x[3];
// f(x) 目标函数
fg[0]=x1 * x4 * (x1 + x2 + x3) + x3;
// 约束
fg[1]=x1 * x2 * x3 * x4;
fg[2]=x1 * x1 + x2 * x2 + x3 * x3 + x4 * x4;
return;
}
};
描述问题与求解
get_started
函数是程序的入口。它初始化了问题的参数,包括变量的数量(nx
),约束的数量(ng
),以及初始条件(x0
向量)。
bool get_started(void)
{
bool ok=true;
size_t i;
typedef CPPAD_TESTVECTOR(double) Dvector;
size_t nx=4; // 决策变量个数
size_t ng=2; // 决策约束个数
Dvector x0(nx); // 变量初始值
x0[0]=1.0;
x0[1]=5.0;
x0[2]=5.0;
x0[3]=1.0;
// 决策变量界限设置
Dvector xl(nx), xu(nx);
for(i=0; i < nx; i++)
{
xl[i]=1.0;
xu[i]=5.0;
}
Dvector gl(ng), gu(ng);
gl[0]=25.0; gu[0]=1.0e19;
gl[1]=40.0; gu[1]=40.0;//等式约束描述为等式约束
FG_eval fg_eval;//创建了 FG_eval 类的实例,用于计算目标函数和约束
string options; // 字符串,用于存储 Ipopt 求解器的选项。
//设置打印级别,0 表示关闭所有打印输出。在求解器运行时,
//它会输出一些信息,例如每次迭代的结果等。通过将打印级别设置为 0,可以减少冗余的输出信息。
options +="Integer print_level 0\
";
options +="String sb yes\
";
// 设置最大迭代次数为 10。这是一个控制求解器运行时间的参数。
//如果求解器达到了最大迭代次数而没有找到满足收敛标准的解,求解器将提前退出。
options +="Integer max_iter 10\
";
//设置收敛容许误差。这个参数控制求解器停止迭代的条件,
//当当前迭代的优化进度足够小(小于 tol)时,求解器将停止运行。
options +="Numeric tol 1e-6\
";
options +="String derivative_test second-order\
";
//置数值微分的随机扰动半径。在进行数值微分时,为了计算梯度和黑塞矩阵,
//可能会对变量进行小幅度的扰动。这个选项设置了扰动的最大半径。将其设置为 0 表示关闭数值微分。
options +="Numeric point_perturbation_radius 0.\
";
CppAD::ipopt::solve_result<Dvector> solution; // 将结果存储在 solution
CppAD::ipopt::solve<Dvector, FG_eval>(options, x0, xl, xu, gl, gu, fg_eval, solution); // 求解问题
cout<<"solution: "<<solution.x<<endl;
//进行最优解的检查,确保求解器成功并且最优解在预期范围内。
//CppAD::ipopt::solve_result<Dvector>::success 表示求解器成功找到了解。
ok &=solution.status==CppAD::ipopt::solve_result<Dvector>::success;
double check_x[]={1.000000, 4.743000, 3.82115, 1.379408};//预期的最优解。这是在已知问题的情况下提前计算的一个参考解。
double check_zl[]={1.087871, 0., 0., 0. };
double check_zu[]={0., 0., 0., 0. };
//相对容差和绝对容差。在进行近似相等性比较时,通常会使用相对容差和绝对容差。这两个参数用于定义两个值在多大程度上被认为是相等的。
double rel_tol=1e-6; // relative tolerance
double abs_tol=1e-6; // absolute tolerance
//对最优解的逐个分量进行检查。使用 CppAD::NearEqual 函数进行比较,
//如果解与预期解在相对容差和绝对容差内足够接近,则 ok 变量会保持为 true,否则为 false。
for(i=0; i < nx; i++)
{
ok &=CppAD::NearEqual(
check_x[i], solution.x[i], rel_tol, abs_tol);
ok &=CppAD::NearEqual(
check_zl[i], solution.zl[i], rel_tol, abs_tol);
ok &=CppAD::NearEqual(
check_zu[i], solution.zu[i], rel_tol, abs_tol);
}
return ok;
}
求解
int main()
{
cout << "CppAD : Hello World Demo!" << endl;
get_started();
return 0;
}
CMakeLists里面的配置,linear_opti是cpp文件的名称
add_executable(opti
src/opti.cpp
)
target_link_libraries(opti
${catkin_LIBRARIES}
${OCTOMAP_INCLUDE_DIRS}
${SIPP_LINK_LIBS}
${PYTHON_LIBRARIES}
m
ipopt
}
3