目录
前言
分支定界算法
列生成算法
步骤
参考文献

前言
简述分支定价算法原理，如有错误可私信，谢谢。部分截图来自本人汇报所用PPT以及参考文献。以下均以最小化问题为例。
分支定界算法
分支定价算法(branch and price, B&P）=分支定界(branch and bound, B&B）+列生成(column generation, CG, 线性规划)。其中列生成算法用于求节点的下界，即节点松弛模型的最优解。列生成算法因其求解方法的本质会大大减少计算量，求解的并非节点松弛模型本身，而是受限制的松弛模型，即减少了决策变量规模。分支定价算法其他步骤与分支定界算法相同，只是下界计算由列生成算法完成。如下为流程图。


列生成算法


列生成算法所求解的问题大都决策变量规模非常大，相应地其约束系数也非常多（如上图每个xj对应一组{a1j,…,aij,…,anj}），不可能同时表达出来一起求解，典型问题就是切卷纸的问题，顾客需要不同长度的卷纸若干，需要对固定长度的卷纸进行裁剪。对卷纸而言可行的裁剪方案的约束条件是不超过卷纸的固定长度（可能会有巨多种），对整个问题而言，就是找到一个解决方案（方案由裁剪方案与裁剪数量组成，如裁剪方案1裁剪5卷纸，裁剪方案2裁剪3卷纸可得到最终结果）得到顾客想要的若干不同长度卷纸，并使用最少的原固定长度的卷纸。



列生成特点为无需列出所有可行的裁剪方案(恢复成多)再进行求解，只需先列出几个裁剪方案然后随着求解这几个裁剪方案下的原问题（主问题，Master Problem）的受限问题（Restricted Master Problem），再不断迭代增加对问题有益的裁剪方案最终求出松弛问题的最优解。
步骤
（如上图）

1、根据原问题，选取几个可行列（可行裁剪方案），得到受限问题模型

2、通过受限问题RMP获得检验数以构建子问题的方程，子问题的约束条件即为可行列的生成条件（裁剪方案需要满足卷纸固定长度的限制，例如5米长的卷纸，只能裁剪成3米1个，2米1个；不能是4米1个，2米1个）

子问题表达：



子问题目标函数中检验数pi来自于RMP问题，通过RMP的基向量和非基向量划分后的对应参数c_B和B计算得到（参考单纯形法计算过程，参考[1]）。需要将RMP问题标准化得到基变量非基变量，将其对应参数计算检验数，并用以求解子问题，得到新的可行列加入RMP问题。



3、求解子问题，子问题的解若对应目标函数（检验数）小于0，那么将解y（可行列）加入受限问题，循环步骤2~3，否则若子问题的解对应目标值不小于0，则循环结束

4、求当前受限问题RMP的最优解，即分支定价中该节点的下界
注：建议配合给出的参考[1]中的链接一起理解，步骤2~3的依据是单纯形法中进基出基的判断方法（进基出基后可得到子问题目标值中的检验数），当基确定后（通过每列的检验数判断），RMP问题最优解则可得出，也就是分支定价过程中该节点的下界。
参考文献
[1] 列生成：https://www.cnblogs.com/dengfaheng/p/11249879.html

https://www.jianshu.com/p/8be0083886ed

https://www.cnblogs.com/cruelty_angel/p/10493527.html
[2] 分支定界：https://www.cnblogs.com/dengfaheng/p/11225612.html

[3] 分支定价：https://my.oschina.net/u/4354879/blog/3432783

李播.基于分支定价的手术计划调度研究

在上一篇《机器学习1》中提到梯度下降算法并列出了代数表达式，来看一下代数实现
下面我们把它放到python 3里面，转变成代码的形式去实现梯度下降。
import numpy as np

X=2*np.random.rand(100,1)#生成训练函数(特征部分)
y=4+3*X+np.random.randn(100,1)   #生成训练数据(标签部分)
plt.plot(X,y,'b.')  #画图
plt.xlabel('$x_1$',fontsize=18)
plt.ylabel('$y$',rotation=0,fontsize=18)
plt.axis([0,2,0,15])
save_fig('generated_data_plot')  #保存图片
plt.show()
1.批量梯度下降算法
在上面代码的基础上,我们还要添加新特征,创建测试数据。设置步长，数据集个数，迭代次数
def plot_gradient_descent(theta,eta,theta_path=None):
    m=len(X_b)
    plt.plot(X,y,'b.')
    n_iterations=1000     #迭代次数
    for iteration in range(n_iterations):
        if iteration <10:    #画线
            y_predict=X_new_b.dot(theta)
            style='b-'
            plt.plot(X_new,y_predict,style)
        gradients=2/m * X_b.T.dot(X_b.dot(theta)-y)
        theta = theta-eta * gradients
        if theta_path is not None:
            theta_path.append(theta)
    plt.xlabel('$x_1$',fontsize=18)
    plt.axis([0,2,0,15])
    plt.title(r'$eta={}$'.format(eta),fontsize=16)
采用三种步长逼近:
2.随机梯度下降算法
n_epochs=50

theta=np.random.randn(2,1)     #随机初始化

for epoch in range(n_epochs):
    for i in range(m):
        if epoch==0 and i<20:
            y_predict=X_new_b.dot(theta)
            style='b-'
            plt.plot(X_new,y_predict,style)
        random_index=np.random.randint(m)
        xi=X_b[random_index:random_index+1]
        yi=y[random_index:random_index+1]
        gradients=2* xi.T.dot(xi.dot(theta)-yi)
        eta=0.1
        theta=theta-eta*gradients
        theta_path_sgd.append(theta)
        
plt.plot(X,y,'b.')
plt.xlabel('$x_1$',fontsize=18)
plt.ylabel('$y$',rotation=0,fontsize=18)
plt.axis([0,2,0,15])
save_fig('sgd_plot')
plt.show()
theta
3.小批量梯度下降算法
theta_path_mgd=[]

n_iterations=50
minibatch_size=20

np.random.seed(42)
theta=np.random.randn(2,1)

for epoch in range(n_iterations):
    shuffled_indices=np.random.permutation(m)
    X_b_shuffled=X_b[shuffled_indices]
    y_shuffled=y[shuffled_indices]
    for i in range(0,m,minibatch_size):
        xi=X_b_shuffled[i:i+minibatch_size]
        yi=y_shuffled[i:i+minibatch_size]
        gradients=2/minibatch_size * xi.T.dot(xi.dot(theta)-yi)
        eta=0.1
        theta=theta-eta*gradients
        theta_path_mgd.append(theta)
泰勒公式(泰勒展开式)
是用一个函数在某点的信息，描述其附近取值的公式。如果函数足够平滑，在已知函数在某一点的各阶导数值的情况下，泰勒公式可以利用这些导数值来做系数，构建一个多项式近似函数，求得在这一点的邻域中的值。
所以泰勒公式是做什么用的？
简单来讲就是用一个多项式函数去逼近一个给定的函数(即尽量使多项式函数图像拟合给定的函数图像)，注意，逼近的时候一定是从函数图像上的某个点展开。如果一个非常复杂函数，想求其某点的值，直接求无法实现，这时候可以使用泰勒公式去近似的求该值，这是泰勒公式的应用之一。泰勒公式在机器学习中主要应用于梯度迭代。
1.一元泰勒展开式
2.二元泰勒展开式

电脑自动生成数独游戏的谜题
要得出所有满足条件的组合确实不是件容易的事情（主要是很多，打印起来很慢） 。但偶们的目标只是每次能得到一个新的组合，然后从格子里面随机遮掉一些数字就可以了。所以只需要在解数独游戏算法的基础上稍作修改即可。
所以，算法的步骤是：
1.往第一行或第一列随机填1-9的数字
2.调用解数独算法得到一个结果
3.每行随机遮掉1-8个数字。如果需要较大的难度，也可以将1-8改为2-8或3-8，等等。
以下是console工程的代码：
// sudoku.cpp : 定义控制台应用程序的入口点。
// by superarhow(superarhow@hotmail.com)
#include "stdafx.h"
#include "conio.h"
/***************** 广告位招租 *********************/
/* 为了代码好看^^ */
#define SUCCESS  1
#define _FAILED  0
/* 地图类型9*9的char，每个char从0-9，0表示待填 */
typedef char MAPTYPE[9][9];
/*  行数据，同时用作“可能性”数据。如LINETYPE a; 当a[0]为真时表示
   当前位置可填1，a[1]为真时表示可填2，以此类推 */
typedef char LINETYPE[9];
typedef void (*ONMAPOKCALLBACK)(MAPTYPE map);
/* 打印地图 */
void dump_map(MAPTYPE dest)
{
 for ( int j = 0; j < 9; j++ )
 {
  for ( int i = 0; i < 9; i++ )
  {
   printf("%d ", dest[i][j]);
  }
  printf("/n");
 }
 printf("/n");
}
int fill_line(MAPTYPE dest, int line, ONMAPOKCALLBACK callback);
/* 填下一个格子。本行的可能性已在调用前算好，要考虑的是列的可能性和九宫格的可能性 */
/* nums_possible : array (0-8) means possible of number (1-9) */
int fill_pos(MAPTYPE dest, LINETYPE nums_possible, int line, int pos, ONMAPOKCALLBACK callback)
{
 if ( pos >= 9 )
 {
  return fill_line(dest, line + 1, callback);
 }
 if ( dest[pos][line] != 0 ) return fill_pos(dest, nums_possible, line, pos + 1, callback);
 for ( int i = 0; i < 9; i++ )
 {
  if ( !nums_possible[i] ) continue;
  /* 检查本列是否重复 */
  int vetical_failed = 0;
  for ( int j = 0; j < 9; j++ ) 
   if ( dest[pos][j] == i + 1 )
   {
    vetical_failed = 1;
    break;
   }
  if ( vetical_failed ) continue; 
  /* 检查九宫格是否重复 */
  int nine_failed = 0;
  int m = pos / 3;
  int n = line / 3;
  m *= 3;
  n *= 3;
  for ( int y = n; y < n + 3; y++ )
  {
   for ( int x = m; x < m + 3; x++ )
   {
    if ( dest[x][y] == i + 1 ) 
    {
     nine_failed = 1;
     break;
    }
   }
   if ( nine_failed ) break;
  }
  if ( nine_failed ) continue;
  /* all ok, try next position */
  dest[pos][line] = i + 1;
  nums_possible[i] = 0;
  if ( fill_pos(dest, nums_possible, line, pos + 1, callback) ) 
  {
   /* 本行已全部OK，尝试下一行 */
   if ( fill_line(dest, line + 1, callback) ) return SUCCESS;
   /* 下一行失败，重新尝试本位置的剩余可能性 */
  }
  nums_possible[i] = 1;
  dest[pos][line] = 0;
 }
 return _FAILED;
}
/* 填下一行 */
int fill_line(MAPTYPE dest, int line, ONMAPOKCALLBACK callback)
{
 if ( line >= 9 )
 {
  /* copy map */
  callback(dest);
  return SUCCESS;
 }
 LINETYPE nums;
 LINETYPE saveline;
 /* calc possibility(for the current line) */
 for ( int i = 0; i < 9; i++ ) nums[i] = 1; /* all can be */
 for ( int i = 0; i < 9; i++ )
 {
  char n = dest[i][line];
  /* save line */
  saveline[i] = dest[i][line];
  if ( n != 0 ) nums[n - 1] = 0; /* appears */
 }
 if ( !fill_pos(dest, nums, line, 0, callback) )
 {
  /* restore line */
  for ( int i = 0; i < 9; i++ ) dest[i][line] = saveline[i];
  return _FAILED;
 }
 return SUCCESS;
}
MAPTYPE g_result;
void on_map_ok(MAPTYPE map)
{
 memcpy(g_result, map, sizeof(MAPTYPE));
}
#include "windows.h"
int _tmain(int argc, _TCHAR* argv[])
{
 MAPTYPE dest;
 memset(dest, 0, sizeof(MAPTYPE));
 srand( GetTickCount() );
 /* 随机填充第一行 */
 char ch[9] = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
 for ( int i = 0; i < 9; i++ )
 {
  int p = rand() % 9;
  char t = ch[p];
  ch[p] = ch[i];
  ch[i] = t;
 }
 for ( int i = 0; i < 9; i++ ) dest[i][0] = ch[i];
 if ( fill_line(dest, 0, on_map_ok) ) 
 {
  /* 修剪掉一些块 */
  for ( int i = 0; i < 9; i++ ) 
  {
   /* 调整n的取值范围可改变难度 %6 + 3是比较难的 */
   int n = (rand() % 6) + 3;
   for ( int j = 0; j < 9; j++ ) ch[j] = j; /* ch: index to erase */
   for ( int j = 0; j < 9; j++ )
   {
    int p = rand() % 9;
    char t = ch[p];
    ch[p] = ch[i];
    ch[i] = t;
   }
   for ( int j = 0; j < n; j++ ) g_result[ch[j]][i] = 0;
  }
  dump_map(g_result);
 }
 getch();
 return 0;
}
 

最小生成树
1.克鲁斯卡尔算法
$\bullet$克鲁斯卡尔算法的实质就是加边，先对边进行从小到大排序，然后再从小的边开始加进树里，但是不能构成环。重复上述步骤，直至树里面有n-1条边（总共有n个结点）
原始图：（从1号点开始）



第一次：



第二次:



第三次：



第四次：



好了，最小生成树就构造好了。

$\bullet$例题：

某省调查乡村交通状况，得到的统计表中列出了任意两村庄间的距离。省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通（但不一定有直接的公路相连，只要能间接通过公路可达即可），并要求铺设的公路总长度为最小。请计算最小的公路总长度。

Input

测试输入包含若干测试用例。每个测试用例的第1行给出村庄数目N ( < 100 )；随后的N(N-1)/2行对应村庄间的距离，每行给出一对正整数，分别是两个村庄的编号，以及此两村庄间的距离。为简单起见，村庄从1到N编号。

当N为0时，输入结束，该用例不被处理。

Output

对每个测试用例，在1行里输出最小的公路总长度。

Sample Input
3
1 2 1
1 3 2
2 3 4
4
1 2 1
1 3 4
1 4 1
2 3 3
2 4 2
3 4 5
0

Sample Output
3
5

$\bullet$代码运用到了并查集：
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<queue>
#include<vector>
#include<set>
#include<iostream>
#include<queue>
#include<string>
using namespace std;
const int maxn=1e4+10;
const int inf=999999999;
int par[maxn];
int k,m,n;
struct node
{
    int s,e,val;
}e[maxn];

int cmp(node a,node b)
{
    return a.val<b.val;
}

int Find(int x)
{
    if(x==par[x])return x;
    else {
        par[x]=Find(par[x]);
        return  par[x];
    }
}

void join(int a,int b)
{
    int fa=Find(a);
    int fb=Find(b);
    if(fa!=fb){
        par[fb]=fa;
    }
}

void init()
{
    for(int i=1;i<=n*(n-1)/2;i++)par[i]=i;
    memset(e,0,sizeof(e));
}


int main()
{
    while(scanf("%d",&n)&&n)
    {
        init();
        int N=n*(n-1)/2;
        for(int i=1;i<=N;i++){
            int a,b,c;
            scanf("%d%d%d",&a,&b,&c);
            e[i]={a,b,c};
        }
        sort(e+1,e+N+1,cmp);//对边进行排序
        int sum=0;
        int flag=0;
        for(int i=1;i<=N;i++){
            if(Find(e[i].s)!=Find(e[i].e)&&(flag<=n-1)){//要合并的两个点的祖先结点不能一样，一样就要构成环了，这是不符合最小生成树的定义的
                join(e[i].s,e[i].e);
                flag++;
                sum+=e[i].val;
            }
            else if(flag>=(n-1))break;
        }
        printf("%d\n",sum);
    }
    return 0;
}

2.prim(普里姆)算法
$\bullet$普里姆算法的实质就是加点，设有两个集合：U和V，U代表已经加入树中的结点，V代表还未加入树的结点。最开始U中没有结点。

首先有个dis[ i ]数组（初始化为无穷大），代表第 i 个节点与把它更新的结点之间的边权算法主要有两个步骤：

1.找到最小的dis[ i ]

2.更新与 i 结点有边的结点

原始图：（从1号点开始）



第一次：



第二次：


第三次：


第四次：



一个最小生成树就构造好了。

$\bullet$例题（还是上面的例题）：
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<queue>
#include<vector>
#include<set>
#include<iostream>
#include<queue>
#include<string>
using namespace std;
const int maxn=1e3+10;
const int inf=999999999;
int n,m;
int mp[maxn][maxn];
int vis[maxn],dis[maxn];

int prim(int start)
{
   int ans=0;
   dis[start]=0;
   for(int i=1;i<=m;i++){
       int minn=inf;
       int now=0;
       for(int j=1;j<=m;j++){//在未加入树中的结点中找最小的边
           if(!vis[j]&&dis[j]<minn){
               minn=dis[j];
               now=j;
           }
       }
       ans+=dis[now];//将点和边加入树中
       vis[now]=1;
       for(int j=1;j<=m;j++){//更新与刚才找到的now点有边相连的点
           if(!vis[j]&&mp[now][j]<dis[j])
               dis[j]=mp[now][j];
       }
   }
   return ans;
}

void init(){
   for(int i=1;i<=m;i++){
       dis[i]=inf;
       for(int j=1;j<=m;j++){
           mp[i][j]=inf;
       }
       mp[i][i]=0;
   }
   for(int i=1;i<=m;i++)vis[i]=0;
}

int main()
{
   while(scanf("%d",&m)&&m){///m个点
       init();
       n=m*(m-1)/2;
       for(int i=1;i<=n;i++){
           int a,b,c;
           scanf("%d%d%d",&a,&b,&c);
           mp[a][b]=min(mp[a][b],c);
           mp[b][a]=min(mp[a][b],c);
       }
       int ans=prim(1);
       printf("%d\n",ans);
   }
   return 0;
}