MindOpt--C++语言-对一个简单的混合整数规划问题建模求解

简介: MindOpt是达摩院决策智能实验室研究的一款优化求解器,目前在优化求解线性规划问题这一功能上取得不错的成绩,希望大家能够帮我们多多打磨其他功能(混合整数线性规划、二次规划、半定规划目前都在公测),让我们的MindOpt在优化求解器这板块成为国产之光。

凌波微步是段誉所习得的上乘轻功功法,学习这门上乘轻功有那么一个约束条件,它需要对易经八卦等知识有了解,甚至可以说是精通。混合整数线性规划问题也有那么一点相似,那就是这个线性问题求解的结果需要有一个或者多个变量整数这么一个约束条件。下文我们将会重点讲述如何使用MindOpt C++ 语言的API来建模优化混合整数线性规划。


MindOpt Python、C、C++语言求解LP、MILP、QP问题系列


下载安装

用户可以点这里下载安装MindOpt优化求解器

开通算法服务控制台(免费的)

MindOpt的更多信息官网

数学公式下的混合整数线性规划问题:

image.png

定义

我个人认为混合整数线性规划线性规划的区别在于,线性规划求解目标函数最优值的时候,决策变量是连续的,即可以是整数也可以是小数,但混合整数线性规划可能会有一个或者多个变量必须为整数。

  • 不要小看只是多了一个为整数的约束,它会导致问题在很多时候会有更多的变数,这样计算起来就更加复杂。打一个简单的比喻,女朋友想吃你做的饭,那么你就在网上选菜,她会告诉你想吃什么(玉米啊、排骨啊、豆腐等等),然后给了你一百的资金,就这样你带着这些条件选择各种食材,但发现在一百块的条件下,最后想买点大葱时钱不够了,但大葱不可能切一半给你,这样你就得重新选择其他食材的数量完成订菜。
  • 还有经典的背包问题:桌子上有一组物品,每个物品有自己的价值和重量,但是包的承重是有限的;我们要装什么物品,在包的重量承受范围内,包里总物品的价值最高?这个里面选择那个物品就是个整数,并不能是小数切开,比如一个吹风机不能切开只带一半走。


混合整数线性规划在求解的时候,可以用分支定界法、割平面法等,会切分成子问题调用线性规划(LP)求解模块。MindOpt在今年也发布了混合整数线性规划(MILP)的求解能力。接下来我会举个数学算例如何使用。

数学算例

混合整数线性规划问题示例:

image.png

是不是看着数学算例很抽象?那么我们来举个例子带入:假设工厂有一种原材料,可以生产多种零件毛坯,但每种零件的生产方式也有多种,每种生产零件的方式可以得到不同零件的毛坯数以及每种零件的需要量,但需要其中一种零件生产必需为整数,我们要做的就是用MindOpt来帮助生产工人计算要怎么生产才能达到零件所需要的数量,所花费的原材料又最少。

MindOpt和C++下的建模优化

核心使用的几个APIs是:

MdoModel model;

model.setIntAttr(MDO_INT_ATTR::MIN_SENSE, MDO_YES);

model.addCons(1.0, MDO_INFINITY, 1.0 * x[0] + 1.0 * x[1] + 2.0 * x[2] + 3.0 * x[3], "c0");
model.addCons(1.0, 1.0,          1.0 * x[0]              - 1.0 * x[2] + 6.0 * x[3], "c1");

model.solveProb();
model.displayResults();

下面是完整的例子,可复制存为MdoMiloEx1.cpp文件。

#include <iostream>
#include <vector>
/*引入头文件*/
#include "MindoptCpp.h"

using namespace mindopt;

int main(void)
{
    /*------------------------------------------------------------------*/
    /* Step 1. 创建模型并更改参数。               */
    /*------------------------------------------------------------------*/
    /* 创建一个空模型 */
    MdoModel model;

    try 
        {
            /*------------------------------------------------------------------*/
            /* Step 2. 输入模型。.                                             */
            /*------------------------------------------------------------------*/
            /* 改为最小化问题 */
            /*通过 mindopt::MdoModel::setIntAttr() 将目标函数设置为 最小化*/ 
            model.setIntAttr(MDO_INT_ATTR::MIN_SENSE, MDO_YES);

            /* 添加变量 */
            /*调用 mindopt::MdoModel::addVar() 来添加四个优化变量,定义其下界、上界、名称和类型*/
            std::vector<MdoVar> x;
            x.push_back(model.addVar(0.0, 10.0,         1.0, "x0", MDO_YES));
            x.push_back(model.addVar(0.0, MDO_INFINITY, 1.0, "x1", MDO_YES));
            x.push_back(model.addVar(0.0, MDO_INFINITY, 1.0, "x2", MDO_YES));
            x.push_back(model.addVar(0.0, MDO_INFINITY, 1.0, "x3", MDO_NO));

            /* 添加约束 */
            /*通过 mindopt::MdoModel::addCons()来添加约束*/
            model.addCons(1.0, MDO_INFINITY, 1.0 * x[0] + 1.0 * x[1] + 2.0 * x[2] + 3.0 * x[3], "c0");
            model.addCons(1.0, 1.0,          1.0 * x[0]              - 1.0 * x[2] + 6.0 * x[3], "c1");

            /*------------------------------------------------------------------*/
            /* Step 3. 解决问题并填充结果。              */
            /*------------------------------------------------------------------*/
            /* 调用 mindopt::MdoModel::solveProb() 求解优化问题,
               并通过 mindopt::MdoModel::displayResults() 查看优化结果 */
            model.solveProb();
            model.displayResults();
        }
    catch (MdoException & e)
        {
            std::cerr << "===================================" << std::endl;
            std::cerr << "Error   : code <" << e.getResult() << ">" << std::endl;
            std::cerr << "Reason  : " << model.explainResult(e.getResult()) << std::endl;
            std::cerr << "===================================" << std::endl;

            return static_cast<int>(e.getResult());
        }

    return static_cast<int>(MDO_OKAY);
}

