discrete_optimization.maximum_independent_set package

Subpackages

Submodules

discrete_optimization.maximum_independent_set.parser module

discrete_optimization.maximum_independent_set.parser.basic_parser(filename: str)[source]

From a file in basic format input, initialise a MisProblem instance.

Parameters:

filename – file in the basic format (same format as for coloring problem)

Returns: a MisProblem instance

discrete_optimization.maximum_independent_set.parser.basic_parser_nx(filename: str)[source]

From a file in basic format input, initialise a MisProblem instance.

Parameters:

filename – file in the basic format (same format as for coloring problem)

Returns: a MisProblem instance

discrete_optimization.maximum_independent_set.parser.dimacs_parser(filename: str)[source]

From a file in dimacs format, initialise a MisProblem instance.

Parameters:

filename – file in the dimacs format

Returns: a MisProblem instance

discrete_optimization.maximum_independent_set.parser.dimacs_parser_nx(filename: str)[source]

From a file in dimacs format, initialise a MisProblem instance.

Parameters:

filename – file in the dimacs format

Returns: a MisProblem instance

discrete_optimization.maximum_independent_set.parser.get_data_available(data_folder: str | None = None, data_home: str | None = None) → list[str][source]

Get datasets available for mis.

Params:
data_folder: folder where datasets for coloring whould be find.

If None, we look in “mis” subdirectory of data_home.

data_home: root directory for all datasets. Is None, set by

default to “~/discrete_optimization_data “

discrete_optimization.maximum_independent_set.plot module

discrete_optimization.maximum_independent_set.plot.plot_mis_graph(problem: MisProblem, name_figure: str = '')[source]
discrete_optimization.maximum_independent_set.plot.plot_mis_solution(solution: MisSolution, name_figure: str = '')[source]

discrete_optimization.maximum_independent_set.problem module

class discrete_optimization.maximum_independent_set.problem.MisProblem(graph: Graph | Graph, attribute_aggregate: str = 'size')[source]

Bases: Problem

compute_violation(variable: MisSolution) → int[source]
evaluate(variable: MisSolution) → dict[str, float][source]

Evaluate a given solution object for the given problem.

This method should return a dictionnary of KPI, that can be then used for mono or multiobjective optimization.

Parameters:

variable (Solution) – the Solution object to evaluate.

Returns: dictionnary of float kpi for the solution.

get_attribute_register() → EncodingRegister[source]

Returns how the Solution should be encoded.

Returns (EncodingRegister): content of the encoding of the solution

get_dummy_solution() → MisSolution[source]
get_objective_register() → ObjectiveRegister[source]

Returns the objective definition.

Returns (ObjectiveRegister): object defining the objective criteria.

get_solution_type() → type[Solution][source]

Returns the class implementation of a Solution.

Returns (class): class object of the given Problem.

satisfy(variable: MisSolution) → bool[source]

Computes if a solution satisfies or not the constraints of the problem.

Parameters:

variable – the Solution object to check satisfability

Returns (bool): boolean true if the constraints are fulfilled, false elsewhere.

class discrete_optimization.maximum_independent_set.problem.MisSolution(problem: MisProblem, chosen: list | ndarray)[source]

Bases: Solution

change_problem(new_problem: Problem) → None[source]

If relevant to the optimisation problem, change the underlying problem instance for the solution.

This method can be used to evaluate a solution for different instance of problems.

Parameters:

new_problem (Problem) – another problem instance from which the solution can be evaluated

Returns: None

copy() → Solution[source]

Deep copy of the solution.

The copy() function should return a new object containing the same input as the current object, that respects the following expected behaviour: -y = x.copy() -if do some inplace change of y, the changes are not done in x.

Returns: a new object from which you can manipulate attributes without changing the original object.

lazy_copy() → Solution[source]

This function should return a new object but possibly with mutable attributes from the original objects.

A typical use of lazy copy is in evolutionary algorithms or genetic algorithm where the use of local move don’t need to do a possibly costly deepcopy.

Returns (Solution): copy (possibly shallow) of the Solution

discrete_optimization.maximum_independent_set.solvers_map module

Utility module to launch different solvers on the maximum independent set problem.

discrete_optimization.maximum_independent_set.solvers_map.solve(method_solver: type[MisSolver], problem: MisProblem, **kwargs: Any) → ResultStorage[source]

Solve a mis instance with a given class of solver.

Parameters:

  • method_solver – class of the solver to use

  • problem – mis problem instance

  • **args – specific options of the solver

Returns: a ResultsStorage objecting obtained by the solver.

Module contents