Skip to content

quast_decisiontree.problems.optimization_problem

quast_decisiontree.problems.optimization_problem

This interface serves as a template for optimization problems

OptimizationProblem

Bases: ABC

an abstract base class for optimization problems.

The init should create an instance of the problem class from the minimum amount of data. E. g., a Travelling Salesperson Problem doesn't need a coordinate list, but just an adjacency matrix. A MaxCut problem is fully defined by a list of edges.

To allow for other creation methods, implement specific from_x methods (e.g. for the TSP: from_coordinate_list()).

Wherever possible, inheriting from (e.g.) Qiskit classes is advised.

Subclasses must implement create_random_instance, from_dict, evaluate_objective and formulate_problem. Implementing to_dict is strongly recommended (it powers equality checks and serialization) but not enforced. Overriding is_feasible is optional; the default treats every candidate solution as feasible.

Source code in src/quast_decisiontree/problems/optimization_problem.py 
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
class OptimizationProblem(ABC):
    """an abstract base class for optimization problems.

    The __init__ should create an instance of the problem class from the minimum amount of
    data. E. g., a Travelling Salesperson Problem doesn't need a coordinate list, but just an
    adjacency matrix. A MaxCut problem is fully defined by a list of edges.

    To allow for other creation methods, implement specific from_x methods (e.g. for the TSP:
    from_coordinate_list()).

    Wherever possible, inheriting from (e.g.) Qiskit classes is advised.

    Subclasses must implement ``create_random_instance``, ``from_dict``, ``evaluate_objective``
    and ``formulate_problem``. Implementing ``to_dict`` is strongly recommended (it powers
    equality checks and serialization) but not enforced. Overriding ``is_feasible`` is optional;
    the default treats every candidate solution as feasible.
    """

    direct_encoding_modes = ()

    @classmethod
    @abstractmethod
    def create_random_instance(
        cls, size: int, seed: int | None = None, *args, **kwargs
    ) -> "OptimizationProblem":
        """create a random problem instance from a size parameter, a seed and possibly other
        parameters.

        This method is needed for quick testing and should have default values for all but the size
        argument. Subclasses may widen ``seed`` to any type their random generator accepts.
        """

    @classmethod
    @abstractmethod
    def from_dict(cls, problem_dict: Mapping) -> "OptimizationProblem":
        """constructs a valid instance of the optimization problem from correct dictionary data

        The typical use is a handler reading a JSON file, determining the problem class via the
        dictionary key "problem_class", then passing the dictionary to the from_dict method of
        the appropriate problem class.
        """

    @abstractmethod
    def evaluate_objective(self, result) -> float:
        """evaluate the optimization objective at a candidate solution.

        The result should be given in a problem-specific way and the format specified in the
        docstring of the concrete implementation.
        """

    @abstractmethod
    def formulate_problem(self, mode: str, *args, **kwargs) -> Any:
        """formulates a QUBO matrix or similar form directly.

        Implementations must accept, for every ``mode`` listed in ``direct_encoding_modes``,
        candidate solutions expressed as lists of binary variables in the encoding that mode
        produces.
        """

    def is_feasible(self, solution_string: Sequence[int] | str, encoding: Any = None) -> bool:
        """check whether a candidate solution satisfies the problem's constraints.

        The default implementation treats every solution as feasible. Override for constrained
        problems. ``solution_string`` is a sequence (or string) of binary variables in the given
        ``encoding``.
        """
        return True

    def to_dict(self) -> dict:
        """serialize the instance to a plain dictionary.

        Not abstract so that subclasses can be instantiated without it, but equality checks and
        serialization rely on it. Override in every subclass that needs those features.
        """
        raise NotImplementedError(f"{type(self).__name__} does not implement to_dict().")

    def _check_mode_support(self, mode: Any) -> None:
        """raises an error if the mode is invalid"""
        supported_modes = [s.lower() for s in self.direct_encoding_modes]
        try:
            if mode.lower() not in supported_modes:
                raise ValueError(f"Mode {mode!r} isn't supported, choose from {supported_modes}")
        except AttributeError as e:
            raise TypeError(f"Mode argument must be a string, not {type(mode).__name__}.") from e

    def __eq__(self, other):
        if isinstance(other, Mapping):
            try:
                other = self.from_dict(other)
            except Exception:
                return NotImplemented
        if not isinstance(other, OptimizationProblem):
            return NotImplemented
        try:
            return self.to_dict() == other.to_dict()
        except NotImplementedError:
            return NotImplemented

direct_encoding_modes class-attribute instance-attribute 

