8.4. C API¶
本章节提供MindOpt的C API手册，内容见下文。
8.4.6. Examples¶
定制食谱
有许多种不同的食物，每种食物可以提供不同的营养元素。请问我们该如何做出食物摄入的决策，以使得在满足人体每天所需的各种营养的前提下，能够最小化购买食物所花费的金额?
集合
食物集合 \(F\)
营养集合 \(N\)
参数
每单位1的食物 \(j\) 中关于营养 \(i \in N\) 的含量为 \(a_{ij}\)
获得单位1的食物 \(j\in F\) 的代价为 \(c_j\)
决策变量
\(x_j\) 是某人每天对食物 \(j\in F\) 的摄入量
目标函数
最小化食物的总采购金额： \(\text{minimize}~ \sum_{j\in F} c_{j}x_j\) 。
约束
每人对营养 \(i\in N\) 的需求介于最小值 \(n_{\min,i}\) 和最大值 \(n_{\max,i}\) 之间： \(n_{\min,i} \le \sum_{j\in F} a_{ij} x_j \le n_{\max,i},~~ \forall\, i\in N\) 。
#include <stdio.h>
#include "Mindopt.h"
#include <stdlib.h>
#define CHECK_RESULT(code) { int res = code; if (res != 0) { fprintf(stderr, "Bad code: %d \\n", res); exit(res); } }
#define NFOOD 9
#define NNUTRITION 8
#define MODEL_NAME "diet"
#define MODEL_SENSE "ModelSense"
#define STATUS "Status"
#define OBJ_VAL "ObjVal"
#define X "X"
int main(void) {
MDOenv *env;
MDOemptyenv(&env);
MDOstartenv(env);
// 建立模型
MDOmodel *m;
// 初始化数据
double demand_ub[] = {MDO_INFINITY, 375, MDO_INFINITY, MDO_INFINITY, MDO_INFINITY, MDO_INFINITY, MDO_INFINITY, 75};
double demand_lb[] = {2000, 350, 55, 100, 100, 100, 100, -MDO_INFINITY};
const char *nutrition_name[] = {"Calories", "Carbohydrates", "Protein", "VitA", "VitC", "Calcium", "Iron", "Volume"};
char *food_name[] = {"Cheeseburger", "HamSandwich", "Hamburger", "FishSandwich", "ChickenSandwich", "Fries",
"SausageBiscuit", "LowfatMilk", "OrangeJuice"};
double food_price[] = {1.84, 2.19, 1.84, 1.44, 2.29, 0.77, 1.29, 0.60, 0.72};
double req_value[NFOOD][NNUTRITION] = {
{510.0, 34.0, 28.0, 15.0, 6.0, 30.0, 20.0, 4.0},
{370.0, 35.0, 24.0, 15.0, 10.0, 20.0, 20.0, 7.5},
{500.0, 42.0, 25.0, 6.0, 2.0, 25.0, 20.0, 3.5},
{370.0, 38.0, 14.0, 2.0, 0.0, 15.0, 10.0, 5.0},
{400.0, 42.0, 31.0, 8.0, 15.0, 15.0, 8.0, 7.3},
{220.0, 26.0, 3.0, 0.0, 15.0, 0.0, 2.0, 2.6},
{345.0, 27.0, 15.0, 4.0, 0.0, 20.0, 15.0, 4.1},
{110.0, 12.0, 9.0, 10.0, 120.0, 30.0, 0.0, 8.0},
{80.0, 20.0, 1.0, 2.0, 4.0, 2.0, 2.0, 12.0}};
int *cbeg, *cind, idx;
double *cval;
int i, j, status;
double obj, x;
// 初始化模型同时添加决策变量
CHECK_RESULT(MDOnewmodel(env, &m, MODEL_NAME, NFOOD, food_price, 0, NULL, NULL, NULL));
// 添加约束
// 应满足每日获取的各种营养素在建议的范围内
cbeg = (int *)malloc(sizeof(int) * NNUTRITION);
cind = (int *)malloc(sizeof(int) * NNUTRITION * (NFOOD));
cval = (double *)malloc(sizeof(double) * NNUTRITION * (NFOOD));
idx = 0;
for (i = 0; i < NNUTRITION; i++) {
// Start index of each constraint
cbeg[i] = idx;
for (j = 0; j < NFOOD; ++j) {
cind[idx] = j;
cval[idx++] = req_value[j][i];
}
}
CHECK_RESULT(MDOaddrangeconstrs(m, NNUTRITION, idx, cbeg, cind, cval, demand_lb, demand_ub, nutrition_name));
// 添加目标函数
CHECK_RESULT(MDOsetintattr(m, MODEL_SENSE, MDO_MINIMIZE));
CHECK_RESULT(MDOoptimize(m));
// 打印结果
CHECK_RESULT(MDOgetintattr(m, STATUS, &status));
if (status == MDO_OPTIMAL) {
CHECK_RESULT(MDOgetdblattr(m, OBJ_VAL, &obj));
printf("The total cost is %f \\n", obj);
for (i = 0; i < NFOOD; ++i) {
CHECK_RESULT(MDOgetdblattrelement(m, X, i, &x));
printf("You should buy %f unit of %s \\n", x, food_name[i]);
}
} else {
printf("No feasible solution exists \\n");
}
// 释放被分配的内存
free(cbeg);
free(cind);
free(cval);
MDOfreemodel(m);
MDOfreeenv(env);
return 0;
}
设施选址
当前有两个商场，商场的位置已经确定。由若干建造仓库的备选位置，已知其坐标和其建造成本。我们假定从仓库到商场的运输成本与货物数量无关但与其之间的距离有关，请找到最小成本的仓库建造和运输方案。
集合
备选仓库 \(F\)
商场 \(M\)
参数
从仓库 \(i\in F\) 向商场 \(j \in M\) 运输的成本为 \(a_{ij}\) 。
建造仓库 \(i\in F\) 的代价为 \(c_j\) 。
商场 \(j \in M\) 的需求的货物量为 \(d_{ij}\) 。
决策变量
\(x_i\) 是是否在备选位置 \(i\in F\) 建造仓库。其取值必须为0或1，值为0时表示不建造，值为1时表示建造。
\(y_{ij}\) 表示是在从备选位置 \(i\in F\) 的仓库向 \(j \in M\) 的商场运输的距离货物数量。
目标函数
最小化仓库建造和商品运输的成本： \(\text{minimize}~ \sum_{i\in F} c_{i}x_i+\sum_{i\in F,j \in M} a_{ij}y_{ij}\) :
\(\text{minimize}~ \sum_{i\in F} c_{i}x_i + \sum_{i\in F,j \in M} a_{ij}y_{ij}\)
约束
\(\sum_{i\in F} y_{ij} = d_{j}, ~~ \forall j\in M\)
\(x_i d_j - \sum_{k\in M} y_{ik} = 0, ~~ \forall i \in F, j \in M\)
#include <stdio.h>
#include "Mindopt.h"
#include <stdlib.h>
#include <math.h>
#define CHECK_RESULT(code) { int res = code; if (res != 0) { fprintf(stderr, "Bad code: %d \\n", res); exit(res); } }
#define FACILITY_NUM 8
#define MARKET_NUM 2
#define MODEL_NAME "facility"
#define VAR_TYPE "VType"
#define MODEL_SENSE "ModelSense"
#define STATUS "Status"
#define OBJ "Obj"
#define OBJ_VAL "ObjVal"
#define VAR_NAME "VarName"
#define X "X"
double calculate_transportation_fee(double *pos1, double *pos2, double transport_fee_per_m) {
double x1 = pos1[0] - pos2[0];
double x2 = pos1[1] - pos2[1];
return sqrt(x1 * x1 + x2 * x2) * transport_fee_per_m;
}
// 本例子的目标是为了找到最小成本的仓库建造和运输方案
int main(void) {
MDOenv *env = NULL;
MDOemptyenv(&env);
MDOstartenv(env);
// 建立模型
MDOmodel *m = NULL;
// 有两个商场，商场的位置已经确定,分别是(0, 1.7)和(1.4, 2.9)， 所需要的货物重量为100单位和200单位
double market_location[MARKET_NUM][2] = {
{0.0, 1.7},
{1.4, 2.9}};
int market_demand[MARKET_NUM] = {100, 200};
// 仓库位置和建造成本
double facility_location[FACILITY_NUM][2] = {
{0, 1},
{0, 2},
{1, 0},
{1, 1},
{1, 2},
{2, 0},
{2, 1},
{2, 2}};
double facility_expense[FACILITY_NUM] = {3.0, 1.0, 1.5, 1.3, 1.8, 1.6, 1.1, 1.9};
const double transport_fee_per_m = 1.23;
int *cbeg, *cind, *cbeg2, *cind2, idx, col, i, j, status;
double *cval, *cval2, *rhs, *rhs2, obj, x;
char *sense, *sense2, var_name[25];
// 初始化模型同时添加决策变量
CHECK_RESULT(MDOnewmodel(env, &m, MODEL_NAME, FACILITY_NUM * (1 + MARKET_NUM), NULL, NULL, NULL, NULL, NULL));
// 初始化决策变量
// x代表是否在该地建仓库
for (i = 0; i < FACILITY_NUM; ++i) {
CHECK_RESULT(MDOsetcharattrelement(m, VAR_TYPE, i, MDO_BINARY));
CHECK_RESULT(MDOsetdblattrelement(m, OBJ, i, facility_expense[i]));
sprintf(var_name, "Position%d", i);
CHECK_RESULT(MDOsetstrattrelement(m, VAR_NAME, i, var_name));
}
// y代表从j仓库运向i商场的货物量，值的类型为CONTINUOUS类型，下限为0代表不能从j仓库运送小于0单位的货物到i商场
for (i = 0; i < FACILITY_NUM; ++i) {
for (j = 0; j < MARKET_NUM; j++) {
sprintf(var_name, "Transportation_%d_to_%d", i, j);
CHECK_RESULT(MDOsetstrattrelement(m, VAR_NAME, FACILITY_NUM * (1 + j) + i, var_name));
CHECK_RESULT(MDOsetdblattrelement(m, OBJ, FACILITY_NUM * (1 + j) + i,
calculate_transportation_fee(market_location[j], facility_location[i], transport_fee_per_m)));
}
}
// 增加约束
cbeg = (int *)malloc(sizeof(int) * FACILITY_NUM * MARKET_NUM);
cind = (int *)malloc(sizeof(int) * (FACILITY_NUM * MARKET_NUM * 2));
cval = (double *)malloc(sizeof(double) * (FACILITY_NUM * MARKET_NUM * 2));
rhs = (double *)malloc(sizeof(double) * FACILITY_NUM * MARKET_NUM);
sense = (char *)malloc(sizeof(char) * FACILITY_NUM * MARKET_NUM);
printf("%d \\n", FACILITY_NUM * MARKET_NUM);
idx = 0;
// 约束1 已经决定建造的仓库必须满足所有商场的货物需求
for (i = 0; i < FACILITY_NUM; i++) {
for (j = 0; j < MARKET_NUM; ++j) {
col = i * MARKET_NUM + j;
cbeg[col] = idx;
rhs[col] = 0;
sense[col] = MDO_LESS_EQUAL;
cind[idx] = FACILITY_NUM * (1 + j) + i;
cval[idx++] = 1;
cind[idx] = i;
cval[idx++] = -market_demand[j];
}
}
CHECK_RESULT(MDOaddconstrs(m, FACILITY_NUM*MARKET_NUM, idx, cbeg, cind, cval, sense, rhs, NULL));
// 约束2 如果不建仓库，则此仓库位置运送给所有商场的货物为0
cbeg2 = (int *)malloc(sizeof(int) * MARKET_NUM);
cind2 = (int *)malloc(sizeof(int) * MARKET_NUM * FACILITY_NUM);
cval2 = (double *)malloc(sizeof(double) * MARKET_NUM * FACILITY_NUM);
rhs2 = (double *)malloc(sizeof(double) * MARKET_NUM);
sense2 = (char *)malloc(sizeof(char) * MARKET_NUM);
idx = 0;
for (j = 0; j < MARKET_NUM; ++j) {
cbeg2[j] = idx;
rhs2[j] = market_demand[j];
sense2[j] = MDO_EQUAL;
for (i = 0; i < FACILITY_NUM; i++) {
cind2[idx] = FACILITY_NUM * (1 + j) + i;
cval2[idx++] = 1;
}
}
CHECK_RESULT(MDOaddconstrs(m, MARKET_NUM, idx, cbeg2, cind2, cval2, sense2, rhs2, NULL));
// 开始优化
CHECK_RESULT(MDOsetintattr(m, MODEL_SENSE, MDO_MINIMIZE));
CHECK_RESULT(MDOwrite(m, "test_c.mps"));
CHECK_RESULT(MDOoptimize(m));
CHECK_RESULT(MDOgetintattr(m, STATUS, &status));
// 打印结果
if (status == MDO_OPTIMAL) {
CHECK_RESULT(MDOgetdblattr(m, OBJ_VAL, &obj));
printf("The total cost is %f \\n", obj);
for (i = 0; i < FACILITY_NUM; ++i) {
CHECK_RESULT(MDOgetdblattrelement(m, "X", i, &x));
if (x) {
printf("The No.%d warehouse should be built at (%g, %g) \\n",
i, facility_location[i][0], facility_location[i][1]);
}
}
} else {
printf("No feasible solution exists \\n");
}
free(cbeg);
free(cind);
free(cval);
free(rhs);
free(sense);
free(cbeg2);
free(cind2);
free(cval2);
free(rhs2);
free(sense2);
MDOfreemodel(m);
MDOfreeenv(env);
return 0;
}
人力分配
在一周中，工厂每天需要的工人数目不同。现在已知每个工人的日工资及其在一周中可以出勤的日期。需要计算如何安排工人，才能在满足工厂运行要求的情况下做到工资成本最低。
集合
一周日期 \(D = 1,2,3...,7\)
工厂需要的工人数目 \(N\)
工人 \(S\)
参数
工厂第 \(i \in D\) 天所需的工人数目为 \(n_i\)
工人 \(j\in S\) 的日工资为 \(s_j\)
表示工人可工作时间的序列，共有 \(T\) 组工人-工作时间数对 \((d_i,t_i)\) ，其中 \(d_i\in S,t_i \in D, i = 1,2,3...T\) 。
目标函数
最小化支付的工资： \(\text{minimize}~ \sum_{i=1,2,3...T} x_is_{d_i}\)
决策变量
\(x_i( i = 1,2,3...T)\) 表示可工作时间序列中，当日改工人是否上班。其取值必须为0或1，值为0时表示不上班，值为1时表示上班。
约束
\(\sum_{d_i=r} x_i = n_{r}, ~~\forall r\in D\)
#include <stdio.h>
#include "Mindopt.h"
#include <stdlib.h>
#define CHECK_RESULT(code) { int res = code; if (res != 0) { fprintf(stderr, "Bad code: %d \\n", res); exit(res); } }
#define MODEL_NAME "workforce"
#define MODEL_SENSE "ModelSense"
#define STATUS "Status"
#define OBJ_VAL "ObjVal"
#define X "X"
#define WORKERS_NUM 7
#define DAY_NUM 7
int main(void) {
MDOenv *env = NULL;
MDOemptyenv(&env);
MDOstartenv(env);
MDOmodel *m = NULL;
int id = 0;
char var_name[20];
int i, j;
// 每天需要的人力数
const char *day_name[] = {"Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday", "Sunday"};
double workers_per_day[] = {3, 1, 4, 2, 1, 3, 3};
// 每个工人一天的工资
char *workers_name[] = {"Xiaoming", "Huahua", "HongHong", "Dahua", "Lihua", "Niuniu", "Gouzi"};
double workers_pay[] = {13, 10, 11, 8, 9, 14, 14};
// 每个工人可以出勤的时间
int availability[WORKERS_NUM][DAY_NUM];
int non_zero_num = 32;
int non_zero_col[] = {0, 0, 0, 0, 1, 1, 1, 1, 2,2, 2,
2, 3, 3, 3, 3, 4,4, 4, 4, 4,
4, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6};
int non_zero_row[] = {1, 2, 4, 6, 0, 1, 4, 5, 2, 3, 4,
6, 1, 2, 4, 5, 0, 1, 2, 3, 4,
6, 0, 1, 2, 5, 0, 1, 2, 4, 5, 6};
for (j = 0; j < non_zero_num; ++j) {
availability[non_zero_col[j]][non_zero_row[j]] = 1;
}
int *cbeg, *cind, idx, status;
double *cval, *rhs, obj, x;
char *sense;
// 初始化模型同时添加决策变量
CHECK_RESULT(MDOnewmodel(env, &m, MODEL_NAME, 0, NULL, NULL, NULL, NULL, NULL));
// 初始化决策变量，并设置其在目标函数中的系数
for (j = 0; j < DAY_NUM; ++j) {
for (i = 0; i < WORKERS_NUM; ++i) {
if (availability[i][j]) {
sprintf(var_name, "%s.%s", workers_name[i], day_name[j]);
CHECK_RESULT(MDOaddvar(m, 0, NULL, NULL, workers_pay[i], 0, 1, MDO_BINARY, (const char*)var_name));
id++;
}
}
}
// 增加约束
// 约束： 满足每天的人力需求
cbeg = (int *)malloc(sizeof(int) * DAY_NUM);
cind = (int *)malloc(sizeof(int) * id);
cval = (double *)malloc(sizeof(double) * id);
rhs = (double *)malloc(sizeof(double) * DAY_NUM);
sense = (char *)malloc(sizeof(char) * DAY_NUM);
idx = 0;
id = 0;
for (i = 0; i < DAY_NUM; ++i) {
cbeg[i] = idx;
rhs[i] = workers_per_day[i];
sense[i] = MDO_EQUAL;
for (j = 0; j < WORKERS_NUM; ++j) {
if (availability[j][i]) {
cind[idx] = id;
cval[idx++] = 1;
id++;
}
}
}
CHECK_RESULT(MDOaddconstrs(m, DAY_NUM, idx, cbeg, cind, cval, sense, rhs, day_name));
// 开始优化
CHECK_RESULT(MDOsetintattr(m, MODEL_SENSE, MDO_MINIMIZE));
CHECK_RESULT(MDOoptimize(m));
CHECK_RESULT(MDOwrite(m, "test_c.mps"));
CHECK_RESULT(MDOgetintattr(m, STATUS, &status));
// 打印结果
if (status == MDO_OPTIMAL) {
CHECK_RESULT(MDOgetdblattr(m, OBJ_VAL, &obj));
printf("The total cost is %f \\n", obj);
for (j = 0; j < WORKERS_NUM; ++j) {
char *worker_name = workers_name[j];
for (i = 0; i < DAY_NUM; ++i) {
CHECK_RESULT(MDOgetdblattrelement(m, X, i, &x));
if (x == 1) {
printf("%s should work at %s \\n", worker_name, day_name[i]);
}
}
}
} else {
printf("No feasible solution exists \\n");
}
// 释放被分配的内存
free(cbeg);
free(cind);
free(cval);
free(rhs);
free(sense);
MDOfreemodel(m);
MDOfreeenv(env);
return 0;
}