[0 basic operations research] [super detail] column generation

Column generation （Column generation） It is an effective algorithm for solving large linear programs .

Related courses

• 【 Starting from scratch 】coin-or/CoinUtils Osi Clp Cgl Cbc Source build debug（CLion/CMake）

Related literature

• Column generation（wikipedia）
• dried food | 10 Minutes will give you a thorough understanding of column generation（ Column generation ） The principle of the algorithm java Code
• Column generation and branch pricing
• Linear programming skills : Column generation (Column Generation)
• Principle of column generation algorithm ( Simplex basis )
• Column generation （Column Generation） Algorithm
• 【Column Generation reflection -02】| Understand... From the perspective of duality Cutting Stock Problem【 An updated version 】
• Gilmore P C, Gomory R E. A linear programming approach to the cutting-stock problem[J]. Operations research, 1961, 9(6): 849-859.
• Operations research says The first 21 period | Algorithm introduction column generation algorithm

Preface

I've always wanted to share with you Column generation （Column generation）, I also searched many documents all over the Internet 、 video 、 Papers, etc . Most tutorials are highly abstract , It requires a lot of basic knowledge to understand , So write an article as much as possible 0 Basic sharing , I hope I can help you who are also engaged in related industries .

Someone must ask , Is there any Row generation algorithm ？ Of course. ！！！ I'll share it with you when I have a chance ！！！——@ Pig Rush

Start with an example ：Cutting Stock Problem

Problem description

The seller has 3 A length of wood ：9cm（5 element ）,14cm（9 element ）,16cm（10 element ）.
Buyers need wood ：4cm（30 root ）,5cm（20 root ）,7cm（40 root ）.
So the seller needs to pass Cut wood Meet the needs of buyers , And the seller hopes Lowest cost So as to benefit the most .

analysis

First, let's think briefly , A piece of 9cm How many kinds of wood cutting methods can meet the needs of buyers 4cm,5cm,7cm

cost（ element ）	Length of wood before cutting （cm）	4cm Quantity of wood	5cm Quantity of wood	7cm Quantity of wood
5	9	1	0	0
5	9	2	0	0
5	9	0	1	0
5	9	1	1	0
5	9	0	0	1

In line with the traditional Chinese virtue of not wasting , obviously The cut of the second line is better than the first line Some (＾Ｕ＾)ノ~ＹＯ
We usually call a cutting method cutting pattern.
All right. , Then it was very easy After that （ Only keep the better pattern）.

All Cutting Pattern：

cost（ element ）	Length of wood before cutting （cm）	4cm Quantity of wood	5cm Quantity of wood	7cm Quantity of wood	Symbol
5	9	2	0	0	$x_1$
5	9	1	1	0	$x_2$
5	9	0	0	1	$x_3$
9	14	3	0	0	$x_4$
9	14	2	1	0	$x_5$
9	14	1	2	0	$x_6$
9	14	1	0	1	$x_7$
9	14	0	1	1	$x_8$
9	14	0	0	2	$x_9$
10	16	4	0	0	$x_{10}$
10	16	2	0	1	$x_{11}$
10	16	1	1	1	$x_{12}$
10	16	0	3	0	$x_{13}$

So we just need to start from All Cutting Pattern It's sure Every Pattern How many times does it take That's it .（ for instance ： such as ${\mathbf{x}}_1=30$ On behalf of us, we use the 1 Cut it in a different way 30 root 9cm Length of wood ）.

Our goal is to use The least money Complete the buyer's needs , That is, every one of them Pattern Of $\mathbf{c}\mathbf{o}\mathbf{s}\mathbf{t}\times \text{Number}$ The sum of .

$5x_1+5x_2+5x_3+9x_4+9x_5+9x_6+9x_7+9x_8+9x_9+10x_{10}+10x_{11}+10x_{12}+10x_{13}$

In addition, we need Meet the requirements of the number of buyers .
4cm More than 30 root ：

$2x_1+x_2+0x_3+3x_4+2x_5+x_6+x_7+0x_8+0x_9+4x_{10}+2x_{11}+x_{12}+0x_{13}\ge 30$

5cm More than 20 root ：

