# Dual constraint of binary variable?

 1 1 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? Thanks in advance. asked 01 Feb '13, 01:09 Gitae 100●2●5 accept rate: 0% fbahr ♦ 4.5k●5●15

 8 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 1.2k●1●5 accept rate: 16% Thank you for your answer, Brian Borchers. I have a problem that has some 0-1 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
 2 Check this out: 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. answered 01 Feb '13, 11:05 thunderain 121●4 accept rate: 0% 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
 toggle preview community wiki

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "Title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported

Tags: