Drift-Weighted Local Branching for Interactive Mixed-Integer Optimization

When a person uses an optimization system to plan a trip, a schedule or a portfolio, they rarely state their goals once. They look at a proposed plan, change their mind about some things, discover new requirements because of what they saw, and ask again. Each request is a new mixed-integer linear program (MILP, an optimization problem with some yes/no or integer decisions), and it must be answered within seconds. Systems that connect conversation to exact solvers today, such as LAPPI, which uses an LLM to turn dialogue into solver parameters, simply re-solve every turn from scratch. Methods that reuse earlier solves, such as Don't Restart, Just Reuse, were designed for parameter changes driven by outside events like demand noise, not by a user reacting to the system's own outputs.

This proposal makes one bet. Across the turns of an interactive session, the plan changes in a small and predictable set of decisions. These are the decisions tied to preferences the user is still forming. The rest are effectively settled. The system can exploit this with a local branching constraint, which limits the solver to solutions that differ from a reference solution in at most $k$ decisions. Our version is cheap: we weight each decision by how stable it has been over recent turns, with older turns discounted over time. Stable decisions are expensive to change and volatile ones are free. The constraint needs no neural network at interaction time and keeps the solver exact. It also opens up exactly the decisions touched by a newly triggered preference, which is where a uniform neighborhood around yesterday's plan fails.

Core Claim

Let $\bar x^{(t-1)}$ be the binary solution shown to the user at turn $t-1$. Each binary variable $j$ gets a weight $w_j^{(t)} \in [0,1]$. The next solve adds the constraint

$$\sum_{j:\,\bar x_j^{(t-1)}=1} w_j^{(t)}(1-x_j) + \sum_{j:\,\bar x_j^{(t-1)}=0} w_j^{(t)} x_j \le k_t .$$

With all $w_j = 1$, this is the standard local branching constraint used by Ding et al. and Liu, Fischetti and Lodi. Our weights come from turn-to-turn change history:

$$w_j^{(t)} = 1 - \frac{\sum_{\tau<t}\gamma^{\,t-1-\tau}\,\mathbb{1}[\bar x_j^{(\tau)} \ne \bar x_j^{(\tau-1)}]}{\sum_{\tau<t}\gamma^{\,t-1-\tau}} .$$

Here $\gamma \in (0,1]$ is a recency discount. It plays the same role as the exponential weight that NS-DPO applies to old preference comparisons when training language models under drift. When the current turn adds a new constraint or changes an objective term, every variable appearing in it gets $w_j = 0$. The radius $k_t$ is set from the decayed history of turn-to-turn Hamming distances, which count how many decisions changed between consecutive turns. A change detector, of the kind used in interactive evolutionary optimization under drift, resets the history when the user's objective shifts sharply.

Exactness is preserved in the usual local branching way. If the restricted problem is infeasible or stops improving within its time slice, the solver adds the reverse inequality, which excludes that neighborhood, and continues on the remainder of the full problem.

The claim is falsifiable. Weighted local branching should beat uniform local branching only when turn-to-turn changes are concentrated on few variables. We will measure this concentration directly, as the entropy of the discounted flip distribution, and test whether the method's advantage tracks it.

Relation to Prior Work

Three lines of work supply the method.

  • Solution prediction and radius learning. Ding et al. predict binary values with a graph network and wrap a Hamming ball around the prediction. Liu et al. show that the radius $k$ is decisive and learn to adapt it with reinforcement learning.
  • Learned bounds after perturbation. Lodi, Mossina and Rachelson show that a single learned cardinality constraint around a reference solution rarely cuts off the optimum after capacity perturbations, with a 0.03% average gap after one hour.

All three treat every variable symmetrically within one instance or across exogenous perturbations. We change the geometry of the neighborhood, not just its size, and we derive that geometry from interaction history rather than from instance features.

Two lines of work motivate the proposal.

  • Exposure-triggered preferences. AcCoRD shows that preferences triggered by seeing an option are where frontier agents fail, with scores as low as 0.09.
  • Concept evolution. Liu, Sarkar et al. show that users' concepts evolve as they see outputs, producing contradictory feedback.

Together these say that drift is endogenous and localized, which is the structure our weights encode.

Two results constrain the design.

  • Inference overhead. Distributional MIPLIB reports that graph-network inference overhead made ML guidance worse than plain SCIP on transmission switching (primal-dual integral 27.9 vs 20.0). This is why our core mechanism has no network forward pass.
  • Matrix changes. The MIP Workshop 2023 reoptimization competition shows that changes to the constraint matrix remain unsolved. We therefore restrict ourselves to objective, bound, right-hand-side and added-row changes, which is what preference updates mostly produce.

VP-OR is the closest competitor. It fixes about 70% of variables using graph-network marginals plus Thompson-sampling refinement under 10-second budgets. However, it conditions on the previous instance's search tree, not on a multi-turn history, and it was evaluated only on exogenous series.

Research Program

We will build three things.

1. A simulated-user testbed with endogenous drift. The simulated user holds a latent linear utility over objective components and a latent set of hard requirements. The utility drifts with a dependency parameter, as in the iEMOA drift study. Requirements are revealed following the AcCoRD taxonomy:

  • some are omitted at first;
  • some are triggered only when the displayed solution contains a specific feature;
  • some are unachievable and must later be relaxed.

