Originally posted by: Paul Shaw
Hello,
Let's assume you are minimizing some integer function f of your problem P. Upper bounds
are found by finding solutions to P. For any solution s, f(s) is an upper bound on problem P.
The lowest upper bound is equal to f(s*), where s* is an optimal solution of P.
One traditional way of tighening lower bounds on f is through successive proofs of
insolubility. Suppose you have an existing lower bound l calculated through some
naive method. This means you know that there is no solution s' with f(s') < l. To
tighten l, you can then try to find a solution to the problem (P && f <= l). If this
problem is insoluble, then you can tighten the lower bound to l + 1 (in the integer
case) since you now know that no solution exists with f < l + 1.
Regards,
Paul
#ConstraintProgramming-General#DecisionOptimization