Filetype Power Point PPTX | Posted on 03 Sep 2022 | 3 years ago
Authentication
digital resources
179x Filetype PPTX File size 1.58 MB Source: www.cs.tau.ac.il
An example: Constrained Shortest Paths • Sh ortest paths with costs , times and time constraint T: Minimize Subject to: An example: Constrained Shortest Paths An example: Constrained Shortest Paths • Bo unding Principle For any nonnegative value of the toll μ, the length of the modified shortest path with costs minus μ T is a lower bound on the length of the constrained shortest path. Example for usefulness of bounds: Branch and bound in integer programming – on board Lagrangian relaxation technique • G eneric optimization model of problem P: Subject to: Lagrangian relaxation PL: Minimize Subject to: Lagrangian function: Lagrangian relaxation technique • La grangian Bounding Principle: For any vector μ of the Lagrangian multipliers, the value L(μ) of the Lagrangian function is a lower bound on the optimal objective function value z* of the original optimization problem (P) Proof:
no reviews yet
Please Login to review.
