Solves the maximum clique problem to global optimality by solving the mixed-integer program.
Maximize ∑ᵢ xᵢ subject to xᵢ + xⱼ ≤ 1 if (i,j) is not in the edge xᵢ ∈ {0,1}.
Note: This solver requires the availability of a Mixed-Integer Linear Programming solver (e.g. Gurobi and/or Mosek). We recommend enabling those solvers if possible (https://drake.mit.edu/bazel.html#proprietary_solvers).
std::exception | if no Mixed-Integer Linear Programming solver is available. |
std::exception | if the initial guess has the wrong size for the provided adjacency matrix. |
#include <drake/planning/graph_algorithms/max_clique_solver_via_mip.h>
Public Member Functions | |
MaxCliqueSolverViaMip ()=default | |
MaxCliqueSolverViaMip (const std::optional< Eigen::VectorXd > &initial_guess, const solvers::SolverOptions &solver_options) | |
void | SetSolverOptions (const solvers::SolverOptions &solver_options) |
solvers::SolverOptions | GetSolverOptions () const |
void | SetInitialGuess (const std::optional< Eigen::VectorXd > &initial_guess) |
std::optional< Eigen::VectorXd > | GetInitialGuess () const |
Implements CopyConstructible, CopyAssignable, MoveConstructible, MoveAssignable | |
MaxCliqueSolverViaMip (const MaxCliqueSolverViaMip &)=default | |
MaxCliqueSolverViaMip & | operator= (const MaxCliqueSolverViaMip &)=default |
MaxCliqueSolverViaMip (MaxCliqueSolverViaMip &&)=default | |
MaxCliqueSolverViaMip & | operator= (MaxCliqueSolverViaMip &&)=default |
Public Member Functions inherited from MaxCliqueSolverBase | |
virtual | ~MaxCliqueSolverBase () |
VectorX< bool > | SolveMaxClique (const Eigen::SparseMatrix< bool > &adjacency_matrix) const |
Given the adjacency matrix of an undirected graph, find the maximum clique within the graph. More... | |
Additional Inherited Members | |
Protected Member Functions inherited from MaxCliqueSolverBase | |
MaxCliqueSolverBase ()=default | |
MaxCliqueSolverBase (const MaxCliqueSolverBase &)=default | |
MaxCliqueSolverBase & | operator= (const MaxCliqueSolverBase &)=default |
MaxCliqueSolverBase (MaxCliqueSolverBase &&)=default | |
MaxCliqueSolverBase & | operator= (MaxCliqueSolverBase &&)=default |
|
default |
|
default |
|
default |
MaxCliqueSolverViaMip | ( | const std::optional< Eigen::VectorXd > & | initial_guess, |
const solvers::SolverOptions & | solver_options | ||
) |
std::optional<Eigen::VectorXd> GetInitialGuess | ( | ) | const |
solvers::SolverOptions GetSolverOptions | ( | ) | const |
|
default |
|
default |
void SetInitialGuess | ( | const std::optional< Eigen::VectorXd > & | initial_guess | ) |
void SetSolverOptions | ( | const solvers::SolverOptions & | solver_options | ) |