The underlying problems are of two kinds. The first is itinerary-selection MILPs built from AcCoRD-Travel scenarios, which average 11.25 preferences each and are formulated as orienteering problems as in LAPPI. The second is set covering and combinatorial auction distributions from Distributional MIPLIB at Medium and Hard tiers, where the objective is a user-weighted mixture of several cost vectors. We choose these tiers deliberately, so that a from-scratch solve does not finish within the interaction budget.

2. The weighted local branching controller. We implement it in SCIP as a sub-MIP with reverse-cut fallback. The controller adds under a millisecond of overhead per turn.

3. An analysis of when it should work. This relates the advantage over uniform local branching to the measured flip-distribution entropy and to the drift rate. We will also test whether $\gamma$ can be set online from the change detector, rather than requiring a known bound on total drift. That bound is the open problem NS-DPO leaves.

As a non-interactive sanity check, we run the same controller on the competition's obj and rhs series. There, the "history" is the sequence of earlier instances.

Baselines

Do-nothing reference. This is default SCIP re-solving each turn from scratch with the same per-turn time limit, on a single thread, matching the competition protocol. It shows whether any reuse matters at our instance sizes.

MIP-start reference. This is SCIP given the previous turn's solution as a MIP start, or its repaired version when the start is infeasible. It is the simplest form of reuse.

Uniform local branching with a learned radius. This is the ablation that isolates our key ingredient: lb-srmrl adapting $k$ around $\bar x^{(t-1)}$ with all weights equal to one. That paper reports reducing the primal integral on Large Set Covering from 59.306 to 2.424. It is the strongest published radius controller, so if our weights add nothing beyond what a well-chosen uniform $k$ achieves, this baseline will show it.

VP-OR applied per turn. This is the strongest existing method. Zhang et al. report a relative primal gap of 0.00 on rhs_1, against 193.04 for Predict-and-Search, and VP-OR was the only method to find feasible solutions on all bnd_2 and bnd_3 instances within 10 seconds. We will train it on the same simulated sessions, with the same number of training instances and the same hyperparameter search budget as our controller's $\gamma$ and radius settings. Its graph-network inference time will count against the per-turn budget.

No reported result was found on Lacuna for any method on interactive, endogenously drifting MILP sessions. All interactive comparisons will therefore be run fresh.

Further ablations. We also run our method with $\gamma = 1$ (no forgetting), with a window of one turn, with random weights of equal total mass, and with oracle weights that zero exactly the variables that change in the true next-turn optimum. The oracle gives an upper bound on what any weighting can achieve.

What counts as beating a baseline. Beating a baseline means a lower mean per-turn primal gap, relative to each turn's true optimum, at 1, 5 and 10 second budgets. It also requires no increase in the fraction of turns that end with no feasible solution. The improvement must be significant across at least 200 simulated sessions per domain.

Why not just…?

Why not just re-solve from scratch, since interactive instances are small? For LAPPI-scale problems this may well suffice, and we will report the instance size below which it does. The claim only matters where re-solving misses the latency budget. The competition results suggest that this regime is real: default SCIP found no feasible solution within 10 seconds on bnd_2 and bnd_3. Our harder Distributional MIPLIB tiers are chosen to test it.

Why not just warm-start from the previous plan? A MIP start offers no guidance once a triggered requirement makes the old plan infeasible, and preference changes are exactly such additions. The MIP-start baseline measures this directly. Our infeasible-turn rate on triggered-preference turns is the decisive comparison.

Why not just tune the radius of ordinary local branching? Liu et al. show that radius matters enormously. A uniform ball around an outdated plan must grow large to reach the user's newly wanted region, and a large ball is nearly as hard as the full problem. Weighting is meant to make the ball long in the volatile directions and short in the stable ones. If lb-srmrl matches us, the concentration hypothesis is wrong. The entropy analysis is designed to show this.

Why not just run VP-OR each turn? This is the real threat. Objective and bound changes are within VP-OR's competence. Two things can still separate the methods. First, VP-OR's graph-network inference may not fit 1-second budgets. Second, a single previous tree cannot reveal which decisions are persistently volatile across many turns. If VP-OR wins at 10 seconds, we will test a hybrid that seeds VP-OR's Beta priors with our stability scores. We will then report which component carries the gain, rather than claim the standalone controller is better.

Why not just discount old preferences in the objective, NS-DPO style, and re-solve? That decides what to optimize, not how quickly the solver finds it. Our simulated user's latent utility is given to every method, so this alternative reduces to the do-nothing baseline on the solver side. It is complementary to our method, not a competitor.

Decisive Checks

The first check is the oracle-weight ablation. If oracle weights do not clearly beat uniform local branching at a matched radius, then neighborhood geometry is not the bottleneck and the project should stop.

The second check is a correlation test. Gains over lb-srmrl should rise as the flip-distribution entropy falls. Such a correlation would show that the mechanism works for the reason we claim.

The third check is behavior on turns where a preference is triggered. There, our controller should cut the no-feasible-solution rate relative to both uniform local branching and VP-OR, because only it frees exactly the variables the new requirement touches.

The fourth check is the competition obj and rhs series, where the method should not lose to uniform local branching. Losing there would mean the weights overfit to session structure that exogenous sequences lack.