I want to decompose my MILP problem into N(N>0) problems with each corresponding node but my constrain includes the dependent term(this term has other node's information).

How can I do to separate my problem?

Thank everyone!!!!

asked 08 Sep '17, 10:56

alan2610107's gravatar image

accept rate: 0%

Can you clarify what you mean? In particular, when you say "node", are you referring to a node in the MILP search tree or a node in some graph underlying your problem? Also, what do you mean by "dependent term"?

(08 Sep '17, 11:00) Paul Rubin ♦♦

Node is like a location but the location can be influenced by others which around it in my constraint

(08 Sep '17, 11:10) alan2610107

If the individual subproblems (I assume they are MILPs themselves) solve quickly (but are not too easy), you can use Lagrangian relaxation within a branch-and-cut framework to tighten bounds. You solve the full problem via branch-and-cut. At each node of the search tree, you calculate the LP bound as usual. Next, you relax the linking constraints (the ones connecting subproblems) by multiplying them by positive multiplier values (initially arbitrary) and moving the products into the objective function. Solve each subproblem and stitch the results together to get an objective value for the relaxed full problem. Adjust the multipliers based on which linking constraints have slack and which are violated, and repeat a few times. The resulting objective values are all bounds on the original objective; if the final bound is tighter than the LP bound, use it in place of the LP bound, hoping that tighter bounds during the branch-and-cut search compensate for all the time spent repeatedly solving the MILP subproblems.

It may also be possible to apply a variant of Benders decomposition, in which the master problem contains any variables not belonging to exactly one of the subproblems and any constraints involving only those variables. You solve the master problem via branch-and-cut. Every time the solver thinks it has an integer feasible incumbent solution, you fix the values of the master problem variables that appear in the subproblems, solve each subproblem, and see if they are all feasible. Normally, Benders uses LP subproblems and uses dual solutions to generate either feasibility cuts (because the alleged master incumbent was actually infeasible) or optimality cuts (because the master incumbent was feasible but not as good in objective terms as the master problem indicated it was). With MILP subproblems, you don't have dual solutions, so barring some specific structure you can exploit, you may be limited to what are sometimes called "no good" feasibility cuts (rejecting the proposed incumbent but only the proposed incumbent).

If you are willing to entertain a heuristic solution, you can also try column generation, along the lines of the Gilmore-Gomory heuristic for the cutting stock problem (too lengthy for me to explain here).


answered 08 Sep '17, 14:31

Paul%20Rubin's gravatar image

Paul Rubin ♦♦
accept rate: 19%

Thank you very much!!!! You help me a lot!!!!


answered 09 Sep '17, 10:57

alan2610107's gravatar image

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



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



Asked: 08 Sep '17, 10:56

Seen: 387 times

Last updated: 09 Sep '17, 10:57

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