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

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

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

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