Feeding lower bounds as >= constraints to MIP solvers...

 1 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 ♦ 4.6k●7●17 accept rate: 13% 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 ♦

 2 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. answered 16 Nov '16, 15:33 Paul Rubin ♦♦ 14.6k●5●13 accept rate: 19%
 toggle preview community wiki

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• 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