Integer variables.

This is the single page you must read if you’re using grove before v0.4 ships. Integer and Binary variables are accepted by the modeling layer but solved as the LP relaxation. Sometimes that’s fine. Sometimes it’s silently wrong. Here’s how to tell the difference.

What the LP relaxation is

Given an integer linear program (ILP), its LP relaxation is the same model with the integrality constraint dropped — x ∈ ℤ becomes x ∈ ℝ. Solving the relaxation is a standard first step in a real MIP algorithm (branch-and-bound uses it as the subproblem) but on its own it’s not the ILP.

Two things can go wrong.

Pitfall 1: non-integer LP optimum

The LP relaxation’s optimal vertex sometimes happens to have integer coordinates and sometimes does not. If it does, the LP answer is also the ILP answer (this is a textbook result; the integer hull and the LP feasible region share that vertex). If it doesn’t, the LP optimum is a bound on the ILP optimum, not the ILP optimum itself.

• For a Maximize problem, the LP optimum is an upper bound on z*_ILP.
• For a Minimize problem, the LP optimum is a lower bound on z*_ILP.

The gap between the two is the integrality gap. For some problem classes it is zero in practice (network flow, assignment, matching on bipartite graphs). For others — most scheduling, most packing — it’s meaningful.

Pitfall 2: LP-feasible, ILP-infeasible

This is the sharp one. The LP relaxation can be feasible and return an optimum even when the ILP has no feasible integer solution at all. grove v0.1 will report Status = Optimal with a non-integer vector; CBC or HiGHS would correctly report Infeasible.

A minimal example. The following ILP is genuinely infeasible — no integer pair (x1, x2) can satisfy 0.5 ≤ x1 − x2 ≤ 0.75:

p := grove.NewProblem("tricky", grove.Minimize)
x1 := p.NewVar("x1", grove.Integer, grove.Bounds(-1, 1))
x2 := p.NewVar("x2", grove.Integer, grove.Bounds(-1, 1))
x3 := p.NewVar("x3", grove.Integer, grove.Bounds(-1, 1))
p.SetObjective(grove.Expr{x1: 2, x2: -3, x3: 1})
p.AddConstraint("c1", grove.Expr{x1: 1, x2: -1}, grove.GTE, 0.5)
p.AddConstraint("c2", grove.Expr{x1: 1, x2: -1}, grove.LTE, 0.75)
p.AddConstraint("c3", grove.Expr{x2: 1, x3: -1}, grove.LTE, 1.25)
p.AddConstraint("c4", grove.Expr{x2: 1, x3: -1}, grove.GTE, 0.95)

r, _ := p.Solve()
// grove v0.1:    r.Status == Optimal,   z* = -0.25, (x1, x2, x3) = (0.75, 0.25, -1)
// PuLP / CBC:    r.Status == Infeasible

In a continuous world this model has a perfectly fine vertex at (0.75, 0.25, -1). In an integer world, there is simply no pair of integers in [-1, 1] whose difference lies between 0.5 and 0.75 (the closest feasible differences are 0 and 1). A true MIP solver knows this; a pure LP solver does not.

How grove protects you

Every Solve runs a post-solve integrality check. If the problem declares any Integer or Binary variables and any of them come back non-integer (within a tolerance of 1e-6), grove does three things:

1. Appends a warning to Result.Warnings.
2. Folds the same text into Result.Message.
3. Makes the list of offending variables available via Result.NonIntegerIntegerVars(p) []*Var.

res, _ := prob.Solve()
if len(res.Warnings) > 0 {
    for _, w := range res.Warnings {
        log.Printf("grove warning: %s", w)
    }
}
for _, v := range res.NonIntegerIntegerVars(prob) {
    log.Printf("non-integer in integer var %s: %g", v.Name(), res.Value(v))
}

The warning prefix is exposed as a stable constant so you can gate CI on it:

for _, w := range res.Warnings {
    if strings.HasPrefix(w, grove.WarnLPRelaxationOnly) {
        return fmt.Errorf("ILP relaxed to LP for model %q — refusing to promote", prob.Name())
    }
}

Rule of thumb until v0.4

For the bottom row, use grove’s result as an upper bound (if you’re maximising) or a lower bound (if you’re minimising) on the true ILP optimum. To get an actual ILP answer, either wait for v0.4 or pass the same model into HiGHS via the Python or C interface — grove can write MPS for you, see File I/O.

Why grove doesn’t just reject integer models

Because the majority of ILPs people write have integer-valued LP vertices; totally-unimodular constraint matrices are common. Rejecting those would be surprising-in-a-different-way. grove takes the middle path: accept the model, solve the relaxation, tell you when the relaxation lied.

The same philosophy applies to the HiGHS backend stub in v0.1 — it accepts the same Solver interface shape so you can wire it into your code today, and it will start returning real answers as soon as v0.3 lands.