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
45    @abstractmethod
46    def compute_scores(self, model: Model) -> np.array:
47        """
48        Compute scores for each branching candidate.
49        scores[i] must contain the score for i th candidate
50        If a score is np.nan, the underlying strategy consider that it can cutoff the node
51
52        Parameters
53        ----------
54        model : Model
55            State of the model
56
57        Returns
58        ----------
59        np.array with a size of the number of branching candidates
60        """
61        candidates, *_ = model.getLPBranchCands()
62        scores = np.zeros(len(candidates))
63        scores[:] = -model.infinity()
64        return scores
65
66
67    def callback(self, model: Model, passive: bool=True) -> SCIP_RESULT:
68        """
69        When called, update the scores and branches on the variable with the highest score if allowed
70        Parameters. If one variable has a score of np.nan, then the node is cutoff
71        ----------
72        model : Model
73        passive : bool
74
75        Returns
76        -------
77        SCIP_RESULT.BRANCHED if passive==False, SCIP_RESULT.DIDNOTRUN otherwise
78        """
79        candidates, *_ = model.getLPBranchCands()
80        scores = self.compute_scores(model)
81
82        if passive:
83            return SCIP_RESULT.DIDNOTRUN
84        elif np.nan in scores:
85            return SCIP_RESULT.CUTOFF
86        else:
87            index = np.argmax(scores)
88            best_cand = candidates[index]
89            model.branchVar(best_cand)
90
91            return SCIP_RESULT.BRANCHED

 95class Pseudocosts(ScoringBranchingStrategy):
 96    def compute_scores(self, model: Model) -> None:
 97        """
 98        Compute pseudocosts scores for each candidate.
 99        Parameters
100        ----------
101        model : Model
102        """
103        scores = super().compute_scores(model)
104        candidates, *_ = model.getLPBranchCands()
105
106        var: pyscipopt.Variable
107        for i, var in enumerate(candidates):
108            lpsol = var.getLPSol()
109            score = model.getVarPseudocostScore(var, lpsol)
110
111            scores[i] = score
112
113        return scores
114
115    def __str__(self):
116        return "Pseudocosts"

118class StrongBranching(ScoringBranchingStrategy):
119    """
120    Simple implementation of Strong Branching.
121    """
122    def __init__(self, priocands: bool = False, all_scores: bool = True):
123        """
124        Parameters
125        ----------
126        priocands : bool
127            Whether the scoring is only done on priocands
128        all_scores : bool
129            Whether all the candidates are scored. If True, the scoring is done when it is possible to cut the node
130        """
131        self.priocands = priocands
132        self.all_scores = all_scores
133
134    def compute_scores(self, model: Model) -> None:
135        scores = super().compute_scores(model)
136
137        branch_cands, branch_cand_sols, branch_cand_fracs, ncands, npriocands, nimplcands = model.getLPBranchCands()
138
139        n = npriocands if self.priocands else ncands
140        # Initialise scores for each variable
141        down_bounds = [None for _ in range(npriocands)]
142        up_bounds = [None for _ in range(npriocands)]
143
144        # Initialise placeholder values
145        num_nodes = model.getNNodes()
146        lpobjval = model.getLPObjVal()
147
148        # Start strong branching and iterate over the branching candidates
149        model.startStrongbranch()
150        for i in range(n):
151
152            # Check the case that the variable has already been strong branched on at this node.
153            # This case occurs when events happen in the node that should be handled immediately.
154            # When processing the node again (because the event did not remove it), there's no need to duplicate work.
155            if model.getVarStrongbranchNode(branch_cands[i]) == num_nodes:
156                down, up, downvalid, upvalid, _, lastlpobjval = model.getVarStrongbranchLast(branch_cands[i])
157                if downvalid:
158                    down_bounds[i] = down
159                if upvalid:
160                    up_bounds[i] = up
161                downgain = max([down - lastlpobjval, 0])
162                upgain = max([up - lastlpobjval, 0])
163                scores[i] = model.getBranchScoreMultiple(branch_cands[i], [downgain, upgain])
164                continue
165
166            # Strong branch!
167            down, up, downvalid, upvalid, downinf, upinf, downconflict, upconflict, lperror = model.getVarStrongbranch(
168                branch_cands[i], 200, idempotent=False)
169
170            # In the case of an LP error handle appropriately (for this example we just break the loop)
171            if lperror:
172                break
173
174            # In the case of both infeasible sub-problems cutoff the node
175            if downinf and upinf:
176                scores[i] = np.nan
177                continue
178
179            # Calculate the gains for each up and down node that strong branching explored
180            if not downinf and downvalid:
181                down_bounds[i] = down
182                downgain = max([down - lpobjval, 0])
183            else:
184                downgain = 0
185            if not upinf and upvalid:
186                up_bounds[i] = up
187                upgain = max([up - lpobjval, 0])
188            else:
189                upgain = 0
190
191            # Update the pseudo-costs
192            lpsol = branch_cands[i].getLPSol()
193            if not downinf and downvalid:
194                model.updateVarPseudocost(branch_cands[i], -model.frac(lpsol), downgain, 1)
195            if not upinf and upvalid:
196                model.updateVarPseudocost(branch_cands[i], 1 - model.frac(lpsol), upgain, 1)
197
198            scores[i] = model.getBranchScoreMultiple(branch_cands[i], [downgain, upgain])
199
200        return scores
201
202    def __str__(self):
203        return "StrongBranching"

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        self.observer = observer
26        self.ecole_model = None
27
28    def reset(self, model: Model) -> None:
29        self.ecole_model = ecole.scip.Model.from_pyscipopt(model)
30        self.observer.before_reset(self.ecole_model)
31
32    def callback(self, model: Model, passive: bool=True):
33        self.observation = self.observer.extract(self.ecole_model, done=False)
34        return None
35
36    def __getstate__(self):
37        return type(self.observer)
38
39    def __setstate__(self, state):
40        self.__init__(state())