The theory of linear programming duality simply doesn't apply to mixed integer linear programming problems. There have been various attempts at duality theories for integer programming problems, but the properties of the dual problem aren't nearly as nice for example you don't get a strong duality theorem saying that the optimal value of the dual problem equals the optimal value of the primal. Look up "Lagrangian Duality" for integer programming problems and "Subadditive Duality" as starting points. answered 01 Feb '13, 09:02 Brian Borchers Thank you for your answer, Brian Borchers. I have a problem that has some 01 variables in the objective funtion and constraints, all others are linear and continuous. It's two stage stochastic program. If I use Benders decomposition, how do I use that? Because the subproblem has binary variables. Should I use some tricks to substitute binary variables into continuous variable?
(01 Feb '13, 10:19)
Gitae
4
You would have to formulate your decomposition so that the binary variables were all in the master problem.
(01 Feb '13, 16:02)
Paul Rubin ♦
Thank you, Paul Rubin. But, all the variables in the objective function are binary. Some constraints have binary. So, it is difficult to have all the binary variables in the master problem. Now, although I haven't used it yet, I am thinking of Reformulation Linearization Technique (RLT) to figure it out. I guess RLT is a technique that removes all binary variables from the subproblem, right?
(04 Feb '13, 00:42)
Gitae
Oh, I am so sorry to confuse all of you. As I read my question again, I said some binary variables in objective, then, all binary variables in objective (this is correct).
(04 Feb '13, 00:51)
Gitae

Check this out: Decomposition algorithms with parametric Gomory cuts for twostage stochastic integer programs and the reference therein. This is a challenging problem and Benders simply does not apply here, you have to make some relaxation to apply Benders. answered 01 Feb '13, 11:05 thunderain 1
@thunderain Your answer is blank this is probably because you tried to include a "naked URL" in the answer, and the software that runs the web site doesn't allow this.
(01 Feb '13, 11:21)
Brian Borchers
Thank you for your comment, @thunderain. I got your link (the paper in MP journal). I didn't read the paper yet, but is that a type of RLT? If not, which one is better in terms of performance and implementation?
(04 Feb '13, 00:47)
Gitae
RLT as far as I know is a general purpose tool, the performance is highly dependent on the formulation and how you do the RLT. That paper has nothing to do with RLT in my opinion.
(06 Feb '13, 10:30)
thunderain
Thank you very much, @thunderain !
(07 Feb '13, 21:29)
Gitae

Hi, I have a problem almost similar to your case. When I read the answers, I see that Paul mentioned that you should keep all binary variables in the master problem. I couldn't understand this, because if you keep binary variables in the master problem then you could not have dual information to use in subproblem and in fact I think that all binary variables should be transformed to the subproblem and all continuous variables in the master problem By the way, did you find any technique to linearize (approximately or exactly) the binary variables? answered 09 May '13, 14:09 Morad 2
What sort of decomposition are you doing? In DantzigWolfe, the dual solution to the master problem is used to create the objective in the subproblem. In Benders, the dual solution to the subproblem is used to create cuts in the master. In his first comment to Brian's answer, Gitae mentioned Benders.
(09 May '13, 15:44)
Paul Rubin ♦
I got it now. I am using DantizigWolfe decomposition. That is why I was confused. I have transformed all integer variables that I have to the subproblem, however, there is a binary variable that I cannot transform it. I am wondering if there is anyway to have a linear approximation(reformulation) of a binary variable
(09 May '13, 16:27)
Morad
1
Morad, I first tried to use a convexification method ReformulationLinearization Technique(RLT), and I tried to implemented the method, but the model becomes complicated and takes much time to finish the implementation even if I used an efficient method from a reference paper (Sherali, Hanif D., Zhu, Xiaomei. On solving discrete twostage stochastic programs having mixedinteger first and secondstage variables. Mathematical Programming, v 108, n 23, p 597616, July 2006).
(09 May '13, 23:04)
Gitae
2
So, we decided to use the method later, and use another way. Now, I used Progressive Hedging method that is a heuristic but doesn't need any convexification scheme and also easy to implement (for me, I implemented with C# having concert tech CPLEX). So, if you should guarantee the optimum, then RLT would be better, but if you can use heuristic, Progressive hedging is a good option.
(09 May '13, 23:04)
Gitae
Thanks a lot Gitae, Interesting option
(10 May '13, 11:31)
Morad
1
@Morad: If you have only a single variable, just solve the problem twice, once with it set to zero and once with it set to one.
(11 May '13, 17:25)
Paul Rubin ♦
Thanks Paul, By doing some reformulation according to the special structure of the problem, my problem had been solved thanks again
(11 May '13, 19:35)
Morad
showing 5 of 7
show 2 more comments
