Hi,

I have minimisation MIP problem in which I previously compute a valid feasible solution and a valid lower bound to the optimal solution. Naively I could add the feasible solution as a warm start and add a constraint:

Obj >= valid lower bound

This makes the initial linear relaxation on the first node have the same value as the valid lower bound. However, it doesn't help the search tree. Node after node gets stuck in the same lower bound.

Is there any way I can use a valid known lower bound to speed up the optimality proof of a MIP? Thanks!

asked 30 Mar, 01:05

Chicoscience's gravatar image

Chicoscience
111
accept rate: 0%

Do you mean "upper bound"? The value of a feasible solution to a minimization problem is an upper bound on the optimal objective value, not a lower bound.

(30 Mar, 09:31) Paul Rubin ♦♦

Dear Paul, thanks for the reply. I actually do mean lower bound. So by solving an approximation of the original problem I get a value that is guaranteed to be a lower bound on the optimal solution value - how I get that is not important now, what matters is that I do have a valid lower bound.

I would like somehow to help the solver finish its branch-and-bound procedure by giving it information about this known lower bound. Is that possible?

(30 Mar, 23:53) Chicoscience

Assuming that by "same lower bound" you mean the lower bound matches the bound you entered (let's call that \(z_0\)) for an extended period, that's not particularly surprising. At any given node of the search tree, the lower bound will be the max of \(z_0\) and whatever bound the solver would have gotten without knowing about \(z_0\). So there are probably a bunch of nodes where you've boosted the lower bound from something smaller to \(z_0\), and until every one of those nodes has been investigate, the lower bound isn't going anywhere.

Once the solver finds a feasible solution whose value is close enough to \(z_0\) (within your optimality tolerance), your lower bound will allow the search to terminate. Until that happens, I don't think it will have much effect on the solver.

link

answered 31 Mar, 11:09

Paul%20Rubin's gravatar image

Paul Rubin ♦♦
14.5k412
accept rate: 19%

Thanks Paul! That was my fear actually. I suppose that if I want to help guide the search path faster I need more than just a lower bound!

(31 Mar, 17:42) Chicoscience

Yes. Assuming that your objective is to prove optimality (not just get an optimal or near-optimal solution) faster, you need some combination of finding improved solutions faster or tightening the lower bound faster. Both are easy to say, hard to do. Sometimes an insight into the structure of the problem will let you tighten constraints locally or globally (e.g., by lift-and-project). Sometimes not.

(31 Mar, 18:04) Paul Rubin ♦♦
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:

×56
×14

Asked: 30 Mar, 01:05

Seen: 105 times

Last updated: 31 Mar, 18:04

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