Heuristics

For the following let us assume that a Model object is available, which is created as follows:

from pyscipopt import Model, Heur, SCIP_RESULT, SCIP_HEURTIMING, SCIP_LPSOLSTAT

scip = Model()

What is a Heuristic?

A (primal) heuristic is an algorithm for finding a feasible solution to an optimization problem at lower computational costs than their exact counterparts but without any optimality guarantees. The reason that heuristics are implemented in exact optimization solvers are two-fold. It is advantageous for certain algorithms to have a good intermediate solution, and it is helpful for users that they can halt the solving process and access the current best solution.

Simple Rounding Heuristic Example

In this example we show how to implement a simple rounding heuristic in SCIP. The rounding heuristic will take all the fractional variables with integer requirements from the current relaxation solution, and attempt to round them to their nearest integer values.

class SimpleRoundingHeuristic(Heur):

    def heurexec(self, heurtiming, nodeinfeasible):

        scip = self.model
        result = SCIP_RESULT.DIDNOTRUN

        # This heuristic does not run if the LP status is not optimal
        lpsolstat = scip.getLPSolstat()
        if lpsolstat != SCIP_LPSOLSTAT.OPTIMAL:
            return {"result": result}

        # We haven't added handling of implicit integers to this heuristic
        if scip.getNImplVars() > 0:
            return {"result": result}

        # Get the current branching candidate, i.e., the current fractional variables with integer requirements
        branch_cands, branch_cand_sols, branch_cand_fracs, ncands, npriocands, nimplcands = scip.getLPBranchCands()

        # Ignore if there are no branching candidates
        if ncands == 0:
            return {"result": result}

        # Create a solution that is initialised to the LP values
        sol = scip.createSol(self, initlp=True)

        # Now round the variables that can be rounded
        for i in range(ncands):
            old_sol_val = branch_cand_sols[i]
            scip_var = branch_cands[i]
            may_round_up = scip_var.varMayRound(direction="up")
            may_round_down = scip_var.varMayRound(direction="down")
            # If we can round in both directions then round in objective function direction
            if may_round_up and may_round_down:
                if scip_var.getObj() >= 0.0:
                    new_sol_val = scip.feasFloor(old_sol_val)
                else:
                    new_sol_val = scip.feasCeil(old_sol_val)
            elif may_round_down:
                new_sol_val = scip.feasFloor(old_sol_val)
            elif may_round_up:
                new_sol_val = scip.feasCeil(old_sol_val)
            else:
                # The variable cannot be rounded. The heuristic will fail.
                continue

            # Set the rounded new solution value
            scip.setSolVal(sol, scip_var, new_sol_val)

        # Now try the solution. Note: This will free the solution afterwards by default.
        stored = scip.trySol(sol)

        if stored:
            return {"result": SCIP_RESULT.FOUNDSOL}
        else:
            return {"result": SCIP_RESULT.DIDNOTFIND}

To include the heuristic in the SCIP model one would use the following code:

heuristic = SimpleRoundingHeuristic()
scip.includeHeur(heuristic, "SimpleRounding", "custom heuristic implemented in python", "Y",
                 timingmask=SCIP_HEURTIMING.DURINGLPLOOP)

Note

The timingmask is especially important when programming your own heuristic. See here for information on timing options and how the affect when the heuristic can be called. Note also that heuristics are, as other plugins, called in order of their priorities.

Note

When you create a SCIP solution object it is important that you eventually free the object. This is done by calling scip.freeSol(sol), although this is not necessary when the solution has been passed to scip.trySol(sol) with free=True (default behavior).