$0x_1+x_2+0x_3+0x_4+x_5+2x_6+0x_7+x_8+0x_9+0x_{10}+0x_{11}+x_{12}+3x_{13}\ge 20$

7cm More than 70 root ：

$0x_1+0x_2+x_3+0x_4+0x_5+0x_6+x_7+x_8+2x_9+0x_{10}+x_{11}+x_{12}+0x_{13}\ge 40$

modeling

Master Problem（MP）

Based on the above analysis , We already have decision variables $x_i$, We have the objective function The least money , We also have corresponding constraints Meet the requirements of the number of buyers , So we can model ！！！

Defining decision variables ${\mathbf{x}}_{\mathbf{i}}$ In order to use the $i$ Kind of Pattern Root number of .
$\min 5x_1+5x_2+5x_3+9x_4+9x_5+9x_6+9x_7+9x_8+9x_9+10x_{10}+10x_{11}+10x_{12}+10x_{13}$
$s.t.$
$2x_1+x_2+0x_3+3x_4+2x_5+x_6+x_7+0x_8+0x_9+4x_{10}+2x_{11}+x_{12}+0x_{13}\ge 30$
$0x_1+x_2+0x_3+0x_4+x_5+2x_6+0x_7+x_8+0x_9+0x_{10}+0x_{11}+x_{12}+3x_{13}\ge 20$
$0x_1+0x_2+x_3+0x_4+0x_5+0x_6+x_7+x_8+2x_9+0x_{10}+x_{11}+x_{12}+0x_{13}\ge 40$
$x_i\in \mathbb{N}$
Each column ： The number of times a feasible cutting scheme needs to be executed , perhaps How many bars use this cutting scheme
Every line ： The need for a bar must be met

Restricted Master Problem（RMP）

occasionally MP Will be very large , So we consider how to use several Pattern Get a feasible solution （ It may not be the optimal solution ）, Then we have this feasible solution, and then we can see in turn if we add others Pattern Will there be a better solution , And directly solve MP The feasible solution may not be obtained in a given time .

So we follow this idea to build RMP（ Pay attention to what we choose Pattern At least one feasible solution can be obtained ）：

Defining decision variables ${\mathbf{x}}_{\mathbf{i}}$ In order to use the $i$ Kind of Pattern Root number of .
$\min 5x_1+5x_2+5x_3$
$s.t.$
$2x_1+x_2+0x_3\ge 30$
$0x_1+x_2+0x_3\ge 20$
$0x_1+0x_2+x_3\ge 40$
$x_i\in \mathbb{N}$

Restricted Linear Master Problem（RLMP）

The conventional column generation method is to solve LP The problem of , At this time, we do some proper relaxation （ That is to say $x_i\in \mathbb{N}$ become $x_i\ge 0$）.

So we follow this idea to build RLMP（ it is to be noted that RLMP The feasible solution of is not necessarily RMP Feasible solution of , But we just need to round up the solution ）：

Defining decision variables ${\mathbf{x}}_{\mathbf{i}}$ In order to use the $i$ Kind of Pattern Root number of .
$\min 5x_1+5x_2+5x_3$
$s.t.$
$2x_1+x_2+0x_3\ge 30$
$0x_1+x_2+0x_3\ge 20$
$0x_1+0x_2+x_3\ge 40$
$x_i\ge 0$

Then we can use LP solver Directly solve the above model （ Here I use Clp For example , Of course, you can use your favorite solver ）

（ In order to make the typesetting neat and convenient for reading , I will put the code at the end of the text ）

Run directly to get

In theory, we should treat the result Round up , But we will get relaxed MP Rounding after solution will be more convenient and efficient , So we don't do it here Round up （ But it seems that the solution is an integer Σ(⊙▽⊙"a——@ Pig Rush ）：
$Objectivevalue=325$
$x_1=5$
$x_2=20$
$x_3=40$
Let's try to explain solution The meaning of ： use 5 individual Pattern 1（ That is to say, I chose 5 root 9cm Of wood , Cut each into 2 individual 4cm）, Similar again 20 individual Pattern 2 and 40 individual Pattern 3, Such a choice can minimize our total cost ——325 element .

