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

Andrea T
384418
accept rate: 0%

retagged 05 Dec '11, 15:19

fbahr's gravatar image

fbahr ♦
4.6k716


If there are constraints unique to either subproblem, separate might be preferable (smaller dimensional basis matrices).

link

answered 06 Dec '11, 17:26

Paul%20Rubin's gravatar image

Paul Rubin ♦♦
14.6k412
accept rate: 19%

It depends on the constraints you've relaxed using Lagrangian relaxation. If these constraints are linking the two resulting subproblems, then solving each subproblem separately is the same as simultaneously solving both subproblems as two subproblems share no similar decision variables. However, even after relaxing the constraints, the two subproblems still share some common variables, then you would have just one problem to solve, not two subproblems.

link

answered 06 Dec '11, 06:25

Ehsan's gravatar image

Ehsan ♦
4.8k31122
accept rate: 16%

Side question on wording: I thought the first situation (disjointed suproblems) was implied by the term "decomposed" I used above, was I wrong? Anyway, yes, the two subproblems are effectively separated.Hence am I able to assume there are no penalties on encoding the subproblems in the same model object?

(06 Dec '11, 09:57) Andrea T

I asked that to make sure there's no error in formulating the Lagrangian dual.

I think since your joint model, including both subproblems, is poorly-formulated due to presence of two unrelated problem, it might cause some overhead for the solver. The amount of overhead is related to the efficiency of pre-processing techniques employed by the solver. In addition, it seems not possible for the solvers to identify unrelated subproblems in order to allocate them different CPUs. Perhaps, people with solver implementation experience could answer your question better.

(06 Dec '11, 10:34) Ehsan ♦

But from a practical point of view, I prefer separate model implementation. As your problem size increases, your joint model would require more memory which makes it hard to solve on computers with limited computational power. However, the separate models might still be solvable on the same computer.

(06 Dec '11, 10:35) Ehsan ♦

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.

link

answered 11 Sep '14, 16:27

Mikhail%20Bragin's gravatar image

Mikhail Bragin
112
accept rate: 0%

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:

×71
×14
×11
×9

Asked: 05 Dec '11, 14:17

Seen: 3,247 times

Last updated: 11 Sep '14, 16:27

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