discrete_optimization.maximum_independent_set.solvers package

Submodules

discrete_optimization.maximum_independent_set.solvers.asp module

class discrete_optimization.maximum_independent_set.solvers.asp.AspMisSolver(problem: Problem, params_objective_function: ParamsObjectiveFunction | None = None, **kwargs: Any)

Bases: MisSolver, AspClingoSolver

build_data_string()

init_model(**kwargs: Any) → None

Initialize internal model used to solve.

Can initialize a ortools, milp, gurobi, … model.

retrieve_solution(model: Model) → MisSolution

Construct a do solution from a clingo model.

Parameters:

model – the current constructed clingo model

Returns:

the intermediate solution, at do format.

discrete_optimization.maximum_independent_set.solvers.cpsat module

class discrete_optimization.maximum_independent_set.solvers.cpsat.CpSatMisSolver(problem: MisProblem, params_objective_function: ParamsObjectiveFunction | None = None, **kwargs: Any)

Bases: MisSolver, OrtoolsCpSatSolver, WarmstartMixin

init_model(**kwargs)

Initialize internal model used to solve.

Can initialize a ortools, milp, gurobi, … model.

retrieve_solution(cpsolvercb: CpSolverSolutionCallback) → MisSolution

Construct a do solution from the cpsat solver internal solution.

It will be called each time the cpsat solver find a new solution. At that point, value of internal variables are accessible via cpsolvercb.Value(VARIABLE_NAME).

Parameters:

cpsolvercb – the ortools callback called when the cpsat solver finds a new solution.

Returns:

the intermediate solution, at do format.

set_warm_start(solution: MisSolution) → None

Make the solver warm start from the given solution.

discrete_optimization.maximum_independent_set.solvers.decomposition module

class discrete_optimization.maximum_independent_set.solvers.decomposition.DecomposedMisSolver(problem: Problem, params_objective_function: ParamsObjectiveFunction | None = None, **kwargs: Any)

Bases: MisSolver, WarmstartMixin

This solver is based on the current observation. From a given mis model and one current solution, if we decide to freeze the decision variable for a subset of items, the remaining problem to solve is also a mis problem, with fewer nodes. DecomposedMisSolver is a basic iterative solver that starts from a given solution, then freeze random items, solve subproblem with a custom root solver, rebuild original solution and repeat the process.

hyperparameters: list[Hyperparameter] = [FloatHyperparameter(name='proportion_to_remove', default=0.7, depends_on=None, name_in_kwargs='proportion_to_remove', low=0.0, high=1.0, suggest_low=False, suggest_high=False, step=None, log=False), IntegerHyperparameter(name='nb_iteration', default=100, depends_on=None, name_in_kwargs='nb_iteration', low=0, high=10000000, step=1, log=False), SubBrickHyperparameter(name='initial_solver', default=SubBrick(cls=<class 'discrete_optimization.maximum_independent_set.solvers.networkx.NetworkxMisSolver'>, kwargs={}, kwargs_from_solution=None), depends_on=None, name_in_kwargs='initial_solver'), SubBrickHyperparameter(name='root_solver', default=SubBrick(cls=<class 'discrete_optimization.maximum_independent_set.solvers.networkx.NetworkxMisSolver'>, kwargs={}, kwargs_from_solution=None), depends_on=None, name_in_kwargs='root_solver')]

Hyperparameters available for this solver.

These hyperparameters are to be feed to **kwargs found in

• __init__()

• init_model() (when available)

• solve()

initial_solution: MisSolution | None = None

Initial solution used for warm start.

rebuild_sol(sol: MisSolution, original_mis_model: MisProblem, original_solution: MisSolution, indexes_to_remove: set[int] | None = None)

Rebuild a full Mus solution object from a partial solution. :param sol: solution to a sub-mis problem :param original_knapsack_problem: original knapsack model to solve :param original_solution: original base solution :param indexes_to_remove: indexes of item removed when building the sub-knapsack problem. :return: A new solution object for the original problem.