direct_encoding_modes = ()

create_random_instance abstractmethod classmethod 

create_random_instance(size, seed=None, *args, **kwargs)

create a random problem instance from a size parameter, a seed and possibly other parameters.

This method is needed for quick testing and should have default values for all but the size argument. Subclasses may widen seed to any type their random generator accepts.

Source code in src/quast_decisiontree/problems/optimization_problem.py 
36
37
38
39
40
41
42
43
44
45
46
@classmethod
@abstractmethod
def create_random_instance(
    cls, size: int, seed: int | None = None, *args, **kwargs
) -> "OptimizationProblem":
    """create a random problem instance from a size parameter, a seed and possibly other
    parameters.

    This method is needed for quick testing and should have default values for all but the size
    argument. Subclasses may widen ``seed`` to any type their random generator accepts.
    """

from_dict abstractmethod classmethod 

from_dict(problem_dict)

constructs a valid instance of the optimization problem from correct dictionary data

The typical use is a handler reading a JSON file, determining the problem class via the dictionary key "problem_class", then passing the dictionary to the from_dict method of the appropriate problem class.

Source code in src/quast_decisiontree/problems/optimization_problem.py 
48
49
50
51
52
53
54
55
56
@classmethod
@abstractmethod
def from_dict(cls, problem_dict: Mapping) -> "OptimizationProblem":
    """constructs a valid instance of the optimization problem from correct dictionary data

    The typical use is a handler reading a JSON file, determining the problem class via the
    dictionary key "problem_class", then passing the dictionary to the from_dict method of
    the appropriate problem class.
    """

evaluate_objective abstractmethod 

evaluate_objective(result)

evaluate the optimization objective at a candidate solution.

The result should be given in a problem-specific way and the format specified in the docstring of the concrete implementation.

Source code in src/quast_decisiontree/problems/optimization_problem.py 
58
59
60
61
62
63
64
@abstractmethod
def evaluate_objective(self, result) -> float:
    """evaluate the optimization objective at a candidate solution.

    The result should be given in a problem-specific way and the format specified in the
    docstring of the concrete implementation.
    """

formulate_problem abstractmethod 

formulate_problem(mode, *args, **kwargs)

formulates a QUBO matrix or similar form directly.

Implementations must accept, for every mode listed in direct_encoding_modes, candidate solutions expressed as lists of binary variables in the encoding that mode produces.

Source code in src/quast_decisiontree/problems/optimization_problem.py 
66
67
68
69
70
71
72
73
@abstractmethod
def formulate_problem(self, mode: str, *args, **kwargs) -> Any:
    """formulates a QUBO matrix or similar form directly.

    Implementations must accept, for every ``mode`` listed in ``direct_encoding_modes``,
    candidate solutions expressed as lists of binary variables in the encoding that mode
    produces.
    """

is_feasible 

is_feasible(solution_string, encoding=None)

check whether a candidate solution satisfies the problem's constraints.

The default implementation treats every solution as feasible. Override for constrained problems. solution_string is a sequence (or string) of binary variables in the given encoding.

Source code in src/quast_decisiontree/problems/optimization_problem.py 
75
76
77
78
79
80
81
82
def is_feasible(self, solution_string: Sequence[int] | str, encoding: Any = None) -> bool:
    """check whether a candidate solution satisfies the problem's constraints.

    The default implementation treats every solution as feasible. Override for constrained
    problems. ``solution_string`` is a sequence (or string) of binary variables in the given
    ``encoding``.
    """
    return True

to_dict 

to_dict()

serialize the instance to a plain dictionary.

Not abstract so that subclasses can be instantiated without it, but equality checks and serialization rely on it. Override in every subclass that needs those features.

Source code in src/quast_decisiontree/problems/optimization_problem.py 
84
85
86
87
88
89
90
def to_dict(self) -> dict:
    """serialize the instance to a plain dictionary.

    Not abstract so that subclasses can be instantiated without it, but equality checks and
    serialization rely on it. Override in every subclass that needs those features.
    """
    raise NotImplementedError(f"{type(self).__name__} does not implement to_dict().")

__eq__ 

__eq__(other)
Source code in src/quast_decisiontree/problems/optimization_problem.py 
101
102
103
104
105
106
107
108
109
110
111
112
def __eq__(self, other):
    if isinstance(other, Mapping):
        try:
            other = self.from_dict(other)
        except Exception:
            return NotImplemented
    if not isinstance(other, OptimizationProblem):
        return NotImplemented
    try:
        return self.to_dict() == other.to_dict()
    except NotImplementedError:
        return NotImplemented