boundml.components

 9class Component(ABC):
10    """
11    A Component is a component of a ModularSolver that contains different callback used by the solver.
12    Depending on its subtype, it is used at different moment of the solving process
13    """
14
15    def __init__(self):
16        self.observation = None
17        """Used by the component to store its output if desired."""
18
19    def reset(self, model: Model) -> None:
20        """
21        Resets the component to its initial state.
22        Called by the solver just before starting the solving process.
23        Parameters
24        ----------
25        model : Model
26            State of the model
27        """
28        pass
29
30    @abstractmethod
31    def callback(self, model: Model, passive: bool=True) -> SCIP_RESULT | None:
32        """
33        Callback method called by the solver.
34        Depending on its subtype, it is used at different moment of the solving process
35
36        Parameters
37        ----------
38        model : Model
39            State of the model
40        passive : bool
41            Whether the component is allowed to perform an action on the model or not
42
43        Returns
44        -------
45        SCIP_RESULT that corresponds to the action made by the callback, if no action was made then return None
46        """
47        raise NotImplementedError("Subclasses must implement this method.")
48
49    def done(self, model: Model) -> None:
50        """
51        Called by the solver once the solving process is done.
52        Can be useful to perform final actions.
53
54        Parameters
55        ----------
56        model : Model
57            State of the model
58        """
59        pass

11class BranchingComponent(Component):
12    """
13    A BranchingComponent is a Component called before each branching decision.
14    The callback method is called when a branching decision is required
15    """
16
17    @abstractmethod
18    def callback(self, model: Model, passive: bool = True) -> SCIP_RESULT | None:
19        """
20        Callback method called by the solver when a branching decision is required.
21        Is responsible to perform the branching as it wants if passive is False.
22
23        Parameters
24        ----------
25        model : Model
26            State of the model
27        passive : bool
28            Whether the component is allowed to perform a branching or not
29        Returns
30        -------
31        SCIP_RESULT among: SCIP_RESULT.BRANCHED, SCIP_RESULT.DIDNOTRUN, SCIP_RESULT.CUTOFF
32        Or None if the component does not aim to perform any action. For exemple, if it collects data.
33        """
34        raise NotImplementedError("Subclasses must implement this method.")

37class RootNodeBranchingComponent(BranchingComponent):
38    """
39    A RootNodeBranchingComponent is a BranchingComponent called only once at the beginning of the tree exploration.
40    The callback method is called only before the branching decision of **the root node**.
41    It is called before every other BranchingComponent.
42    """

 44class ScoringBranchingStrategy(BranchingComponent):
 45    """
 46    A ScoringBranchingStrategy is a BranchingComponent that represents a score based branching strategies.
 47    When called, it computes score for each candidate and branches on the one with the highest score.
 48    """
 49    def __init__(self):
 50        super().__init__()
 51        self.scores = None
 52
 53    @abstractmethod
 54    def compute_scores(self, model: Model) -> np.ndarray:
 55        """
 56        Compute scores for each branching candidate.
 57        scores[i] must contain the score for i th candidate
 58        If a score is np.nan, the underlying strategy consider that it can cutoff the node
 59
 60        Parameters
 61        ----------
 62        model : Model
 63            State of the model
 64
 65        Returns
 66        ----------
 67        np.ndarray with a size of the number of branching candidates
 68        """
 69        candidates, *_ = model.getLPBranchCands()
 70        scores = np.zeros(len(candidates))
 71        scores[:] = -model.infinity()
 72        return scores
 73
 74
 75    def callback(self, model: Model, passive: bool=True) -> SCIP_RESULT:
 76        """
 77        When called, update the scores and branches on the variable with the highest score if allowed
 78        Parameters. If one variable has a score of np.nan, then the node is cutoff
 79        ----------
 80        model : Model
 81        passive : bool
 82
 83        Returns
 84        -------
 85        SCIP_RESULT.BRANCHED if passive==False, SCIP_RESULT.DIDNOTRUN otherwise
 86        """
 87        candidates, candidates_sols, *_ = model.getLPBranchCands()
 88        self.scores = self.compute_scores(model)
 89
 90        if passive:
 91            return SCIP_RESULT.DIDNOTRUN
 92        elif np.nan in self.scores:
 93            return SCIP_RESULT.CUTOFF
 94        else:
 95            index = np.argmax(self.scores)
 96            model.branchVarVal(candidates[index], candidates_sols[index])
 97
 98            return SCIP_RESULT.BRANCHED
 99
100    def get_last_scores(self):
101        """
102        Get the last score for each branching candidate used on the last callback
103        Returns
104        -------
105        np.ndarray with a size of the number of branching candidates
106        """
107        return self.scores

111class Pseudocosts(ScoringBranchingStrategy):
112    def compute_scores(self, model: Model) -> np.ndarray:
113        """
114        Compute pseudocosts scores for each candidate.
115        Parameters
116        ----------
117        model : Model
118        """
119        scores = super().compute_scores(model)
120        candidates, *_ = model.getLPBranchCands()
121
122        var: pyscipopt.Variable
123        for i, var in enumerate(candidates):
124            lpsol = var.getLPSol()
125            score = model.getVarPseudocostScore(var, lpsol)
126
127            scores[i] = score
128
129        return scores
130
131    def __str__(self):
132        return "Pseudocosts"

