Local branching: Difference between revisions
| Line 3: | Line 3: | ||
== Introduction == | == Introduction == | ||
Mixed-Integer Linear Programming (MILP) is a sophisticated optimization model aimed at solving problems that involve both discrete decision and continuous variables, where the discrete variables are often constrained to take on integer values<ref name="LoC">. Local Branching is a heuristic that has been explicitly developed to enhance the effectiveness of solving MILP problems by focusing the optimization search in a defined neighborhood around the current incumbent solution. This approach has special advantages for large-scale, computationally intensive MILP instances because it allows one to explore the solution space in a more focused manner, improving the solution quality while still keeping the computations tractable. | Mixed-Integer Linear Programming (MILP) is a sophisticated optimization model aimed at solving problems that involve both discrete decision and continuous variables, where the discrete variables are often constrained to take on integer values<ref name="LoC"> Fischetti, M., & Lodi, A. (2003). Local branching. Mathematical Programming, 98(1), 23–47. https://doi.org/10.1007/s10107-003-0395-5</ref>. | ||
Local Branching is a heuristic that has been explicitly developed to enhance the effectiveness of solving MILP problems by focusing the optimization search in a defined neighborhood around the current incumbent solution. This approach has special advantages for large-scale, computationally intensive MILP instances because it allows one to explore the solution space in a more focused manner, improving the solution quality while still keeping the computations tractable. | |||
Furthermore, local branching was introduced as a refinement heuristic for dealing with the computational tractability issues that global optimization methods, such as branch-and-bound, became widely resource-consuming for large instances of a problem. One of the main motivations to study Local Branching is its ability to do iterative solution improvement, thereby making it possible to get good solutions fast with MILP solvers. Thus, local branching becomes extremely important when applied to domains demanding quick and reliable decision-making, more precisely within logistics optimization, production scheduling, and resource planning. | Furthermore, local branching was introduced as a refinement heuristic for dealing with the computational tractability issues that global optimization methods, such as branch-and-bound, became widely resource-consuming for large instances of a problem. One of the main motivations to study Local Branching is its ability to do iterative solution improvement, thereby making it possible to get good solutions fast with MILP solvers. Thus, local branching becomes extremely important when applied to domains demanding quick and reliable decision-making, more precisely within logistics optimization, production scheduling, and resource planning. | ||
Revision as of 13:55, 15 December 2024
Author: Bruce Wang (bw549), Ashley Yang (yy2333), Pufan You (py234), Sandro Xu (sx289), Yihan Wang (yw2744) (ChemE 6800 Fall 2020)
Introduction
Mixed-Integer Linear Programming (MILP) is a sophisticated optimization model aimed at solving problems that involve both discrete decision and continuous variables, where the discrete variables are often constrained to take on integer values[1].
Local Branching is a heuristic that has been explicitly developed to enhance the effectiveness of solving MILP problems by focusing the optimization search in a defined neighborhood around the current incumbent solution. This approach has special advantages for large-scale, computationally intensive MILP instances because it allows one to explore the solution space in a more focused manner, improving the solution quality while still keeping the computations tractable.
Furthermore, local branching was introduced as a refinement heuristic for dealing with the computational tractability issues that global optimization methods, such as branch-and-bound, became widely resource-consuming for large instances of a problem. One of the main motivations to study Local Branching is its ability to do iterative solution improvement, thereby making it possible to get good solutions fast with MILP solvers. Thus, local branching becomes extremely important when applied to domains demanding quick and reliable decision-making, more precisely within logistics optimization, production scheduling, and resource planning.
Algorithm Discussion
Numerical Examples
Application
Conclusion
References
- ↑ Fischetti, M., & Lodi, A. (2003). Local branching. Mathematical Programming, 98(1), 23–47. https://doi.org/10.1007/s10107-003-0395-5
Stewards: Nathan Preuss, Wei-Han Chen, Tianqi Xiao, Guoqing Hu