Stay organized with collections
Save and categorize content based on your preferences.
C++ Reference: class HittingSetOptimizer
Note: This documentation is automatically generated.
Generalization of the max-HS algorithm (HS stands for Hitting Set). This is
similar to MinimizeWithCoreAndLazyEncoding() but it uses a hybrid approach
with a MIP solver to handle the discovered infeasibility cores.
[[["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\u003eHittingSetOptimizer is a generalization of the max-HS algorithm, similar to MinimizeWithCoreAndLazyEncoding but uses a hybrid approach with a MIP solver.\u003c/p\u003e\n"],["\u003cp\u003eIt's based on the research paper "Solving MAXSAT by Solving a Sequence of Simpler SAT Instances" by Jessica Davies and Fahiem Bacchus.\u003c/p\u003e\n"],["\u003cp\u003eThis approach was successful in the 2016 max-SAT competition, specifically in the industrial category.\u003c/p\u003e\n"],["\u003cp\u003eCurrently, it requires linking with the SCIP MIP solver, which is large and potentially needs optimization.\u003c/p\u003e\n"]]],["The `HittingSetOptimizer` class implements a hybrid approach, generalizing the max-HS algorithm, using a MIP solver to manage infeasibility cores. It is similar to `MinimizeWithCoreAndLazyEncoding`. This approach won the 2016 max-SAT competition in the industrial category. Key methods include `HittingSetOptimizer`, which initializes with model data and an observer, and `Optimize`, which performs the optimization and returns the solver status. The implementation is noted to require linking with the SCIP MIP solver.\n"],null,["# HittingSetOptimizer\n\nC++ Reference: class HittingSetOptimizer\n========================================\n\n\nNote: This documentation is automatically generated.\nGeneralization of the max-HS algorithm (HS stands for Hitting Set). This is similar to MinimizeWithCoreAndLazyEncoding() but it uses a hybrid approach with a MIP solver to handle the discovered infeasibility cores. \n\nSee, Jessica Davies and Fahiem Bacchus, \"Solving MAXSAT by Solving a Sequence of Simpler SAT Instances\", [http://www.cs.toronto.edu/\\~jdavies/daviesCP11.pdf](http://www.cs.toronto.edu/~jdavies/daviesCP11.pdf)\" \n\nNote that an implementation of this approach won the 2016 max-SAT competition on the industrial category, see \u003chttp://maxsat.ia.udl.cat/results/#wpms-industrial\u003e \n\nTODO(user): This class requires linking with the SCIP MIP solver which is quite big, maybe we should find a way not to do that.\n\n| Method ||\n|------------------------------------------------------------------------------------------------|------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|\n| [`HittingSetOptimizer`](https://github.com/google/or-tools/blob/v9.4/ortools/sat/max_hs.h#L60) | \u003cbr /\u003e Arguments: `const CpModelProto& model_proto, const ObjectiveDefinition& objective_definition, const std::function\u003cvoid()\u003e& feasible_solution_observer, Model* model` \u003cbr /\u003e |\n| [`Optimize`](https://github.com/google/or-tools/blob/v9.4/ortools/sat/max_hs.h#L65) | Return type: `SatSolver::Status ` \u003cbr /\u003e |"]]
