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

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

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

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

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


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

安装

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

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

线性规划

我们先介绍一下线性规划，我个人认为是在线性的目标和约束中，找出一个最优解(如最大利润或最低成本)。线性规划可以广泛的应用在我们的生活中，解决资源利用、人力调配、生产安排等问题。

入门案例

一位员工每天要负责处理a任务(生成零部件) 和b任务(组装产品)。其参与a任务的报酬为100元/小时，b任务的报酬为150元/小时。工厂要求该员工每天在每个任务上花费至少 3 个小时。已知该员工每天工作8小时（因此在 6 小时之外，可以自行决定 2 小时如何工作），那么他该如何在两项任务上分配时间以得到尽可能多的报酬？


  • 以上问题可以被称为任务分配问题，也可以被视为一个简单的排产排程问题，由于该员工要决策时间分配，我们引入决策变量 Xa和 Xb用于表示该工人投入在任务和任务中的时长。由问题描述可知，这些变量需要满足Xa+Xb=8 和 Xa>=3,Xb>=3。
  • 此外，该工人的目标是获得尽可能多的报酬。在定义如上三要素后，我们可以建立如下的数学规划问题：
  • 决策变量: Xa,Xb
  • 目标函数: maxmize 100Xa + 150Xb
  •     约束:  s.t.  Xa + Xb = 8
  •                      Xa>=3 , Xb>=3
  • 这个列题最后求出的最优解是每天参与a任务三小时、b任务5小时。

image.png

在上文的例子，是一个简单的线性规划问题，只有两个决策变量，而线性规划问题示例中的问题涉及到四个决策变量，人工去求最优解呢，需要先把线性规划问题转换为标准形式，然后制表、入基、出基、换基，最后迭代得出最优解，过程比较复杂，那么我们可以使用商用求解器 MindOpt ，让计算机来帮助我们求解。

线性规划问题可以用以下数学公式来描述：

image.png

公式参考自：https://solver.damo.alibaba.com/doc/html/model/lp/linear%20problem.html

进阶算例

要找到一个和线性规划问题示例中的问题相匹配的文字列题比较困难，所以我们在这里做一个假设，把它当成是一个人力调配的问题，求解的是一个目标函数的最小值，也就是花费最低成本去解决问题。

接下来把上述的问题带入下文的数学算例，用MindOpt优化求解器进行求解。

线性规划问题示例：

image.png

MindOpt+c语言的建模与优化

核心使用的几个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 接口函数

下面是完整的例子，可复制存为MdoLoEx1.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;                                           \}intmain(void)
{
/* 变量 */charstr[1024] = { "\0" };
MdoMdl*model=NULL;
MdoResultcode=MDO_OKAY;
MdoStatusstatus=MDO_UNKNOWN;
constintrow1_idx[] = { 0,   1,   2,   3   };
constdoublerow1_val[] = { 1.0, 1.0, 2.0, 3.0 };
constintrow2_idx[] = { 0,    2,   3   };
constdoublerow2_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_NO));
MDO_CHECK_CALL(Mdo_addCol(model, 0.0, MDO_INFINITY, 1.0, 0, NULL, NULL, "x1", MDO_NO));
MDO_CHECK_CALL(Mdo_addCol(model, 0.0, MDO_INFINITY, 1.0, 0, NULL, NULL, "x2", MDO_NO));
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. 释放模型。                                          *//*------------------------------------------------------------------*//* Free the model. */Mdo_freeMdl(&model);
return (int)code;
}

MindOpt求解的结果

如何运行MdoLoEx1.c文件

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

#运行文件放在“源文件”下，图片被挡住了不好意思。

*linux和mac系统在命令行输入cd<MDOHOME>/<VERSION>/examples/Cmake-fMakefileall./MdoLoEx1

运行MdoLoEx1.c文件后，得到求解的结果如下所示，/**/号里面是小编的注释

