0
$\begingroup$

The specific linear programme has an optimal solution as $x_1 = 0.66$, $x_2 = 1.33$, $x_3 = 12.2$, $x_4 = 0.0$ and the objective value is $33.3$. While the problem is solved by D-W decomposition method, in the specific iteration (defining two sub-problems in which, $x_1$ and $x_2$ are defined in the first and the rest are in the second), reduced cost of the second sub-problem is zero and the first has a negative reduced cost.

When we add columns based on the reduced cost, the objective value of the master problem will be $33.3$ and convergence has been attained. The solutions of the problem by using D-W are $x_1 = 0.66$, $x_2 = 1.33$, $x_3 = 8$, $x_4 = 0.0$.

The small example of the problem is: \begin{equation}\begin{array}{rrrrrr} \text { Minimize } & -x_{1} & - & 2 x_{2} & +3 x_{3} & +x_{4} & \\ \text { subject to } & x_{1} & + & 2 x_{2} & +3 x_{3} & +x_{4} & \geq 40 \\ & x_{1} & + & x_{2} & & & \leq 2 \\ & -x_{1} & + & 2 x_{2} & & & \leq 2 \\ & & & x_{3} & + & x_{4} & \geq 8 \\ & x_{1}, & & x_{2}, & x_{3}, & x_{4} \geq 0 \end{array}\end{equation}

I'm wondering if,

  • What is the reason(s) to obtain the different value of the variable $x_3$?
  • Is there any specific issue to deal with the sub-problem with zero reduced cost while another has a negative value?
Improve this question
$\endgroup$
4
  • $\begingroup$ Related question : or.stackexchange.com/questions/3428/… $\endgroup$
    – Kuifje
    Jun 19, 2020 at 11:27
  • $\begingroup$ @Kuifje, thanks so much. In my specific case, the problem was solved by WD method and convergence was attained. All of the sub-problems cannot produce any negative reduced cost and what I'm trying to know is, What is the reason(s) to obtain the different value of the variable $X_3$. $\endgroup$
    – A.Omidi
    Jun 19, 2020 at 13:27
  • $\begingroup$ The second solution you mention does not equal 33.3, but 20.68, so there is an improvement in the master problem's value ; $x$ values have changed and yield a better solution. The fact that one subproblem had 0 reduced cost does not prove convergence as stated by Marco Lübbecke. $\endgroup$
    – Kuifje
    Jun 19, 2020 at 13:47
  • $\begingroup$ @Kuifje, thanks. The second solution mentioned is about the master problem optimal solution, not the original problem. In the last iteration, both sub-problems do not produce negative reduced cost and convergence was attained. This is why I need to know the difference between the values of the variable $x_3$. I just tried another example and the problem is solved optimality by using DW method but in this case, there is an issue!!! $\endgroup$
    – A.Omidi
    Jun 19, 2020 at 20:47

1 Answer 1

Reset to default
2
$\begingroup$

It would help to see the entire model (I assume $c_3=0$?); when I understand correctly (first question) you have multiple optimal solutions (which happens) and the algorithm needs to iterate until optimality is proven (which apparently was not the case yet). In that sense there is no "reason" for a different value of $x_3$. Column generation terminates when all subproblems return that their minimum reduced cost is non-negative (second question).

Improve this answer
$\endgroup$
1
  • $\begingroup$ Many thanks for your response. I just updated the question. I should say that I try to use SCIP to achieve all multiple optimal solutions and It shows there are no multiple solutions. Would you say please, where I am wrong and how can I fix this issue? Thanks once again $\endgroup$
    – A.Omidi
    Jun 19, 2020 at 13:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.