Question about upper bound

[yangliuxin-nn]

Hi sir,

I am an undergraduate at BJUT. I am writing to ask could you please explain what is the "upper bound" of your branch and price model and how do you establish it?

Best wishes, Liuxin

[shaoxiang-zheng]

"Upper bound" means a value that is no less than the optimal value. Generally speaking, any feasible solution value is an upper bound (for minimization problem). Before the solving process, any feasible solution (e.g., obtained by a heuristic) can be regarded as an upper bound. Durting the execution of the branch and price, any identified feasible solution can be used to possibly update upper bound.

[yangliuxin-nn]

Many thanks for your detailed explanation. Could you please explain:

• "Before the solving process, any feasible solution (e.g., obtained by a heuristic) can be regarded as an upper bound."

• Which way do you use to generate the upper bound before the solving process? Or specifically could you please show which line of codes you set up the initial upper bound?

• "During the execution of the branch and price, any identified feasible solution can be used to possibly update upper bound."

• Could you please show where you update the upper bound? Sorry for my confusion I cannot find the "upper_bound" tag in the repository.

Many thanks for your time!!!

[shaoxiang-zheng]

1. for a minimization optimization problem, any feasible solution is no less than the optimal value. Also, the procedure to obtain a feasible solution is not necessary before the solving process.
2. I do not choose to generate an upper bound. In line 125, searchTree,py, I initialize "incumbent", and you can view it as an upper bound. Besides, you can also generate a feasible solution in this line instead of initializing "None" as its intial value. 3-4. In line 157-158 of searchTree.py, any found feasible solution may be the material of the upper bound ("incumbent" in the code)

[yangliuxin-nn]

Thank you!!!

I am searching for the "pattern" of your model. Could you please show which attributes represent the "pattern" for the bin packing problem and how do you establish and update it?

[shaoxiang-zheng]

“Pattern” means some items are placed in a bin, e.g., there are 5 items 1-5, and their sizes are 2, 3, 4, 5, 6, the bin size is 8. [item 1, item 2] is a pattern, and [item 1, item 3] is a different pattern. You can also think that its a set of items whose sizes are not greater than the bin's. In the model, each column of its coefficient matrix is also a pattern. So it may not be apparent in model. In line 121-122 masterModel.py, we initialize the model with some columns, each representing a pattern in which exact one item is included.

[yangliuxin-nn]

Thank you!!!

I understand that the pattern for a bin is composed of 0 and 1. 1 means pack that item into the bin and 0 means do not pack the item into the bin. Hope my understanding is consistent with your illustration. But I am wondering what is the meaning of "self.x[i] == 1 for i in x_index" in lines 121-122 of masterModel.py; as you said, this is where the pattern is initialized.

[shaoxiang-zheng]

Yes, I will give you another example. For an instance with three items, we initialize three patterns (columns) with exact one item: [1, 0, 0], [0, 1, 0] and [0, 0, 1]. Obviously, it's a identity matrix. Therefore, the corresponding constrants are x[1] = 1, x[2] = 1, x[3] =1., which is coded as my programme: x[i] = 1 for i in ....

[yangliuxin-nn]

Thank you!!! You are so nice and the example is very vivid. Could you please show where the coefficient of the combination of different patterns is established and updated?

[shaoxiang-zheng]

As I just stated, line 121-122 masterModel.py is the initialization process. When column generatetion procedure is performed, column (pattern) is iteratively added into the model (line 44 columnGeneration.py, which calls the function add_col in masterModel.py).

[yangliuxin-nn]

Many thanks for your time! That is very helpful!

[yangliuxin-nn]

Hello sir. Sorry for my bother again. If I print the "coe" of the line 44 columnGeneration.py using the provided data.txt, it prints the following:

[[1, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1], [1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0], [1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0], [1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0]]

[[0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1], [0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0]]

[[0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0], [0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0]]

1. Why does it print out nine coe in total, but the optimal and feasible solution finally given is six? Could you please explain what each item in each coe list means?
2. There are 10 items in the provided data.txt. Why the pattern/column is composed of 13 elements?
3. Another question is that given the order of the items in the data.txt, since the first item in the first coe list is [1, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1], can I add the weight of each item in the data.txt in which its value is 1 and get the sum less than the capacity of the bin?

[shaoxiang-zheng]

emmm... how about wechart?

[yangliuxin-nn]

Thank you! My WeChat id is Happyxinxin822