Stay organized with collections
Save and categorize content based on your preferences.
C++ Reference: class LbTreeSearch
Note: This documentation is automatically generated.
Implement a "classic" MIP tree search by having an exhaustive list of open
nodes.
The goal of this subsolver is to improve the objective lower bound. It is
meant to be used in a multi-thread portfolio, and as such it really do not
care about finding solution. It is all about improving the lower bound.
TODO(user): What this is doing is really similar to asking a SAT solver if
the current objective lower bound is reachable by solving a SAT problem.
However, this code handle on the side all the "conflict" of the form
objective > current_lb. As a result, when it is UNSAT, we can bump the lower
bound by a bigger amount than one. We also do not completely loose everything
learned so far for the next iteration.
[[["Easy to understand","easyToUnderstand","thumb-up"],["Solved my problem","solvedMyProblem","thumb-up"],["Other","otherUp","thumb-up"]],[["Missing the information I need","missingTheInformationINeed","thumb-down"],["Too complicated / too many steps","tooComplicatedTooManySteps","thumb-down"],["Out of date","outOfDate","thumb-down"],["Samples / code issue","samplesCodeIssue","thumb-down"],["Other","otherDown","thumb-down"]],["Last updated 2024-08-06 UTC."],[[["\u003cp\u003eLbTreeSearch is a subsolver in OR-Tools designed to improve the objective lower bound in Mixed Integer Programming (MIP) problems.\u003c/p\u003e\n"],["\u003cp\u003eIt functions by exhaustively exploring open nodes in the search tree, similar to a SAT solver, but focuses solely on lower bound improvement.\u003c/p\u003e\n"],["\u003cp\u003eUpon determining unsatisfiability, it can increase the lower bound by more than one unit and retains learned information for subsequent iterations.\u003c/p\u003e\n"],["\u003cp\u003eIt is intended for multi-thread portfolio use and does not prioritize finding solutions.\u003c/p\u003e\n"],["\u003cp\u003eKey methods include LbTreeSearch for initialization and Search for exploration of the search space.\u003c/p\u003e\n"]]],["The `LbTreeSearch` class in C++ implements a MIP tree search focused on improving the objective lower bound. It maintains an exhaustive list of open nodes and operates within a multi-threaded portfolio. The core functionality is in the `Search` method, which explores the search space, and it also handles conflicts related to the objective lower bound, potentially allowing for larger increments to the bound than just one. It does not care about finding solution. The constructor takes a pointer to the `Model` as argument.\n"],null,["# LbTreeSearch\n\nC++ Reference: class LbTreeSearch\n=================================\n\n\nNote: This documentation is automatically generated.\nImplement a \"classic\" MIP tree search by having an exhaustive list of open nodes. \n\nThe goal of this subsolver is to improve the objective lower bound. It is meant to be used in a multi-thread portfolio, and as such it really do not care about finding solution. It is all about improving the lower bound. \n\nTODO(user): What this is doing is really similar to asking a SAT solver if the current objective lower bound is reachable by solving a SAT problem. However, this code handle on the side all the \"conflict\" of the form objective \\\u003e current_lb. As a result, when it is UNSAT, we can bump the lower bound by a bigger amount than one. We also do not completely loose everything learned so far for the next iteration.\n\n| Method ||\n|-------------------------------------------------------------------------------------------------|------------------------------------------------------------------------------------------------------------------------------------|\n| [`LbTreeSearch`](https://github.com/google/or-tools/blob/v9.4/ortools/sat/lb_tree_search.h#L59) | Return type: `explicit ` Arguments: `Model* model` \u003cbr /\u003e |\n| [`Search`](https://github.com/google/or-tools/blob/v9.4/ortools/sat/lb_tree_search.h#L62) | Return type: `SatSolver::Status ` Arguments: ` const std::function\u003cvoid()\u003e& feasible_solution_observer` Explores the search space. |"]]