Concurrentoptimizationstarted. /*并发优化开始*/-Num. threads       : 2-Num. optimizers    : 2-Registeredoptimizers.
+                  : Simplexmethod (1thread, enabledoutput)
+                  : Interiorpointmethod (1thread, disabledoutput)
Modelsummary.
-Num. variables     : 4-Num. constraints   : 2-Num. nonzeros      : 7-Boundrange        : [1.0e+00,1.0e+01]  /*限制范围*/-Objectiverange    : [1.0e+00,1.0e+00]       /*目标范围*/-Matrixrange       : [1.0e+00,6.0e+00]       /*矩阵范围*/Presolverstarted.
Presolverterminated. Time : 0.000sSimplexmethodstarted.                     /*使用单纯形法*/Modelfingerprint: ==gZ3B2djdXZIterationObjectiveDualInf.     PrimalInf.     Time00.00000e+000.0000e+001.0000e+000.00s24.00000e-010.0000e+000.0000e+000.00sPostsolverstarted.
Simplexmethodterminated. Time : 0.002sConcurrentoptimizationterminated. /*求解器最终选择的优化方法以及求解消耗的时间*/Optimizersummary.
-Optimizerused     : Simplexmethod/*单纯形法*/-Optimizerstatus   : OPTIMAL-Totaltime         : 0.005sSolutionsummary.       Primalsolution/*目标函数最优解*/-Objective          : 4.0000000000e-01

联系我们

钉钉群号：32451444

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

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

文章标签：
C++
C语言
Python
达摩院
API
关键词：
优化求解器建模
优化求解器线性规划
优化求解器建模线性规划
决策智能Lab_运营小编003
目录
相关文章
决策智能Lab_运营小编003
|
6月前
|
人工智能 自然语言处理 达摩院
MindOpt 云上建模求解平台：多求解器协同优化
数学规划是一种数学优化方法，主要是寻找变量的取值在特定的约束情况下，使我们的决策目标得到一个最大或者最小值的决策。
决策智能Lab_运营小编003
209 0
决策智能Lab_运营小编003
|
6月前
|
机器学习/深度学习 算法 测试技术
MindOpt APL向量化建模语法的介绍与应用（1）
向量化建模是一种高效的数学建模和编程技术，它涉及到对向量、矩阵和更高维数组进行操作，以实现操作的同时性和批量处理。在优化和数据分析等领域，向量化建模可以极大地提高计算效率，特别是当涉及到大量的重复计算时。由于向量化建模具有表述优势、操作优势、计算性能、可扩展性等优势，使得其适合于解决很大一类实际问题
决策智能Lab_运营小编003
92 4
决策智能Lab_运营小编003
|
6月前
|
测试技术 索引
MindOpt APL向量化建模语法的介绍与应用（2）
在数据科学、工程优化和其他科学计算领域中，向量和矩阵的运算是核心组成部分。MAPL作为一种数学规划语言，为这些领域的专业人员提供了强大的工具，通过向量式和矩阵式变量声明以及丰富的内置数学运算支持，大大简化了数学建模和优化问题的处理。在本文中，我们将探索MAPL的这些特性，并且通过示例来展示如何有效使用这些工具。
决策智能Lab_运营小编003
69 0
决策智能Lab_运营小编003
|
6月前
|
开发框架 自然语言处理 达摩院
MindOpt APL，可以支持调用几十种求解器的建模语言
建模语言可以提供更高级、更灵活的问题描述方式，从而提高问题的理解和求解效率。它可以加速问题的开发和部署过程，促进不同领域之间的合作和交流，从而推动问题求解的进展和创新。
决策智能Lab_运营小编003
130 1
决策智能Lab_运营小编003
|
6月前
MindOpt APL建模语言自定小义函数的重要性和示例
在编程和建模语言中，函数是一段独立的、可重复使用的代码块，用于执行特定任务。在MindOpt APL中，自定义函数的使用非常重要，因为它们提高了建模过程的效率、可读性和灵活性。
决策智能Lab_运营小编003
90 0
决策智能Lab_运营小编003
|
6月前
|
人工智能 算法 决策智能
MindOpt云上建模求解平台功能的简单介绍
MindOpt云上建模求解平台是阿里巴巴达摩院研发的一款“优化领域”的云平台。它结合了最新的算法研究和云技术，为用户提供了一个易于使用的界面和强大的后台计算能力。该平台支持广泛的优化问题，包括线性规划、整数规划、非线性规划和混合整数规划等。
决策智能Lab_运营小编003
187 0
决策智能Lab_运营小编003
|
6月前
|
达摩院 自然语言处理 Java
MindOpt APL：一款适合优化问题数学建模的编程语言
本文将以阿里达摩院研发的MindOpt建模语言(MindOpt Algebra Programming Language, MindOptAPL，简称为MAPL)来讲解。MAPL是一种高效且通用的代数建模语言，当前主要用于数学规划问题的建模，并支持调用多种求解器求解。
决策智能Lab_运营小编003
308 0
决策智能Lab_运营小编003
|
6月前
|
达摩院 开发者 容器
「达摩院MindOpt」优化形状切割问题（MILP）
在制造业，高效地利用材料不仅是节约成本的重要环节，也是可持续发展的关键因素。无论是在金属加工、家具制造还是纺织品生产中，原材料的有效利用都直接影响了整体效率和环境影响。
决策智能Lab_运营小编003
152 0
「达摩院MindOpt」优化形状切割问题（MILP）
Deephub
|
1月前
|
机器学习/深度学习 算法 数据可视化
如果你的PyTorch优化器效果欠佳,试试这4种深度学习中的高级优化技术吧
在深度学习领域，优化器的选择对模型性能至关重要。尽管PyTorch中的标准优化器如SGD、Adam和AdamW被广泛应用，但在某些复杂优化问题中，这些方法未必是最优选择。本文介绍了四种高级优化技术：序列最小二乘规划（SLSQP）、粒子群优化（PSO）、协方差矩阵自适应进化策略（CMA-ES）和模拟退火（SA）。这些方法具备无梯度优化、仅需前向传播及全局优化能力等优点，尤其适合非可微操作和参数数量较少的情况。通过实验对比发现，对于特定问题，非传统优化方法可能比标准梯度下降算法表现更好。文章详细描述了这些优化技术的实现过程及结果分析，并提出了未来的研究方向。
Deephub
27 1
嘟嘟嘟嘟嘟嘟
|
4月前
|
人工智能 算法 调度
优化问题之如何选择合适的优化求解器
优化问题之如何选择合适的优化求解器
嘟嘟嘟嘟嘟嘟
37 1

