discrete_optimization.maximum_independent_set package

Subpackages

Submodules

discrete_optimization.maximum_independent_set.parser module

class discrete_optimization.maximum_independent_set.parser.DimacsPrefixes(*values)[source]

Bases: Enum

COMMENT = 'c'
EDGE = 'e'
PROBLEM = 'p'
discrete_optimization.maximum_independent_set.parser.dimacs_parser(filename: str)[source]

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

Parameters:

filename – path to the input file using dimacs format

See http://prolland.free.fr/works/research/dsat/dimacs.html for reference about dimacs format

Returns: a MisProblem instance

discrete_optimization.maximum_independent_set.parser.dimacs_parser_nx(filename: str)

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

Parameters:

filename – path to the input file using dimacs format

See http://prolland.free.fr/works/research/dsat/dimacs.html for reference about 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.

Useful to find automatically available mutations for local search. Used by genetic algorithms Ga and Nsga.

This needs only to be implemented in child classes when GA or LS solvers are to be used.

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

get_dummy_solution() → MisSolution[source]

Create a trivial solution for the problem.

Should satisfy the problem ideally. Does not exist for all kind of problems.

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

copy() → MisSolution[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() → MisSolution[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

problem: MisProblem

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