# When decomposing problems via lagrangean relaxation, do I need to solve each subproblem separately?

 4 I have a MIP problem decomposed in two subproblems by lagrangian relaxation. One of them is MIP, the other completely continuous. I'm going to solve the main problem with a branch-and-bound algorithm coded in C, using the CPLEX solver on the subproblems to compute a dual bound, the question is solver-independent though. I have two ways to implement the dual bound computation: I) by creating and solving one model object for each subproblem, or II) creating just one model object for both and solving it at once. In this project (II) comes natural, in another project I preferred doing (I). Can this choice, in general, have any impact on the efficiency of the solver, apart from the chance of solving the two subproblems in parallel? TIA Andrea T. asked 05 Dec '11, 14:17 Andrea T 384●4●18 accept rate: 0% fbahr ♦ 4.6k●7●16

 2 If there are constraints unique to either subproblem, separate might be preferable (smaller dimensional basis matrices). answered 06 Dec '11, 17:26 Paul Rubin ♦♦ 14.6k●5●13 accept rate: 19%
 0 There are such methods like the Interleaved method which is a spacial case of the Surrogate Lagrangian Relaxation method that allows solving only one sub-problem at a time before updating multipliers. answered 11 Sep '14, 16:27 Mikhail Bragin 11●2 accept rate: 0%
 toggle preview community wiki

### Follow this question

By Email:

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

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:

Asked: 05 Dec '11, 14:17

Seen: 3,352 times

Last updated: 11 Sep '14, 16:27

### Related questions

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