MindOpt求解的结果

运行MdoMiloEx1.cpp文件的步骤

linux和Mac系统在命令行输入以下代码

cd <MDOHOME>/<VERSION>/examples/CPP
make -f Makefile all
./MdoMiloEx1

windows系统本例是在Visual Studio上运行,版本为2019

#运行方式与前文    一致,只需要修改文件就好;把MdoLoEx1.cpp换成MdoMiloEx1.cpp

C++.gif

如上文所述,运行MdoMiloEx1.cpp文件,得到求解的结果如下所示,/**/号里面是我添加的注释。

Model summary.                    /*模型摘要*/
 - Num. variables     : 4
 - Num. constraints   : 2
 - Num. nonzeros      : 7
 - Num. integer vars. : 3
 - Bound range        : [1.0e+00,1.0e+01]限制范围
 - Objective range    : [1.0e+00,1.0e+00]目标范围

Branch-and-cut method started.      /*分支切割方法*/
Model summary.
 - Num. variables     : 4
 - Num. constraints   : 2
 - Num. nonzeros      : 7
 - Bound range        : [1.0e+00,1.0e+01]
 - Objective range    : [1.0e+00,1.0e+00]
 - Matrix range       : [1.0e+00,6.0e+00]

Presolver started.
Presolver terminated. Time : 0.005s

Simplex method started.

    Iteration       Objective       Dual Inf.     Primal Inf.     Time
            0     0.00000e+00      0.0000e+00      1.3102e+00     0.04s
            2     5.55556e-01      0.0000e+00      0.0000e+00     0.06s
Postsolver started.                      /*单纯形法开始*/
Simplex method terminated. Time : 0.051s

            2     5.55556e-01      0.0000e+00      0.0000e+00     0.08s
            2     5.55556e-01      0.0000e+00      0.0000e+00     0.09s
            2     5.55556e-01      0.0000e+00      0.0000e+00     0.10s
            2     5.55556e-01      0.0000e+00      0.0000e+00     0.11s
            0     5.55556e-01      0.0000e+00      0.0000e+00     0.12s
            0     5.55556e-01      0.0000e+00      0.0000e+00     0.14s
            0     5.55556e-01      0.0000e+00      0.0000e+00     0.14s
            0     5.55556e-01      0.0000e+00      0.0000e+00     0.15s
            0     5.55556e-01      0.0000e+00      0.0000e+00     0.17s
            0     5.55556e-01      0.0000e+00      0.0000e+00     0.18s
            0     5.55556e-01      0.0000e+00      0.0000e+00     0.18s
            0     5.55556e-01      0.0000e+00      0.0000e+00     0.19s
            0     5.55556e-01      0.0000e+00      0.0000e+00     0.20s
            0     5.55556e-01      0.0000e+00      0.0000e+00     0.21s
            0     5.55556e-01      0.0000e+00      0.0000e+00     0.22s
            0     5.55556e-01      0.0000e+00      0.0000e+00     0.22s
            0     5.55556e-01      0.0000e+00      0.0000e+00     0.23s
            0     5.55556e-01      0.0000e+00      0.0000e+00     0.25s
            0     5.55556e-01      0.0000e+00      0.0000e+00     0.25s
            0     5.55556e-01      0.0000e+00      0.0000e+00     0.26s
Branch-and-cut method terminated. Time : 0.567s

Optimizer summary.
 - Optimizer used     : Branch-and-cut method   /*显示最终使用分支切割方法*/
 - Optimizer status   : OPTIMAL
 - Total time         : 0.624s

Solution summary.       Primal solution
 - Objective          : 1.0000000000e+00    /*目标函数最优解*/

联系我们

钉钉:damodi

邮箱地址:solver.damo@list.alibaba-inc.com