set_warm_start(solution: MisSolution) → None

Make the solver warm start from the given solution.

Will be ignored if arg initial_solver is set and not None in call to solve().

solve(callbacks: list[Callback] | None = None, **kwargs: Any) → ResultStorage

Generic solving function.

Parameters:

• callbacks – list of callbacks used to hook into the various stage of the solve

• **kwargs – any argument specific to the solver

Solvers deriving from SolverDo should use callbacks methods .on_step_end(), … during solve(). But some solvers are not yet updated and are just ignoring it.

Returns (ResultStorage): a result object containing potentially a pool of solutions to a discrete-optimization problem

discrete_optimization.maximum_independent_set.solvers.dp module

class discrete_optimization.maximum_independent_set.solvers.dp.DpMisSolver(problem: Problem, params_objective_function: ParamsObjectiveFunction | None = None, **kwargs: Any)

Bases: DpSolver, MisSolver, WarmstartMixin

hyperparameters: list[Hyperparameter] = [CategoricalHyperparameter(name='solver', default=<class 'builtins.CABS'>, depends_on=None, name_in_kwargs='solver'), EnumHyperparameter(name='modeling', default=<DpModeling.ORDER: 0>, depends_on=None, name_in_kwargs='modeling'), EnumHyperparameter(name='order_method', default=<FixedOrderMethod.ORIGINAL_ORDER: 0>, depends_on=('modeling', <DpModeling.ORDER: 0>), name_in_kwargs='order_method')]

Hyperparameters available for this solver.

These hyperparameters are to be feed to **kwargs found in

• __init__()

• init_model() (when available)

• solve()

init_any_order(**kwargs: Any) → None

init_in_order(**kwargs: Any)

init_model(**kwargs: Any) → None

Initialize internal model used to solve.

Can initialize a ortools, milp, gurobi, … model.

modeling: DpModeling

nodes_convention: list

problem: MisProblem

retrieve_solution(sol: Solution) → Solution

set_warm_start(solution: MisSolution) → None

Make the solver warm start from the given solution.

transitions: dict

class discrete_optimization.maximum_independent_set.solvers.dp.DpModeling(value)

Bases: Enum

An enumeration.

ANY_ORDER = 1

ORDER = 0

class discrete_optimization.maximum_independent_set.solvers.dp.FixedOrderMethod(value)

Bases: Enum

An enumeration.

DEGREE = 1

ORIGINAL_ORDER = 0

discrete_optimization.maximum_independent_set.solvers.gurobi module

class discrete_optimization.maximum_independent_set.solvers.gurobi.GurobiMisSolver(problem: Problem, params_objective_function: ParamsObjectiveFunction | None = None, **kwargs: Any)

Bases: GurobiMilpSolver, BaseLpMisSolver

convert_to_variable_values(solution: MisSolution) → dict[Var, float]

Convert a solution to a mapping between model variables and their values.

Will be used by set_warm_start().

init_model(**kwargs: Any) → None

Initialize internal model used to solve.

Can initialize a ortools, milp, gurobi, … model.

class discrete_optimization.maximum_independent_set.solvers.gurobi.GurobiQuadraticMisSolver(problem: Problem, params_objective_function: ParamsObjectiveFunction | None = None, **kwargs: Any)

Bases: GurobiMilpSolver, BaseQuadMisSolver

Quadratic solver with gurobi.

Work only for graph without weight on nodes. If there are weights, it’s going to ignore them.

convert_to_variable_values(solution: MisSolution) → dict[Var, float]

Convert a solution to a mapping between model variables and their values.

Will be used by set_warm_start().

create_vars_node_matrix() → gurobipy.MVar

init_model(**kwargs: Any) → None

Initialize internal model used to solve.

Can initialize a ortools, milp, gurobi, … model.

vars_node_matrix: gurobipy.MVar

discrete_optimization.maximum_independent_set.solvers.kamis module

