Given a MIP problem that aims at minimizing some objective function [actually: think of the TSP] and some lower bound that's valid for all optimal solutions: for what (technical?) reason[s] wouldn't you feed this bound as ">=" constraint to your [favo(u)rite] MIP solver [Gurobi, CPLEX, ...]?

asked 15 Nov '16, 15:13

fbahr's gravatar image

fbahr ♦
4.6k716
accept rate: 13%

edited 15 Nov '16, 15:18

1

I remember trying this for some problems (feeding the best lower bound of a previous run as a new constraint on the objective function value), but saw no effect on CPU time. I'm not sure whether this is a general observation or something by accident.

(15 Nov '16, 22:47) Ehsan ♦
2

Quick comment : It has pros and cons and is model dependent. A few things come to mind on the pros side. It may provide extra bound tightenings for presolve, which can help make further reductions and also help dual simplex in node solves. Further more nodes can be found LP infeasible with this constraint and feasible without i.e nodes might be pruned faster. On the cons side, adding an extra constraint parallel with the objective might be a bad idea as Paul mention. Also the objective is often relative dense compared to constraints, so we might make node solves more dense for no gain.

(16 Nov '16, 18:35) Bo Jensen ♦

If your objective function is a single variable, feel free to enter it as a lower bound on the variable. Otherwise, the danger is that you add a constraint parallel to the objective function, which I think introduces dual degeneracy.

link

answered 16 Nov '16, 15:33

Paul%20Rubin's gravatar image

Paul Rubin ♦♦
14.6k412
accept rate: 19%

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:

×191
×71
×56
×26
×22

Asked: 15 Nov '16, 15:13

Seen: 779 times

Last updated: 16 Nov '16, 18:35

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