相关文章
|
达摩院 Linux API
阿里达摩院MindOpt求解器V1.1新增C#接口
阿里达摩院MindOpt求解器发布最新版本V1.1,增加了C#相关API和文档。优化求解器产品是求解优化问题的专业计算软件,可广泛各个行业。阿里达摩院从2019年投入自研MindOpt优化求解器,截止目前经历27个版本的迭代,取得了多项国内和国际第一的成绩。就在上个月,2023年12月,在工信部产业发展促进中心等单位主办的首届能源电子产业创新大赛上,MindOpt获得电力用国产求解器第一名。本文将为C#开发者讲述如何下载安装MindOpt和C#案例源代码。
455 3
阿里达摩院MindOpt求解器V1.1新增C#接口
|
算法 安全 机器人
Python语言如何使用MindOpt建模并求解二次规划问题
MindOpt是一款高效的优化算法软件包,求解算法实现了线性规划(LP)、混合整数线性规划(MILP)、二次规划(QP),可以支持命令行、c、c++、java和python调用。接下来我们将发布一系列文章,讲述各个语言如何使用 MindOpt 来求解数学规划问题。
Python语言如何使用MindOpt建模并求解二次规划问题
MindOpt APL 达摩院自己的建模语言!
MindOpt建模语言(MindOpt Algebraic Programming Language, MindOpt APL, 简称为MAPL)是MindOpt团队研发的一种代数建模语言。相比与其他的语言,MAPL语法相对较少且自然,很贴近数学语言。用MAPL描述数学规划模型与用数学公式进行描述非常类似。
MindOpt APL 达摩院自己的建模语言!
|
机器学习/深度学习 达摩院
阿里达摩院MindOpt优化求解器-月刊(2024年4月)
【摘要】2024.04.30,阿里云发布了MindOpt优化求解器的新商品和功能。MindOpt现在已上架,提供超低价零售求解器,支持按需购买,可在阿里云平台上直接购买联网或不联网License。新版本V1.2发布,提升MILP性能,并增加PostScaling参数。此外,MindOpt Studio推出租户定制版,正处于邀测阶段。同时分享了使用MindOpt解决二分类SVM问题的案例。更多内容,可访问相关链接。
367 0
|
达摩院 IDE 开发工具
阿里达摩院MindOpt优化求解器-月刊(2024年5月)
阿里达摩院MindOpt优化求解器-月刊(2024年5月版),新增了两个案例,如何使用LLM和MindOpt更准确地回答数学问题、如何使用MindOpt优化云计算集群虚拟机资源配置提高机器利用率,和如何利用IIS冲突分析指导不可解的问题解决方案。MindOpt的求解器已经可以在阿里云线上购买不联网版本。租户版也正式上线,可体验更多功能。新增QQ交流群。
265 4
|
达摩院 算法 Java
选择优化求解器的关键因素:以MindOpt为例
选择一款适合自己业务需求的求解器我们一般需要考量什么呢?可求解的问题类型?问题规模?本文将介绍一些需要考虑的重要因素,并且介绍阿里达摩院MindOpt优化求解器在这些因素下的表现。
|
达摩院 Python
阿里达摩院MindOpt优化求解器-月刊(2024年6月)
**阿里达摩院MindOpt优化求解器2024年6月月刊概览:** - 发布新功能,MAPL建模语言V2.5上线,Python APIs全面升级,旧版本不兼容。 提供快速入门教程、示例代码展示如何用Python调用MAPL。MindOpt Studio租户版新增Gradio支持,便于开发WebAPP,提供了案例源码展示如何开发。引入新案例: 1. 巡检线路的排班-2017全国大学生数学建模竞赛D题。包含最短路模型、TSP模型、弧分割模型。2. 商品组合定价策略:探讨如何最赚钱的加购区商品定价。
222 0
|
算法 Java 数据处理
了解MindOpt优化求解器的各种调用方式、方法
Mindopt是一款高性能优化求解器,专为求解大规模数学规划问题,当前支持线性规划 (LP) 、混合整数线性规划 (MILP) 、非线性规划(QP、SDP)。其强大的算法旨在有效地找到符合规规则约束、目标值最优的最佳解决方案,使其成为运筹学必学工具,广泛用在电商互联网、金融、电力能源、工业制造、交通物流等领域。
|
达摩院 API C语言
C语言如何使用MindOpt建模并求解混合整数线性规划问题
MindOpt是达摩院决策智能实验室研究的一款优化求解器,能帮助做方案设计、生产方案优化、资源合理分配、辅助决策等。可以支持命令行、c、c++、java和python调用,目前求解算法实现了线性规划、混合整数线性规划、二次规划。
C语言如何使用MindOpt建模并求解混合整数线性规划问题
|
机器学习/深度学习 人工智能 达摩院
MindOpt工具是如何做到配套使用的?请看此篇
MindOpt是阿里巴巴达摩院决策职能实验室研发的专注于优化领域,提供智能优化解决方案的品牌。主要的目标是帮助客户通过先进的优化算法和技术,实现业务流程的最佳化,提升效率,降低成本,并最大化业务价值。