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's gravatar image

Gitae
2113
accept rate: 0%

edited 11 Dec '13, 08:08

fbahr's gravatar image

fbahr ♦
3.5k313


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.

link

answered 01 Feb '13, 09:02

Brian%20Borchers's gravatar image

Brian Borchers
1.1k15
accept rate: 17%

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

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.

link

answered 01 Feb '13, 11:05

thunderain's gravatar image

thunderain
1214
accept rate: 0%

edited 01 Feb '13, 11:23

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?

link

answered 09 May '13, 14:09

Morad's gravatar image

Morad
434
accept rate: 0%

2

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.

(09 May '13, 15:44) Paul Rubin ♦

I got it now. I am using Dantizig-Wolfe 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 Reformulation-Linearization 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 two-stage stochastic programs having mixed-integer first- and second-stage variables. Mathematical Programming, v 108, n 2-3, p 597-616, 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
Your answer
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "Title")
  • 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:

×96
×6

Asked: 01 Feb '13, 01:09

Seen: 1,279 times

Last updated: 11 Dec '13, 08:08

OR-Exchange! Your site for questions, answers, and announcements about operations research.