class discrete_optimization.maximum_independent_set.solvers.kamis.KamisMisSolver(problem: Problem, params_objective_function: ParamsObjectiveFunction | None = None, **kwargs: Any)

Bases: MisSolver

To use Kamis Solver you need to define an environment variable “KAMIS_DEPLOY” who is the path to the folder where are Kamis executable.

hyperparameters: list[Hyperparameter] = [CategoricalHyperparameter(name='method', default='weighted', depends_on=None, name_in_kwargs='method')]

Hyperparameters available for this solver.

These hyperparameters are to be feed to **kwargs found in

• __init__()

• init_model() (when available)

• solve()

init_model(**kwargs)

Initialize internal model used to solve.

Can initialize a ortools, milp, gurobi, … model.

solve(**kwargs) → ResultStorage

Generic solving function.

Parameters:

• callbacks – list of callbacks used to hook into the various stage of the solve

• **kwargs – any argument specific to the solver

Solvers deriving from SolverDo should use callbacks methods .on_step_end(), … during solve(). But some solvers are not yet updated and are just ignoring it.

Returns (ResultStorage): a result object containing potentially a pool of solutions to a discrete-optimization problem

discrete_optimization.maximum_independent_set.solvers.lns module

class discrete_optimization.maximum_independent_set.solvers.lns.AllVarsOrtoolsCpSatMisConstraintHandler(problem: MisProblem, fraction_to_fix: float = 0.9)

Bases: OrtoolsCpSatConstraintHandler

Fix fraction of all variables, not only the ones already chosen.

adding_constraint_from_results_store(solver: CpSatMisSolver, result_storage: ResultStorage, last_result_store: ResultStorage | None = None, **kwargs: Any) → Iterable[Constraint]

hyperparameters: list[Hyperparameter] = [FloatHyperparameter(name='fraction_to_fix', default=0.9, depends_on=None, name_in_kwargs='fraction_to_fix', low=0.0, high=1.0, suggest_low=False, suggest_high=False, step=None, log=False)]

Hyperparameters available for this solver.

These hyperparameters are to be feed to **kwargs found in

• __init__()

• init_model() (when available)

• solve()

class discrete_optimization.maximum_independent_set.solvers.lns.DestroyOrtoolsCpSatMisConstraintHandler(problem: MisProblem, fraction_to_fix: float = 0.9)

Bases: OrtoolsCpSatConstraintHandler

adding_constraint_from_results_store(solver: CpSatMisSolver, result_storage: ResultStorage, last_result_store: ResultStorage | None = None, **kwargs: Any) → Iterable[Constraint]

hyperparameters: list[Hyperparameter] = [FloatHyperparameter(name='fraction_to_fix', default=0.9, depends_on=None, name_in_kwargs='fraction_to_fix', low=0.0, high=1.0, suggest_low=False, suggest_high=False, step=None, log=False)]

Hyperparameters available for this solver.

These hyperparameters are to be feed to **kwargs found in

• __init__()

• init_model() (when available)

• solve()

class discrete_optimization.maximum_independent_set.solvers.lns.LocalMovesOrtoolsCpSatMisConstraintHandler(problem: MisProblem, nb_moves: int = 5, fraction_to_fix: float = 0.9)

Bases: OrtoolsCpSatConstraintHandler

adding_constraint_from_results_store(solver: CpSatMisSolver, result_storage: ResultStorage, last_result_store: ResultStorage | None = None, **kwargs: Any) → Iterable[Constraint]

hyperparameters: list[Hyperparameter] = [IntegerHyperparameter(name='nb_moves', default=1, depends_on=None, name_in_kwargs='nb_moves', low=0, high=10, step=1, log=False), FloatHyperparameter(name='fraction_to_fix', default=0.9, depends_on=None, name_in_kwargs='fraction_to_fix', low=0.0, high=1.0, suggest_low=False, suggest_high=False, step=None, log=False)]

