添加链接 注册    登录
link之家
链接快照平台
  • 输入网页链接，自动生成快照
  • 标签化管理网页链接
相关文章推荐
稳重的冰淇淋  ·  AutoGPT：有手就会的安装教程-CSDN博客·  1 月前    · 
爱吹牛的稀饭  ·  Hibernate常用方法整理-阿里云开发者社区·  1 年前    · 
内向的脸盆  ·  Unity基础篇：Unity实现双击事件（奔 ...·  1 年前    · 
无邪的夕阳  ·  TypeScript 3.9 更新了什么？ ...·  1 年前    · 
鼻子大的饭盒  ·  Expression.Lambda 方法 ...·  1 年前    · 
link之家  ›  C语言如何使用MindOpt建模并求解混合整数线性规划问题-阿里云开发者社区
c语言 线性规划 二次规划
https://developer.aliyun.com/article/1106414
果断的针织衫
2 年前

下文我们将讲述小编对线性规划的理解以及展示两个算例，和 使用 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

联系我们

钉钉群号：32451444

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

更多更新通知： https://solver.damo.alibaba.com

C语言如何使用MindOpt建模并求解线性规划问题
MindOpt是达摩院决策智能实验室研究的一款优化求解器，能帮助做方案设计、生产方案优化、资源合理分配、辅助决策等。可以支持命令行、c、c++、java和python调用，目前求解算法实现了线性规划、混合整数线性规划、二次规划。
今日选择什么语言调用MindOpt对二次规划问题建模优化呢？
MindOpt是达摩院决策智能实验室研究的一款优化求解器，能帮助做方案设计、生产方案优化、资源合理分配、辅助决策等。可以支持命令行、c、c++、java和python调用，目前求解算法实现了线性规划、混合整数线性规划、二次规划。
Python语言如何使用MindOpt建模并求解二次规划问题
MindOpt是一款高效的优化算法软件包，求解算法实现了线性规划(LP)、混合整数线性规划(MILP)、二次规划(QP)，可以支持命令行、c、c++、java和python调用。接下来我们将发布一系列文章，讲述各个语言如何使用 MindOpt 来求解数学规划问题。
Python语言如何使用MindOpt建模并求解混合整数线性规划问题
MindOpt是一款高效的优化算法软件包，求解算法实现了线性规划(LP)、混合整数线性规划(MILP)、二次规划(QP)，可以支持命令行、c、c++、java和python调用。接下来我们将发布一系列文章，讲述各个语言如何使用 MindOpt 来求解数学规划问题。
43815 线性规划求解第一的MindOpt如何使用Python语言的API建模及优化
MindOpt是一款高效的优化算法软件包，求解算法实现了线性规划(LP)、混合整数线性规划(MILP)、二次规划(QP)，可以支持命令行、c、c++、java和python调用。接下来我们将发布一系列文章，讲述各个语言如何使用 MindOpt 来求解数学规划问题
【计算理论】可判定性 ( 计算模型与语言 | 区分 可计算语言 与 可判定语言 | 证明 通用图灵机语言是 可计算语言 | 通用任务图灵机 与 特殊任务图灵机 )
【计算理论】可判定性 ( 计算模型与语言 | 区分 可计算语言 与 可判定语言 | 证明 通用图灵机语言是 可计算语言 | 通用任务图灵机 与 特殊任务图灵机 )
 
推荐文章
稳重的冰淇淋  ·  AutoGPT：有手就会的安装教程-CSDN博客
1 月前
爱吹牛的稀饭  ·  Hibernate常用方法整理-阿里云开发者社区
1 年前
内向的脸盆  ·  Unity基础篇：Unity实现双击事件（奔跑，位移）。_unity人物实现单击移动,双击奔跑-CSDN博客
1 年前
无邪的夕阳  ·  TypeScript 3.9 更新了什么？ - 知乎
1 年前
鼻子大的饭盒  ·  Expression.Lambda 方法 (System.Linq.Expressions) | Microsoft Learn
1 年前
今天看啥   ·   Py中国   ·   codingpro   ·   小百科   ·   link之家   ·   卧龙AI搜索
删除内容请联系邮箱 2879853325@qq.com
link之家 - 链接快照平台
© 2024 ~ 沪ICP备11025650号