Dual of Restricted Linear Master Problem

Now let's consider from another angle RMP.
【 The seller 】 Buy the finished product directly （ Cut wood ）, Sell it to customers , Similar middlemen .
【 The seller 】 The goal is ： At most, how much money do you spend to buy finished products and earn more than you produce yourself .
【 The seller 】 constraint ： We need to set a psychological price for the finished product . These psychological prices must meet ： For any cutting scheme , Money to buy finished products <= Money produced by oneself .（ for instance , Seller flower 5 Yuan to buy 1 root 9cm The wood can be cut into 2 individual 4cm finished product , That is to say, if the seller purchases directly 2 individual 4cm The price of finished products exceeds 5 Yuan, it's better to produce it yourself . Write a formula ：$2y_1\le 5$, among ${\mathbf{y}}_1$ by 4cm Psychological price of wood ）
————————————————————————————————————————————————————————
Defining decision variables ${\mathbf{y}}_{\mathbf{i}}$ Respectively 4cm（30 root ）,5cm（20 root ）,7cm（40 root ） Psychological price of wood .
$\max 30y_1+20y_2+40y_3$
$s.t.$
$2y_1+0y_2+0y_3\le 5$
$y_1+y_2+0y_3\le 5$
$0y_1+0y_2+y_3\le 5$
$y_i\ge 0$

Solve directly ：

$Objectivevalue=325$
$y_1=2.5$
$y_2=2.5$
$y_3=5.0$
Let's try to explain solution The meaning of ：4cm、5cm、7cm The psychological prices of finished wood are 2.5 element 、2.5 element 、5 element , Most flowers 325 Yuan to buy finished products to earn more than their own production . That is, as long as Price ratio 2.5 element 、2.5 element 、5 Yuan is low , The seller makes money .

Subproblem

• The meaning of simplex method test number ： The product （ Variable ） The difference between the market price of and the implied cost of the product . The market price is higher than the implied cost , That is, when the inspection number is greater than zero , Then the product can be put into production .
• The test number of the original problem corresponds to a basic solution of its dual problem

If you know the concept of test number , Will soon understand subproblem, But here I'll assume you don't know , Try to make you understand in the simplest way ——@ Pig Rush

stay dual In the question, we calculate the psychological price of the finished product . Next, we want to know whether there is a more economical Pattern.
First, let's think about how to judge a Pattern Is it more economical .
Example 1：9cm The complete waste of wood is also a kind of Pattern, But one 9cm The wood should be 5 element , In other words, the seller lost 5 element .
Example 2：Pattern 9：14cm Wood （9 element ） Cut into 2 root 7cm finished product （ Use Pattern 1、2、3 Of 7cm Psychological price is 5 element ）. That is, sellers only use Pattern 1、2、3 These three cutting methods , Just use less than 5 Yuan price purchase 7cm Selling it again is more profitable than cutting it yourself , And if you add Pattern 9, If the seller uses 5 The price of yuan is not as good as using it directly Pattern 9 To make money , It must be lower than 4.5 element （9 element /2） For the price of 7cm Selling it again is more profitable than cutting it yourself .
With the above two examples, we have gradually clarified how to judge a Pattern Is it more economical .
In other words, our goal is to find a new Pattern： new Pattern The finished product after cutting is old Pattern Psychological price under > new Pattern The price of
Defining decision variables ${\mathbf{a}}_{\mathbf{j}}$ It's new. Pattern After cutting 4cm,5cm,7cm The amount of wood .
new Pattern The finished product after cutting is old Pattern Psychological price under 【$2.5a_1+2.5a_2+5a_3$】> new Pattern The price of 【9 element （14cm）】
namely ：
$2.5a_1+2.5a_2+5a_3>9$
$\Rightarrow 9-(2.5a_1+2.5a_2+5a_3)<0$（ To the left of the inequality sign we generally call it Inspection number , This is what we often say The test number determines whether the solution is the optimal solution ）
Here we use a trick of converting constraints into objective functions ： Make $z=9-(2.5a_1+2.5a_2+5a_3)$, If $\min z$ Than 0 Also big , That means it doesn't exist $z>0$ Solution , That is, there is no more economical Pattern.
new Pattern The total length after cutting cannot exceed the length of the original wood ：$4a_1+5a_2+7a_3\le 14$
All in all ：
$\min 9-(2.5a_1+2.5a_2+5a_3)$
$4a_1+5a_2+7a_3\le 14$

