递归分支定界

2019-11-08 02:26:55

字体：大中小

来源：转载

供稿：网友

递归解分支定界问题

标签（空格分隔）：算法学习

一、算法描述

线性规划是日常常用的算法之一，通过线性规划的对偶单纯性，可以解决最大流，最短路径等常见的规划问题。但是在TSP问题中，所要求得的解释选择或者不选择当前的边，输出结果也就是只有0,1两种结果，此种问题也被称为0,1规划。或者当我们计算给每条边分配怎样的权重的时候，最大最小化代价函数问题，也被称为整数规划的问题。

二、算法描述

(1)求整数规划的松弛问题最优解。 (2)若松弛问题的最优解满足整数要求，得到整数规划的最优解，否则转下一步。 (3)任意选一个非整数解的变量，在松弛问题中加上约束及+1组成两个新的松弛问题，称为分支。新的松弛问题具有如下特征：当原问题是求最大值时，目标值是分支问题的上界；当原问题足求最小值时，目标值是分支问题的下界。 (4)检查所有分支的解及目标函数值，若某分支的解是整数并且目标函数值大于(max)等于其他分支的目标值，则将其他分支剪去不再计算，若还存在非整数解并且目标值大于(max)整数解的目标值，需要继续分支，再检查，直到得到最优解算法的流程图与说明见下图所示此处输入图片的描述

三、具体代码以及运行实例

#define _CRT_SECURE_NO_WARNINGS#include<stdio.h>#include<stdlib.h>#include "search_route.h"#include "lp_lib.h"#include<math.h>#define INF 65535#define NaN -65535#define LEFT 1#define RIGHT 2double UB;double* UB_X;int BB_JYLL(lPRec* lp, int lp_length);int IsArrInteger(double*, int);int FindFirstDecimal(double *, int, double&);double RoundDouble(const double);int main(){ lprec *lp; int ret = 0, count, ret_int; int colno[2] = { 1, 2 }; // 未知数个数编号 count = 2; // 未知数个数 lp = make_lp(0, count); //double row[3] = { -1, -1, 0 }; // 目标函数系数 //double row_LE[8] = { 14, 9, -6, 3, -1, 0, 0, -1}; // LE 约束系数左边 //double B_LE[4]= { 51, 1, 0, 0 }; // LE 约束系数右边 //double row[3] = { -5, -8, 0 }; // 目标函数系数 //double row_LE[8] = { 5, 9, 1,1, -1, 0, 0, -1 }; // LE 约束系数左边 //double B_LE[4] = { 45, 6, 0, 0 }; // LE 约束系数右边 double row[3] = { -3, -2, 0 }; // 目标函数系数 double row_LE[8] = { 2, 3, 1, 0.5, -1, 0, 0, -1 }; // LE 约束系数左边 double B_LE[4] = { 14, 4.5, 0, 0 }; // LE 约束系数右边 UB_X = new double[count]; // set the objective in lpsolve set_obj_fnex(lp, count, row, colno); //double row_LE[2]; for (int i = 0; i < 4; ++i) { add_constraintex(lp, count, row_LE + i * count, colno, LE, B_LE[i]); } ret_int = BB_JYLL(lp, count); if (ret_int == 0) // 有整数解 { printf("有整数解 /n"); for (int i = 0; i < count; i++) { printf("%lf/n", UB_X[i]); } printf("最优代价 : %lf /n/n", UB); } else { printf("无解/n"); } delete[] UB_X; return 0;}//==================================================================================================================================================================================================//==================================================================================================================================================================================================//==================================================================================================================================================================================================int BB_JYLL(lprec* lp, int lp_length){ int ret = 0; lprec* lp_hat = NULL; lp_hat = copy_lp(lp); // 线性规划松弛条件 ret = solve(lp_hat); if (ret == 0) // LP 有解 { double* x_hat; double y_hat; x_hat = (double *)malloc(lp_length * sizeof(double)); // 获取 x_hat y_hat get_variables(lp_hat, x_hat); y_hat = get_working_objective(lp_hat); if (y_hat <= UB) // y_hat 在界内 { if (IsArrInteger(x_hat, lp_length)) // x_hat 为整数 { UB = y_hat; // 存上界为 y_hat memcpy(UB_X, x_hat, lp_length * sizeof(double)); // 存 x_hat return 0; } else // x_hat 为分数 { int xk_id; double xk_val; xk_id = FindFirstDecimal(x_hat, lp_length, xk_val); //============================== int* colno; colno = new int[lp_length]; for (int i = 0; i < lp_length; i++) { colno[i] = i + 1; } lprec *lp_l, *lp_r; lp_l = copy_lp(lp_hat); lp_r = copy_lp(lp_hat); int flag_l, flag_r; double* row_LE = NULL; // 新增左侧 row_LE = (double*)malloc(lp_length * sizeof(double)); //memset(row_LE, 0, lp_length * sizeof(double)); for (int i = 0; i < lp_length; i++) { row_LE[i] = 0; } printf("/n/n %lf %lf /n/n", xk_val, floor(xk_val)); printf("/n/n %lf /n/n", ceil(xk_val)); row_LE[xk_id] = 1; add_constraintex(lp_l, lp_length, row_LE, colno, LE, double(floor(xk_val))); // 左侧分支 //flag_l = solve(lp_l); flag_l = BB_JYLL(lp_l, lp_length); row_LE[xk_id] = -1; add_constraintex(lp_r, lp_length, row_LE, colno, LE, -ceil(xk_val)); // 右侧分支 flag_r = BB_JYLL(lp_r, lp_length); free(row_LE); delete[] colno; if ((flag_l + flag_r) < 2) // 有解 { return 0; } else // 无解 { return 1; } } } else // y_hat 在界外 { return 1; } } else // LP无解 { return 1; }}static int IsArrInteger(double *arr, int length){ // function : // 检查一维数组是否全为整数 // // input : // arr : 被检测一维数组 // length : 数组长度 // // output : // return 1 : 数组中全为整数 // return 0 : 数组中不全为整数，存在分数 // // 2016.04.06 // JY double diff = 0; for (int i = 0; i < length; ++i) { diff = fabs(arr[i] - RoundDouble(arr[i])); if (diff >= 0.00001) // 数组 arr 中存在分数 return 0; } return 1; // 数组 arr 中全为整数}int FindFirstDecimal(double *arr, int length, double& xk_val){ // function : // 找到数组 arr 中第一个小数位置 // // input : // arr : 被搜索数组 // // output : // return 小数位置索引 // 如果返回 -1 ，则代表数组中无小数 // // 2016.04.06 // JY for (int i = 0; i < length; ++i) { if (fabs((arr[i] - RoundDouble(arr[i]))) >= 0.00001) { xk_val = arr[i]; return i; } } return -1;}double RoundDouble(const double dVal){ // function : // 对单个 double 型变量四舍五入取整 // // input : // dVal : 输入数据 // // output : // // 返回 dVal 的四舍五入数据 // // // 2016.04.05 // JY int res = (int)(dVal)+((int)(10 * dVal) % 10 < 5 ? 0 : 1); return double(res);}

程序说明，此程序时用来接min整数规划，要求解最大值的时候，需要设置下界为全局变量。程序中的线性规划的实现是基于在线开源库lp_solver http://www.gnu.org/software/glpk/glpk.html $http://www.gnu.org/software/glpk/glpk.html$

以上过程的实现可以总结为0,1规划问题。0,1规划可以用在线开源库GLPK进行实现

上一篇：常用排序算法小结

下一篇：【牛腩新闻发布系统】网页发布问题梳理