Hyperparameters available for this solver.

These hyperparameters are to be feed to **kwargs found in

• __init__()

• init_model() (when available)

• solve()

class discrete_optimization.maximum_independent_set.solvers.lns.OrtoolsCpSatMisConstraintHandler(problem: MisProblem, fraction_to_fix: float = 0.9)

Bases: OrtoolsCpSatConstraintHandler

adding_constraint_from_results_store(solver: CpSatMisSolver, result_storage: ResultStorage, last_result_store: ResultStorage | None = None, **kwargs: Any) → Iterable[Constraint]

hyperparameters: list[Hyperparameter] = [FloatHyperparameter(name='fraction_to_fix', default=0.9, depends_on=None, name_in_kwargs='fraction_to_fix', low=0.0, high=1.0, suggest_low=False, suggest_high=False, step=None, log=False)]

Hyperparameters available for this solver.

These hyperparameters are to be feed to **kwargs found in

• __init__()

• init_model() (when available)

• solve()

discrete_optimization.maximum_independent_set.solvers.lp module

class discrete_optimization.maximum_independent_set.solvers.lp.BaseLpMisSolver(problem: Problem, params_objective_function: ParamsObjectiveFunction | None = None, **kwargs: Any)

Bases: MisSolver, MilpSolver

convert_to_variable_values(solution: MisSolution) → dict[Any, float]

Convert a solution to a mapping between model variables and their values.

Will be used by set_warm_start().

init_model(**kwargs: Any) → None

Initialize internal model used to solve.

Can initialize a ortools, milp, gurobi, … model.

retrieve_current_solution(get_var_value_for_current_solution: Callable[[Any], float], get_obj_value_for_current_solution: Callable[[], float]) → MisSolution

Retrieve current solution from internal gurobi solution.

This converts internal gurobi solution into a discrete-optimization Solution. This method can be called after the solve in retrieve_solutions() or during solve within a gurobi/pymilp/cplex callback. The difference will be the get_var_value_for_current_solution and get_obj_value_for_current_solution callables passed.

Parameters:

• get_var_value_for_current_solution – function extracting the value of the given variable for the current solution will be different when inside a callback or after the solve is finished

• get_obj_value_for_current_solution – function extracting the value of the objective for the current solution.

Returns:

the converted solution at d-o format

vars_node: list[Any]

class discrete_optimization.maximum_independent_set.solvers.lp.BaseQuadMisSolver(problem: Problem, params_objective_function: ParamsObjectiveFunction | None = None, **kwargs: Any)

Bases: BaseLpMisSolver

Base class for quadratic solvers with gurobi or mathopt.

Work only for graph without weight on nodes. If there are weights, it’s going to ignore them.

create_vars_node_matrix() → array

init_model(**kwargs: Any) → None

Initialize internal model used to solve.

Can initialize a ortools, milp, gurobi, … model.

property vars_node: list[Any]

vars_node_matrix: array

discrete_optimization.maximum_independent_set.solvers.mathopt module

class discrete_optimization.maximum_independent_set.solvers.mathopt.MathOptMisSolver(problem: Problem, params_objective_function: ParamsObjectiveFunction | None = None, **kwargs: Any)

Bases: OrtoolsMathOptMilpSolver, BaseLpMisSolver

convert_to_variable_values(solution: MisSolution) → dict[Variable, float]

Convert a solution to a mapping between model variables and their values.

Will be used by set_warm_start() to provide a suitable SolutionHint.variable_values. See https://or-tools.github.io/docs/pdoc/ortools/math_opt/python/model_parameters.html#SolutionHint for more information.

Override it in subclasses to have a proper warm start.

class discrete_optimization.maximum_independent_set.solvers.mathopt.MathOptQuadraticMisSolver(problem: Problem, params_objective_function: ParamsObjectiveFunction | None = None, **kwargs: Any)

Bases: OrtoolsMathOptMilpSolver, BaseQuadMisSolver

Quadratic solver mathopt.