134class StrongBranching(ScoringBranchingStrategy):
135    """
136    Simple implementation of Strong Branching.
137    """
138    def __init__(self, priocands: bool = False, all_scores: bool = True, allow_cutoff: bool = False, idempotent: bool = True):
139        """
140        Parameters
141        ----------
142        priocands : bool
143            Whether the scoring is only done on priocands
144        all_scores : bool
145            Whether all the candidates are scored. If True, the scoring is done when it is possible to cut the node
146        allow_cutoff : bool
147            Whether the cutoff is allowed.
148        idempotent: bool
149            Whether getVarStrongbranch calls are idempotent.
150        """
151        super().__init__()
152        self.priocands = priocands
153        self.all_scores = all_scores
154        self.allow_cutoff = allow_cutoff
155        self.idempotent = idempotent
156
157    def compute_scores(self, model: Model) -> np.ndarray:
158        scores = super().compute_scores(model)
159
160        branch_cands, branch_cand_sols, branch_cand_fracs, ncands, npriocands, nimplcands = model.getLPBranchCands()
161
162        n = npriocands if self.priocands else ncands
163
164        lpobjval = model.getLPObjVal()
165
166        # Start strong branching and iterate over the branching candidates
167        model.startStrongbranch()
168        for i in range(n):
169            # Strong branch!
170            down, up, downvalid, upvalid, downinf, upinf, downconflict, upconflict, lperror = model.getVarStrongbranch(
171                branch_cands[i], 2147483647, idempotent=self.idempotent)
172
173            down = max(down, lpobjval)
174            up = max(up, lpobjval)
175            downgain = down - lpobjval
176            upgain = up - lpobjval
177
178            scores[i] = model.getBranchScoreMultiple(branch_cands[i], [downgain, upgain])
179
180            # In the case of both infeasible sub-problems cutoff the node
181            if not self.all_scores and self.allow_cutoff and downinf and upinf:
182                scores[i] = np.nan
183                continue
184
185        model.endStrongbranch()
186        return scores
187
188    def __str__(self):
189        return "StrongBranching"

192class AccuracyBranching(ScoringBranchingStrategy):
193    """
194    AccuracyBranchingComponent is a component that depends on 2 ScoringBranchingStrategy.
195    Generally an oracle, and another one that tries to imitate the oracle.
196    It outputs the same results as the model, but in addition stores for each branching decision at which position the
197    second component best candidate would have been ranked by the oracle. This allows to compare good the model's
198    decisions are comparedd to its oracle.
199    /!\ If used by a solver during an evaluate_solvers call, the evaluate_solvers must use only one CPU to gather data
200    from each solving process
201    """
202
203    def __init__(self, oracle: ScoringBranchingStrategy, model: ScoringBranchingStrategy):
204        super().__init__()
205        self.oracle_strategy = oracle
206        self.model_strategy = model
207        self.observation = []
208
209    def reset(self, model: Model) -> None:
210        super().reset(model)
211        self.oracle_strategy.reset(model)
212        self.model_strategy.reset(model)
213
214    def compute_scores(self, model: Model) -> np.ndarray:
215        scores = super().compute_scores(model)
216
217        oracle_scores = self.oracle_strategy.compute_scores(model)
218        model_scores = self.model_strategy.compute_scores(model)
219
220        scores = model_scores
221
222        best_index = np.argmax(model_scores) # model's choice
223        oracle_sorted_indexes = np.argsort(-oracle_scores)
224
225        position = np.where(oracle_sorted_indexes == best_index)[0][0] + 1
226        self.observation.append(position)
227
228        return scores
229
230    def done(self, model: Model) -> None:
231        self.oracle_strategy.done(model)
232        self.model_strategy.done(model)
233
234        super().done(model)
235
236    def get_observations(self):
237        return np.array(self.observation)
238
239    def get_accuracy(self, n: int) -> float:
240        """
241        Returns the proportion of time when the model's choice is among the n bests candidates of its oracle
242        """
243        return np.average(self.get_observations() <= n)
244
245    def __str__(self):
246        return f"Acc {str(self.model_strategy)}"

12class EcoleComponent(BranchingComponent):
13    """
14    EcoleComponent is a wrapper around a [ecole](https://github.com/sirenard/ecole) Observer.
15    Its callback method returns what the extract method of the Observer would have returned
16    """
17    def __init__(self, observer):
18        super().__init__()
19
20        if not HAS_ECOLE_FORK:
21            raise RuntimeError(
22                "EcoleComponent requires 'ecole-fork' package. "
23                "Install with: pip install boundml[ecole]"
24            )
25
26        self.observer = observer
27        self.ecole_model = None
28
29    def reset(self, model: Model) -> None:
30        self.ecole_model = ecole.scip.Model.from_pyscipopt(model)
31        self.observer.before_reset(self.ecole_model)
32
33    def callback(self, model: Model, passive: bool=True):
34        self.observation = self.observer.extract(self.ecole_model, done=False)
35        return None
36
37    def done(self, model: Model) -> None:
38        super().done(model)
39
40    def __getstate__(self):
41        return type(self.observer)
42
43    def __setstate__(self, state):
44        self.__init__(state())