CODEWITHSUNDEEP
cplexconstraint-programmingoplcp-optimizer
Alex
Alex

Reputation: 81

How is the lower bound that is displayed created?

my Flexible Job Shop Problem (CP) shows me a result of Best objective :423 (gap is 49,88%) and Best bound: 212. So my question is how is this bound created? Because In my case the lowest value that can be theoretical achived is in the area of about 400. Thank you in advance

Upvotes: 1

Views: 404

Answers (1)

Philippe Laborie
Philippe Laborie

Reputation: 446

The (lower) bound computed by CP Optimizer is the aggregation of several bounds (initial propagation at the root node, linear relaxation, etc.). In the case of a flexible jobshop problem, you can probably improve this lower bound by strengthening the formulation with redundant cumul functions (typically: if you have m machines, have a single cumul function 'nbUsedMachines' that is the sum of a pulse('op',1) by all the operations 'op' of the problem, and posting nbUsedMachines<=m). This will probably not improve very much the upper-bound/solutions but may positively impact the lower bound value.

Upvotes: 4

Related Questions