stephenjmaher
commented
4 years ago This question appears to be both about the theoretical aspects of column generation and the implementation details. Since #395 was about branch-and-price, I am assuming that your question is focused on using the LP dual solution for generating columns.
First, could you please clarify what you mean by
The behavior of SCIP is not normal.
What is the reference state for this statement? Also, what behaviour do you think is not normal for mixed integer programming solvers.
When applying column generation, it is best if you can specify binary variables as integer variables without an upper bound. This avoids the need to handle the variable upper bound.
For constraints such as lhs <= Exp <= rhs, you don't need to be concerned about checking both sides of the constraint to identify the dual solution. From theory, for a minimisation problem
- if
Exp = rhsthen the dual value will be negative - if
Exp = lhsthen the dual value will be positive - if
lhs < Exp < rhs, then the dual value is zero. For a linear constraint, if you callgetDualsolLinear, the appropriate dual value will be returned.
What do you mean by
Also, the sign of the reduced cost is not fixed.
For minimisation problems, a column with a negative reduced cost will improve the LP objective of the restricted master problem. For maximisation problems, a column with a positive reduced cost will improve the LP objective of the restricted master problem. For both minimisation and maximisation problems, some columns will have a positive reduced cost and some will have a negative reduced cost.
In regards to
Is there any reference that I can read to figure out how the SCIP deals with the dual variables? The best literature is standard literature on linear programming.
The case of SCIP imposing an upper bound on an integer variable. It is best to disable propagations and also disable dual reductions to avoid this situation.
What's more, there are many papers relaxing the constraint
0 <= x <= 1tox >= 0with respected to binary variable x in order to avoid dealing with the dual variables associated withx <= 1. I guess SCIP cannot handle this task, i.e., usingx >= 0to derive dual bound while usingx = 0or1to derive the primal bound. Is it right?
You can most certainly achieve what you are asking in SCIP. You need to define x as an integer variable without an upper bound. Then you include a linear constraint x <= 1. You can query the constraint x <= 1 for the dual values associated with the upper bound.
mattmilten
Hi @fserra, sorry for making issue #395 so long and leaving problems that is not relevant to the topic. So I open this new issue.
I realize that the three constraints in #395 imply that all decision variables can not be larger than one. Hence, I can just define them as integer variables (instead of binary variables) and the dual solutions are correct. So when the constraints are like
lhs <= Exp <= rhs, how is the dual solution calculated? It seems like we have to check the both sides and the sign of the dual solution is not fixed (non-positive or non-negative). Also, the sign of the reduced cost is not fixed. In the canonical form of a LP (i.e., minimization, and>=constraints), the signs of dual solutions are non-negative, the reduced costs of basic variables are zeros and the reduced costs of non-basic variables are non-negative. The behavior of SCIP is not normal. Is there any reference that I can read to figure out how the SCIP deals with the dual variables?Besides, I am wondering that if an upper bound
x <= 1is automatically imposed by SCIP when solving the linear relaxation problem, how can we obtain the dual solution associated with the implicit constraintx <= 1directly?What's more, there are many papers relaxing the constraint
0 <= x <= 1tox >= 0with respected to binary variablexin order to avoid dealing with the dual variables associated withx <= 1. I guess SCIP cannot handle this task, i.e., usingx >= 0to derive dual bound while usingx = 0 or 1to derive the primal bound. Is it right?Thank you.