达摩院 MindOpt 优化

热门文章

最新文章

  • 1
    SQL优化器原理 - Auto Hash Join
  • 2
    PostgreSQL 9.6 并行计算 优化器算法浅析
  • 3
    MySQL · 捉虫动态 · order by limit 造成优化器选择索引错误
  • 4
    PostgreSQL 优化器案例之 - order by limit 索引选择问题
  • 5
    达摩院的MindOpt优化求解器发布新功能，又获第一，还免费
  • 6
    pytorch优化器与学习率设置详解
  • 7
    SQL Server优化器特性-隐式谓词
  • 8
    Pytorch学习笔记（7）：优化器、学习率及调整策略、动量
  • 9
    Oracle数据的优化器有两种优化方法：
  • 10
    学习黑盒优化算法CMA和RandomSearch，借助阿里达摩院MindOpt的RABBO榜单【系列2/4】
  • 1
    人员排班【数学规划的应用(含代码)】阿里达摩院MindOpt
    135
  • 2
    排产排程问题【数学规划的应用（含代码）】阿里达摩院MindOpt
    111
  • 3
    阿里达摩院MindOpt优化求解器-月刊（2024年6月）
    130
  • 4
    仓库选址问题【数学规划的应用(含代码)】阿里达院MindOpt
    104
  • 5
    【FlowShop流水线作业排班问题【数学规划的应用(含代码)】阿里达摩院MindOpt】
    95
  • 6
    PolarDB产品使用合集之优化器对索引的阈值一般是多少
    53
  • 7
    阿里达摩院MindOpt优化求解器-月刊（2024年5月）
    118
  • 8
    选择优化求解器的关键因素：以MindOpt为例
    97
  • 9
    深度探索自适应学习率调整：从传统方法到深度学习优化器
    131
  • 10
    阿里达摩院MindOpt优化求解器-月刊（2024年4月）
    124

    • 相关课程

    更多
  • C语言学习教程
  • 你的第一门C语言课
  • 达摩院MindOpt优化求解器入门与实践
  • 【算法实战】8. 集成方法-Adaboost
  • 机器学习入门-概念原理及常用算法
  • 【算法实战】9. 线性回归算法

    • 相关电子书

    更多
  • 阿里技术专家一挃：MongoDB 优化器 & 执行器介绍
  • 纯干货|机器学习中梯度下降法的分类及对比分析
  • 纯干货 | 机器学习中梯度下降法的分类及对比分析

    • 相关实验场景

    更多
  • 欧拉图的构造性证明与算法实现
    • 下一篇
    阿里云OSS设置跨域访问