So we set up 9cm、14cm、16cm Of Subproblem ：
————————————————————————————————————————————————————————
Subproblem 1（9cm,5 element ）
Defining decision variables ${\mathbf{a}}_{\mathbf{j}}$ yes Pattern After cutting 4cm,5cm,7cm The amount of wood .
$\min z=5-(2.5a_1+2.5a_2+5a_3)$
$s.t.$
$4a_1+5a_2+7a_3\le 9$
$a_i\in \mathbb{N}$
To solve the need to ：$a=(2,0,0{)}^T,z=0$
————————————————————————————————————————————————————————
Subproblem 2（14cm,9 element ）
Defining decision variables ${\mathbf{a}}_{\mathbf{j}}$ yes Pattern After cutting 4cm,5cm,7cm The amount of wood .
$\min z=9-(2.5a_1+2.5a_2+5a_3)$
$s.t.$
$4a_1+5a_2+7a_3\le 14$
$a_i\in \mathbb{N}$
To solve the need to ：$\mathbf{a}=(0,0,2{)}^{\mathbf{T}},\mathbf{z}=-1$
————————————————————————————————————————————————————————
Subproblem 3（16cm,10 element ）
Defining decision variables ${\mathbf{a}}_{\mathbf{j}}$ yes Pattern After cutting 4cm,5cm,7cm The amount of wood .
$\min z=10-(2.5a_1+2.5a_2+5a_3)$
$s.t.$
$4a_1+5a_2+7a_3\le 16$
$a_i\in \mathbb{N}$
To solve the need to ：$a=(4,0,0{)}^T,z=0$

iteration

We found that Subproblem 2 Of $z<0$, So we put $a=(0,0,2{)}^T$ This Pattern Add to RLMP in , Because this is what we found to be more economical Pattern.
Defining decision variables ${\mathbf{x}}_{\mathbf{i}}$ In order to use the $i$ Kind of Pattern Root number of .
$\min 5x_1+5x_2+5x_3+9x_9$
$s.t.$
$2x_1+x_2+0x_3+0x_9\ge 30$
$0x_1+x_2+0x_3+0x_9\ge 20$
$0x_1+0x_2+x_3+2x_9\ge 40$
$x_i\ge 0$

After solving, we get ：

$Objectivevalue=305$
$x_1=5$
$x_2=20$
$x_3=0$
$x_9=20$
$y_1=2.5$
$y_2=2.5$
$y_9=4.5$
because $x_3=0$, So we can omit from the model $x_3$.
So we set up 9cm、14cm、16cm Of Subproblem ：
————————————————————————————————————————————————————————
Subproblem 1（9cm,5 element ）
Defining decision variables ${\mathbf{a}}_{\mathbf{j}}$ yes Pattern After cutting 4cm,5cm,7cm The amount of wood .
$\min z=5-(2.5a_1+2.5a_2+4.5a_9)$
$s.t.$
$4a_1+5a_2+7a_9\le 9$
$a_i\in \mathbb{N}$
To solve the need to ：$a=(2,0,0{)}^T,z=0$
————————————————————————————————————————————————————————
Subproblem 2（14cm,9 element ）
Defining decision variables ${\mathbf{a}}_{\mathbf{j}}$ yes Pattern After cutting 4cm,5cm,7cm The amount of wood .
$\min z=9-(2.5a_1+2.5a_2+4.5a_9)$
$s.t.$
$4a_1+5a_2+7a_9\le 14$
$a_i\in \mathbb{N}$
To solve the need to ：$a=(0,0,2{)}^T,z=0$
————————————————————————————————————————————————————————
Subproblem 3（16cm,10 element ）
Defining decision variables ${\mathbf{a}}_{\mathbf{j}}$ yes Pattern After cutting 4cm,5cm,7cm The amount of wood .
$\min z=10-(2.5a_1+2.5a_2+4.5a_9)$
$s.t.$
$4a_1+5a_2+7a_9\le 16$
$a_i\in \mathbb{N}$
To solve the need to ：$a=(4,0,0{)}^T,z=0$

