Tree decomposition and postoptimality analysis in discrete optimization

Details Tree decomposition and postoptimality analysis in discrete optimization Tree decomposition and postoptimality analysis in discrete optimization

2009-03-25

arxiv.org/abs/0903.4435v1

Computer Science

Discrete Mathematics

19 pages, 5 fugures

Scientific paper

Many real discrete optimization problems (DOPs) are $NP$-hard and contain a huge number of variables and/or constraints that make the models intractable for currently available solvers. Large DOPs can be solved due to their special tructure using decomposition approaches. An important example of decomposition approaches is tree decomposition with local decomposition algorithms using the special block matrix structure of constraints which can exploit sparsity in the interaction graph of a discrete optimization problem. In this paper, discrete optimization problems with a tree structural graph are solved by local decomposition algorithms. Local decomposition algorithms generate a family of related DO problems which have the same structure but differ in the right-hand sides. Due to this fact, postoptimality techniques in DO are applied.

Affiliated with

Also associated with

No associations

Rating

Tree decomposition and postoptimality analysis in discrete optimization does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Tree decomposition and postoptimality analysis in discrete optimization, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Tree decomposition and postoptimality analysis in discrete optimization will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-63647