4 stars based on
I have a quick question. If one of variables is a binary variable 0 or 1 and the others are linear and continuous, then what is the dual constraint of the binary variable? The theory of linear programming duality simply doesn't apply to mixed binary variable constraint 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.
Binary variable constraint you for your answer, Brian Borchers. I have a problem that has some 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? You would have to formulate your decomposition so that the binary variables were all in the master problem.
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. I guess RLT is a technique that removes all binary variables from the subproblem, right? Oh, I am so sorry to confuse all of you. As I read my question again, I said some binary variables binary variable constraint objective, then, all binary variables in objective binary variable constraint is correct.
Decomposition algorithms with parametric Gomory cuts for two-stage 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. Thank you for your comment, thunderain. I got your binary variable constraint 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? RLT as far as I know is a general purpose tool, the performance is highly dependent on the formulation and how binary variable constraint do the RLT. That paper has nothing to do with RLT in my opinion. Thank you very much, thunderain! 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 binary variable constraint any technique to linearize approximately or exactly the binary variables? What sort of decomposition are you doing? In Dantzig-Wolfe, 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. I have transformed all integer variables that I have to the subproblem, however, there is a binary variable that Binary variable constraint cannot transform it.
I am wondering if there is anyway to have a linear approximation reformulation of a binary variable. Morad, I first tried to use a convexification method Reformulation-Linearization Technique RLTand 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.
On solving discrete two-stage stochastic programs having mixed-integer first- and second-stage variables. Mathematical Programming, vnpJuly 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 binary variable constraint to implement binary variable constraint me, I implemented with C having concert tech CPLEX.
So, if you should guarantee the optimum, then Binary variable constraint would be better, but if you can use heuristic, Progressive hedging is a good option. 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. Thanks Paul, By doing some reformulation according to the special structure of the problem, my problem had been solved thanks again.
Visualizing the dual problem. Valid solution to integer program. What will happen binary variable constraint dual problem if lower bound of primal variables is positive? Find the optimal solution without going through the ERO's. If the primal is unbounded, then the dual is infeasible. Dual value of equality constraint.
Conditions for Linear Programming Optimizing at a Point. Prove optimal solution to dual is not unique if optimal solution to the primal is degenerate and unique? Dual constraint of binary variable?
Hi, I have a problem almost similar to your case. 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?
I got it now. I am using Dantizig-Wolfe decomposition. Binary variable constraint is why I was confused. Binary variable constraint this question By Email: Once you sign in you will be able to subscribe for any updates here By RSS: Answers Answers and Comments.
Bar to add a line break simply add two spaces to where binary variable constraint would like the new line to be.
Related questions Visualizing the dual problem Valid solution to integer program What will happen in dual problem if lower bound of primal variables is positive? Binary variable constraint the optimal solution without going through the ERO's If the primal is unbounded, then the dual is infeasible. Your site for questions, answers, and announcements about operations research. Check out the FAQ! I am wondering if there is anyway binary variable constraint have a linear approximation reformulation of a binary variable 09 May '13,