Batching

[gdalle]

• Small problem, large batch (like BatchPDLP.jl)
• Large problem, small batch
  • Mat-mat instead of mat-vec
  • One mat-vec per stream
• Parametrizable grid size as in AcceleratedKernels.jl

What do we batch?

• Multiple starting points
• Multiple constraint or variable bound RHS
• Multiple objective vectors
• Multiple constraint matrices with the same pattern

Idea to have individual solves but running on views from the same matrix

[gdalle]

Since @maelVerbois0 seems motivated to tackle this, here's how I envision things:

• The solution should be representable either as an AbstractVector or as an AbstractMatrix. The alternative would be to put matrices everywhere, but I feel we would hit less efficient implementations when doing a mat-mat-multiplication (where the right-hand side has one column) than a mat-vec multiplication.
• Every field in MILP should accept either an AbstractVector or an AbstractMatrix too, except for the constraint matrix A.
• Most of the routines should be rewritten to be agnostic to the format of the inputs. For instance, A .+ v will add v to each column of A, while A .+ V will add the two matrices together. So A .+ v_or_V works either way.

@klamike what do you think?

[klamike]

Sounds good to me! That should work for the "Large problem, small batch" when batching starting points, RHS, or obj while keeping the code clean. Batching the constraint matrix is a bit more involved, we'd need to define a batched SpMV/SpMM, though we can probably still use multiple dispatch to make the code read as unbatched. I'm actually working on a batched SpMV for MadIPM as well. @maelVerbois0 feel free to ping me, happy to review the PRs/help with the design.

The main design question on the algorithm side is termination.. we need to decide if we want to have per-instance termination, or terminate the entire batch at once, or let the user decide. IIRC cuOpt's batch mode is using some averaged termination criterion to terminate the entire batch. I'd prefer the "let the user decide" option, perhaps default to per-instance termination. For per-instance termination, we'd want to benchmark to see if it makes sense to rearrange the batch to stay contiguous or to zero the step lengths for terminated instances.

[gdalle]

Batching the constraint matrix is a bit more involved

I think for now we should stick to a single constraint matrix, which is probably the relevant case for most applications. This also enables easier plug-and-play behavior for arbitrary matrix types.

The main design question on the algorithm side is termination

I agree that letting the user decide is best. Probably with a function kwarg setting like batch_stopping = maximum / mean / median that gets applied to the error statistics across batches?