AI 助理
备案控制台
开发者社区 达摩院 MindOpt 优化 文章 正文

C语言如何使用MindOpt建模并求解混合整数线性规划问题

2022-12-09 732
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： MindOpt是达摩院决策智能实验室研究的一款优化求解器，能帮助做方案设计、生产方案优化、资源合理分配、辅助决策等。可以支持命令行、c、c++、java和python调用，目前求解算法实现了线性规划、混合整数线性规划、二次规划。

下文我们将讲述小编对线性规划的理解以及展示两个算例，和使用 MindOpt C 语言的 API 来建模以及求解 混合整数线性规划示例 中的问题。

(混合整数线性规划定义、算数例题都是与前文python语言的混合整数线性规划问题是一致的，已经阅读了前文可以忽略，直接点击目录进阶算例阅读建模优化代码。)


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

下载安装

用户可以点这里下载安装MindOpt优化求解器，免费的。找不到安装步骤点这里。

(官网https://opt.aliyun.com有更多信息等着您哟!)

混合整数线性规划

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

比如经典的背包问题：桌子上有一组物品，每个物品有自己的价值和重量，但是包的承重是有限的；我们要装什么物品，在包的重量承受范围内，包里总物品的价值最高？这个里面选择那个物品就是个整数，并不能是小数切开，比如一个吹风机不能切开只带一半走。

数学形式下的混合整数线性规划问题：

image.png

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


案例

和上篇 线性规划 一样，我们对于混合线性规划问题示例 做一个假设，把它当作一个生活中实际的例子，而不是数学公式这么抽象。

假设工厂有一种原材料，可以生产多种零件毛坯，但每种零件的生产方式也有多种，每种生产零件的方式可以得到不同零件的毛坯数以及每种零件的需要量，但需要其中一种零件生产必需为整数，那么要怎么生产才能达到零件所需要的数量，所花费的原材料又最少。

image.png

数学算例

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

image.png

C语言+MindOpt代码实现

核心使用的几个APIs是：

MDO_CHECK_CALL(Mdo_createMdl(&model))

MDO_CHECK_CALL(Mdo_setIntAttr(model, MDO_INT_ATTR_MIN_SENSE, MDO_YES))

MDO_CHECK_CALL(Mdo_addRow(model, 1.0, MDO_INFINITY, 4, row1_idx, row1_val, "c0"));
MDO_CHECK_CALL(Mdo_addRow(model, 1.0, 1.0,          3, row2_idx, row2_val, "c1"));

MDO_CHECK_CALL(Mdo_solveProb(model));
Mdo_displayResults(model);

#关于更多API的详细使用方式，请参考 C 接口函数

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

#include <stdio.h>
/*引入头文件*/
#include "Mindopt.h"

/* 检查返回码的宏 */
#define MDO_CHECK_CALL(MDO_CALL)                                    \
code = MDO_CALL;                                                \
if (code != MDO_OKAY)                                           \
{                                                               \
Mdo_explainResult(model, code, str);                        \
Mdo_freeMdl(&model);                                        \
fprintf(stderr, "===================================\n");   \
fprintf(stderr, "Error   : code <%d>\n", code);             \
fprintf(stderr, "Reason  : %s\n", str);                     \
fprintf(stderr, "===================================\n");   \
return (int)code;                                           \
}

int main(void)
{
    /* 变量 */
    char str[1024] = { "\0" };
    MdoMdl * model = NULL;
    MdoResult code = MDO_OKAY;
    MdoStatus status = MDO_UNKNOWN;

    const int    row1_idx[] = { 0,   1,   2,   3   };
    const double row1_val[] = { 1.0, 1.0, 2.0, 3.0 };
    const int    row2_idx[] = { 0,    2,   3   };
    const double row2_val[] = { 1.0, -1.0, 6.0 };

    /*------------------------------------------------------------------*/
    /* Step 1. 创建模型并更改参数。               */
    /*------------------------------------------------------------------*/
    /* 创建一个空模型。 */
    MDO_CHECK_CALL(Mdo_createMdl(&model));

    /*------------------------------------------------------------------*/
    /* Step 2. 输入模型。                                             */
    /*------------------------------------------------------------------*/
    /* 改成最小化问题。 */
    /*通过 Mdo_setIntAttr() 将目标函数设置为 最小化 */
    MDO_CHECK_CALL(Mdo_setIntAttr(model, MDO_INT_ATTR_MIN_SENSE, MDO_YES));

    /* 添加变量。 */
    /*调用 Mdo_addCol() 来添加四个优化变量，定义其下界、上界、名称和类型*/
    MDO_CHECK_CALL(Mdo_addCol(model, 0.0, 10.0,         1.0, 0, NULL, NULL, "x0", MDO_YES));
    MDO_CHECK_CALL(Mdo_addCol(model, 0.0, MDO_INFINITY, 1.0, 0, NULL, NULL, "x1", MDO_YES));
    MDO_CHECK_CALL(Mdo_addCol(model, 0.0, MDO_INFINITY, 1.0, 0, NULL, NULL, "x2", MDO_YES));
    MDO_CHECK_CALL(Mdo_addCol(model, 0.0, MDO_INFINITY, 1.0, 0, NULL, NULL, "x3", MDO_NO));

    /* 添加约束。
     * 请注意，这里的非零元素是按行顺序输入的。
     *调用 Mdo_addRow() 来输入约束
*/
    MDO_CHECK_CALL(Mdo_addRow(model, 1.0, MDO_INFINITY, 4, row1_idx, row1_val, "c0"));
    MDO_CHECK_CALL(Mdo_addRow(model, 1.0, 1.0,          3, row2_idx, row2_val, "c1"));

    /*------------------------------------------------------------------*/
    /* Step 3. 解决问题并填充结果。               */
    /*------------------------------------------------------------------*/
    /* 调用 Mdo_solveProb() 求解优化问题，并通过 Mdo_displayResults() 查看优化结果 */
    MDO_CHECK_CALL(Mdo_solveProb(model));
    Mdo_displayResults(model);

    /*------------------------------------------------------------------*/
    /* Step 4. 释放模型。                                          */
    /*------------------------------------------------------------------*/
    /* 调用 Mdo_freeMdl() 来释放内存 */
    Mdo_freeMdl(&model);

    return (int)code;
}

MindOpt求解的结果

如何编译及运行MdoMiloEx1.c文件

#运行方式与前文线性规划一致，只需要修改文件就好；把MdoLoEx1.c换成MdoMiloEx1.c

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

c语言 windows系统运行mindopt.gif 

/*linux和mac系统直接在命令行输入*/

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

然后运行MdoMiloEx1.c 文件后，得到求解的结果如下所示，/**/号里面是我添加的注释。

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.       /*分支切割方法*/
Original model: nrow = 2 ncol = 4 nnz = 7
Tolerance: primal = 1e-06 int = 1e-05 mipgap = 0.0001 mipgapAbs = 1e-06
Parallelism: root=1, tree=2
tree id 0 node 0 accept a new sol: obj 1 (heur) bnd vio 0 int vio 0 mipgap 1e+100
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.003s

Simplex method started.        /*单纯形法*/

    Iteration       Objective       Dual Inf.     Primal Inf.     Time
            0     0.00000e+00      0.0000e+00      2.0000e+00     0.02s    
            2     5.55556e-01      0.0000e+00      0.0000e+00     0.02s    
Postsolver started.
Simplex method terminated. Time : 0.014s

            0     5.55556e-01      0.0000e+00      0.0000e+00     0.03s    
            0     5.55556e-01      0.0000e+00      0.0000e+00     0.03s    
            0     5.55556e-01      0.0000e+00      0.0000e+00     0.03s    
            0     5.55556e-01      0.0000e+00      0.0000e+00     0.03s    
            0     5.55556e-01      0.0000e+00      0.0000e+00     0.03s    
            0     5.55556e-01      0.0000e+00      0.0000e+00     0.03s    
            0     5.55556e-01      0.0000e+00      0.0000e+00     0.03s    
            0     5.55556e-01      0.0000e+00      0.0000e+00     0.03s    
            0     5.55556e-01      0.0000e+00      0.0000e+00     0.03s    
            0     5.55556e-01      0.0000e+00      0.0000e+00     0.03s    
            0     5.55556e-01      0.0000e+00      0.0000e+00     0.03s    
            0     5.55556e-01      0.0000e+00      0.0000e+00     0.03s    
            0     5.55556e-01      0.0000e+00      0.0000e+00     0.03s    
            0     5.55556e-01      0.0000e+00      0.0000e+00     0.03s    
            0     5.55556e-01      0.0000e+00      0.0000e+00     0.03s    
            0     5.55556e-01      0.0000e+00      0.0000e+00     0.03s    
            0     5.55556e-01      0.0000e+00      0.0000e+00     0.03s    
            0     5.55556e-01      0.0000e+00      0.0000e+00     0.03s    
            0     5.55556e-01      0.0000e+00      0.0000e+00     0.03s    
            0     5.55556e-01      0.0000e+00      0.0000e+00     0.03s    
Branch-and-cut method terminated. Time : 0.062s

Optimizer summary.   /*求解器最终选择的优化方法以及求解消耗的时间*/
 - Optimizer used     : Branch-and-cut method   /*分支和切割方法*/
 - Optimizer status   : OPTIMAL
 - Total time         : 0.087s

Solution summary.
 - Primal objective   : 1.0000000000e+00 /*目标函数最优解*/
 - Dual bound         : 5.5555555556e-01

联系我们

钉钉：damodi

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

文章标签：
C++
C语言
Python
达摩院
API
决策智能Lab_运营小编003
目录
相关文章
mindopt
|
达摩院 Linux API
阿里达摩院MindOpt求解器V1.1新增C#接口
阿里达摩院MindOpt求解器发布最新版本V1.1，增加了C#相关API和文档。优化求解器产品是求解优化问题的专业计算软件，可广泛各个行业。阿里达摩院从2019年投入自研MindOpt优化求解器，截止目前经历27个版本的迭代，取得了多项国内和国际第一的成绩。就在上个月，2023年12月，在工信部产业发展促进中心等单位主办的首届能源电子产业创新大赛上，MindOpt获得电力用国产求解器第一名。本文将为C#开发者讲述如何下载安装MindOpt和C#案例源代码。
mindopt
455 3
阿里达摩院MindOpt求解器V1.1新增C#接口
决策智能Lab_运营小编003
|
算法 安全 机器人
Python语言如何使用MindOpt建模并求解二次规划问题
MindOpt是一款高效的优化算法软件包，求解算法实现了线性规划(LP)、混合整数线性规划(MILP)、二次规划(QP)，可以支持命令行、c、c++、java和python调用。接下来我们将发布一系列文章，讲述各个语言如何使用 MindOpt 来求解数学规划问题。
决策智能Lab_运营小编003
1385 163
Python语言如何使用MindOpt建模并求解二次规划问题
决策智能实验室运营小编
|
C语言 Perl 存储
优化求解器之MPS文件的格式简介
在使用MindOpt优化求解器解决实际问题时，其中重要的一环在于如何建立优化模型，以及存储优化模型以便于作为求解器的输入文件。存储优化模型的文件，其关键在于定义一种清晰的格式，用来说明优化模型的数学结构和相关的数据。接下来我们将发布一系列文章，对常见的MPS/LP等格式的模型文件和命名规范进行简要的介绍。
决策智能实验室运营小编
7859 0
优化求解器之MPS文件的格式简介
决策智能Lab_运营小编003
|
达摩院
MindOpt APL 达摩院自己的建模语言！
MindOpt建模语言(MindOpt Algebraic Programming Language, MindOpt APL, 简称为MAPL)是MindOpt团队研发的一种代数建模语言。相比与其他的语言，MAPL语法相对较少且自然，很贴近数学语言。用MAPL描述数学规划模型与用数学公式进行描述非常类似。
决策智能Lab_运营小编003
763 0
MindOpt APL 达摩院自己的建模语言！
mindopt
|
达摩院 IDE 开发工具
阿里达摩院MindOpt优化求解器-月刊（2024年5月）
阿里达摩院MindOpt优化求解器-月刊（2024年5月版），新增了两个案例，如何使用LLM和MindOpt更准确地回答数学问题、如何使用MindOpt优化云计算集群虚拟机资源配置提高机器利用率，和如何利用IIS冲突分析指导不可解的问题解决方案。MindOpt的求解器已经可以在阿里云线上购买不联网版本。租户版也正式上线，可体验更多功能。新增QQ交流群。
mindopt
265 4
决策智能Lab_运营小编003
|
达摩院 算法 Java
选择优化求解器的关键因素：以MindOpt为例
选择一款适合自己业务需求的求解器我们一般需要考量什么呢？可求解的问题类型？问题规模？本文将介绍一些需要考虑的重要因素，并且介绍阿里达摩院MindOpt优化求解器在这些因素下的表现。
决策智能Lab_运营小编003
246 4
决策智能Lab_运营小编003
|
达摩院 API C++
MindOpt--C++语言-对一个简单的混合整数规划问题建模求解
MindOpt是达摩院决策智能实验室研究的一款优化求解器，目前在优化求解线性规划问题这一功能上取得不错的成绩，希望大家能够帮我们多多打磨其他功能(混合整数线性规划、二次规划、半定规划目前都在公测)，让我们的MindOpt在优化求解器这板块成为国产之光。
决策智能Lab_运营小编003
889 1
MindOpt--C++语言-对一个简单的混合整数规划问题建模求解
mindopt
|
达摩院 Python
阿里达摩院MindOpt优化求解器-月刊（2024年6月）
**阿里达摩院MindOpt优化求解器2024年6月月刊概览：** - 发布新功能，MAPL建模语言V2.5上线，Python APIs全面升级，旧版本不兼容。 提供快速入门教程、示例代码展示如何用Python调用MAPL。MindOpt Studio租户版新增Gradio支持，便于开发WebAPP，提供了案例源码展示如何开发。引入新案例： 1. 巡检线路的排班-2017全国大学生数学建模竞赛D题。包含最短路模型、TSP模型、弧分割模型。2. 商品组合定价策略：探讨如何最赚钱的加购区商品定价。
mindopt
222 0
mindopt
|
缓存 达摩院 算法
如何通过阿里达摩院MindOpt获得MILP多个解
在2024年1月达摩院新发布的MindOpt 优化求解器V1.1.0版本中，新增加了一个"MIP/SolutionNumber"参数，可以用于获取MILP多个解。有些业务里，会想要找到更多的可行解，目标值不一定最优，用于给业务指导。本篇案例将讲解如何使用此功能。
mindopt
455 1
决策智能Lab_运营小编003
|
机器学习/深度学习 人工智能 达摩院
MindOpt工具是如何做到配套使用的？请看此篇
MindOpt是阿里巴巴达摩院决策职能实验室研发的专注于优化领域，提供智能优化解决方案的品牌。主要的目标是帮助客户通过先进的优化算法和技术，实现业务流程的最佳化，提升效率，降低成本，并最大化业务价值。
决策智能Lab_运营小编003
252 3

达摩院 MindOpt 优化

热门文章

最新文章

  • 1
    ACP认证考试-必须要了解的那点事
  • 2
    什么叫灰度测试
  • 3
    PostgreSQL Huge Page 使用建议 - 大内存主机、实例注意
  • 4
    从零开始学_JavaScript_系列（一）初步概念、工具选择、简单内容输出、加载js文件
  • 5
    阿里云虚拟主机HTTPS（HTTP+SSL）加密开通了
  • 6
    网络知识大集合（最详细）与网络通信过程
  • 7
    2019·杭州·云栖大会·MVP见闻分享
  • 8
    静态库改为动态库后，可以影响到程序的执行结果
  • 9
    HTML中的相对路径与绝对路径
  • 10
    LDD3学习笔记（1）：设备驱动简介
  • 1
    Coze平台指南（3）：核心功能-创建智能体与设计角色
    135
  • 2
    Playwright携手MCP：AI智能体实现自主化UI回归测试
    122
  • 3
    从文本到知识：使用LLM图转换器构建知识图谱的详细指南
    100
  • 4
    《云原生微服务治理进阶：隐性风险根除与全链路能力构建》
    25
  • 5
    在折叠屏应用中，如何处理不同屏幕尺寸和设备类型的样式兼容性？
    212
  • 6
    《云原生故障诊疗指南：从假活到配置漂移的根治方案》
    27
  • 7
    在React中使用React Foldable Layout时，如何处理折叠区域的样式问题？
    18
  • 8
    除了Foldables.js库，还有哪些库可以实现折叠屏适配？
    116
  • 9
    Browser Use：打造你的浏览器自动化助手
    107
  • 10
    ChatGPT与我们玩游戏_排雷
    19

    • 相关电子书

    更多
  • 低代码开发师（初级）实战教程
  • 冬季实战营第三期：MySQL数据库进阶实战
  • 阿里巴巴DevOps 最佳实践手册
    • 下一篇
    阿里云 EMR Serverless Spark 版开启免费公测