Work only for graph without weight on nodes. If there are weights, it’s going to ignore them.

convert_to_variable_values(solution: MisSolution) → dict[Variable, float]

Convert a solution to a mapping between model variables and their values.

Will be used by set_warm_start() to provide a suitable SolutionHint.variable_values. See https://or-tools.github.io/docs/pdoc/ortools/math_opt/python/model_parameters.html#SolutionHint for more information.

Override it in subclasses to have a proper warm start.

has_quadratic_objective: bool = True

Flag telling that the objective is a quadratic expression.

This is use to pass the proper function to retrieve_current_solution for the objective. Should be overriden to True in solvers with quadratic objectives.

discrete_optimization.maximum_independent_set.solvers.mis_solver module

class discrete_optimization.maximum_independent_set.solvers.mis_solver.MisSolver(problem: Problem, params_objective_function: ParamsObjectiveFunction | None = None, **kwargs: Any)

Bases: SolverDO

problem: MisProblem

discrete_optimization.maximum_independent_set.solvers.networkx module

class discrete_optimization.maximum_independent_set.solvers.networkx.NetworkxMisSolver(problem: Problem, params_objective_function: ParamsObjectiveFunction | None = None, **kwargs: Any)

Bases: MisSolver

solve(callbacks: list[Callback] | None = None, **kwargs: Any) → ResultStorage

Generic solving function.

Parameters:

• callbacks – list of callbacks used to hook into the various stage of the solve

• **kwargs – any argument specific to the solver

Solvers deriving from SolverDo should use callbacks methods .on_step_end(), … during solve(). But some solvers are not yet updated and are just ignoring it.

Returns (ResultStorage): a result object containing potentially a pool of solutions to a discrete-optimization problem

discrete_optimization.maximum_independent_set.solvers.quantum module

class discrete_optimization.maximum_independent_set.solvers.quantum.MisQiskit(problem: MisProblem)

Bases: object

interpret(result: object | ndarray) → MisSolution

to_quadratic_program() → object

class discrete_optimization.maximum_independent_set.solvers.quantum.QaoaMisSolver(problem: MisProblem, params_objective_function: ParamsObjectiveFunction | None = None, **kwargs)

Bases: MisSolver, QiskitQaoaSolver

init_model(**kwargs)

Initialize internal model used to solve.

Can initialize a ortools, milp, gurobi, … model.

retrieve_current_solution(result)

Retrieve current solution from qiskit result.

Parameters:

result – list of value for each binary variable of the problem

Returns:

the converted solution at d-o format

class discrete_optimization.maximum_independent_set.solvers.quantum.VqeMisSolver(problem: MisProblem, params_objective_function: ParamsObjectiveFunction | None = None, **kwargs)

Bases: MisSolver, QiskitVqeSolver

init_model(**kwargs)

Initialize internal model used to solve.

Can initialize a ortools, milp, gurobi, … model.

retrieve_current_solution(result) → Solution

Retrieve current solution from qiskit result.

Parameters:

result – list of value for each binary variable of the problem

Returns:

the converted solution at d-o format

discrete_optimization.maximum_independent_set.solvers.toulbar module

class discrete_optimization.maximum_independent_set.solvers.toulbar.ToulbarMisSolver(problem: Problem, params_objective_function: ParamsObjectiveFunction | None = None, **kwargs: Any)

Bases: MisSolver

init_model(**kwargs)

Initialize internal model used to solve.

Can initialize a ortools, milp, gurobi, … model.

solve(**kwargs: Any) → ResultStorage

Generic solving function.

Parameters:

• callbacks – list of callbacks used to hook into the various stage of the solve

• **kwargs – any argument specific to the solver

Solvers deriving from SolverDo should use callbacks methods .on_step_end(), … during solve(). But some solvers are not yet updated and are just ignoring it.

Returns (ResultStorage): a result object containing potentially a pool of solutions to a discrete-optimization problem

Module contents