be-all Subproblem The goal is $z\ge 0$, That means there is no better Pattern, So the final solution （ Remember Round up ）：$x_1=5,x_2=20,x_9=20$

The whole algorithm process above is called —— Column generation

Column generation ：Cutting Stock Problem

This section requires a certain basis of operations research , But if you have read the above , I believe it will be very simple to understand .——@ Pig Rush

Put forward Gomory The big guy who cut Gomory stay IBM When , With another big man Gilmore Jointly put forward the famous Column Generation：

reference ：
@article{gilmore1961linear,
title={A linear programming approach to the cutting-stock problem},
author={Gilmore, Paul C and Gomory, Ralph E},
journal={Operations research},
volume={9},
number={6},
pages={849–859},
year={1961},
publisher={INFORMS}
}

Problem description

The seller has $n$ A length of wood ：$L_i$ m（$c_i$ element ）
Buyers need $m$ A length of wood ：$l_i$ m（$d_i$ root ）
So the seller needs to pass Cut wood Meet the needs of buyers , And the seller hopes Lowest cost So as to benefit the most .

modeling

Master Problem（MP）

$$\begin{array}{rl}& \min \sum _{i=1}^n{c}_i{x}_i\\ & s.t.\sum _{i=1}^n{a}_{ij}{x}_i\ge b_i,j=1,2,...,m\\ & x_i\in \mathbb{N},\forall i\end{array}$$

Restricted Master Problem（RMP）

$$\begin{array}{rl}& \min \sum _{i=1}^k{c}_i{x}_i\\ & s.t.\sum _{i=1}^k{a}_{ij}{x}_i\ge b_i,j=1,2,...,m\\ & x_i\in \mathbb{N},\forall i\end{array}$$

That is to say MP The number of problem variables ranges from $n$ Reduced to $k$ individual , It should be noted that we forced $x_i(i>k)$ The variable of is a non base variable .

Dual of Restricted Master Problem

In order to be in Subproblem Calculate the inspection number ：${\sigma }_j=c_j-c_B{B}^{-1}{a}_j$, We need to figure out $c_B{B}^{-1}$, Generally speaking, he has two meanings ：

1. By solving RMP The shadow price of the problem （shadow price）.
2. By solving RMP The dual variable of dual problem (dual variable).

We usually use the 2 Solve a dual problem . because RMP There are many general variables , Simplex method is difficult to solve problems with many variables . The variables of the original problem correspond to the constraints of the dual problem , The target coefficient corresponds to the constraint boundary , The constraint matrix is reversed . So there is no such problem on the duality problem .

Subproblem

$$\begin{array}{rl}& \min c_j-\sum {\omega }_i{a}_i\\ & s.t.\sum _{i=1}^m{l}_i{a}_i\le L_j\\ & a_i\ge 0,\forall i\end{array}$$

iteration

The inspection number is less than 0 Words , Just put Pattern Add column , Go to the next iteration , Until all inspection numbers are greater than or equal to 0. Finally, round up the result .

flow chart

summary

1. Column generation algorithm is mainly used to solve More variables , but Most variables take 0 The linear programming problem of .
2. The general idea is to select a small number of variables to build RMP（ That is, the values of other variables are 0） Get a feasible solution quickly , After that Subproblem Calculate the number of tests （reduced cost） Look for better variables to add to the model and solve again , Until no better variable can be found .
3. Why can adding variables make the target value better ？ Add variables to the original problem => Dual problems add constraints => The optimal value of the dual problem remains unchanged or becomes smaller （ The dual problem is max problem , The more constraints, the smaller the feasible region , The goodness of natural objective function decreases ）=> The optimal value of the original problem remains unchanged or becomes smaller （ The optimal solution of the dual problem is the same as that of the original problem ）
   in fact , The variable we need to find is to make the optimal solution not meet the new constraints in the dual problem .