Skip to content

MILP Solver

CloudSlash doesn't guess at right-sizing. It runs a Branch-and-Bound MILP solver against your fleet and finds the provably optimal configuration.

Tip

Translating raw cluster metrics into deterministic financial savings is a resource allocation problem mathematically equivalent to the Multi-Knapsack problem. We define the Mixed-Integer Linear Programming (MILP) equations executed within pkg/engine/solver/ to find the lowest-bound cluster provisioning costs.

The Allocation Problem

A Kubernetes cluster has \(W\) workloads with capacity requirements \((CPU_w, RAM_w)\). The cloud offers \(T\) instance types, each with monthly cost \(C_t\) and capacities \((CPU_t, RAM_t)\).

The goal: find the integer count \(x_t\) for each instance type \(t\) that minimizes total cost while satisfying aggregate workload demand with a fractional headroom factor \(P\).

Mathematical Formulation

\[ \text{Minimize} \quad Z = \sum\_{t=1}^{T} C_t \cdot x_t \]

Subject to:

  1. CPU Demand Satisfaction: $$ \sum{t=1}^{T} CPU_t \cdot x_t \ge P \cdot \sum CPU_w $$}^{W
  2. Memory Demand Satisfaction: $$ \sum{t=1}^{T} RAM_t \cdot x_t \ge P \cdot \sum RAM_w $$}^{W
  3. Integral Bounding: $$ xt \in \mathbb{Z} \quad \forall t \in {1, \dots, T} $$

Simplex Interface

The Go

Integer programming is NP-hard. The solver uses Branch and Bound over linear relaxations (Simplex), bounded by a time constraint so it doesn't stall production workflows.

// pkg/engine/solver/milp.go

type Instance struct {
    Type     string
    CPU      float64
    RAM      float64
    CostHr   float64
}

type Objective struct {
    Instances []Instance
    DemandCPU float64
    DemandRAM float64
}

// Solve Branch and Bound
func (o *Objective) SolveBranchAndBound(ctx context.Context) ([]int, float64) {
    // Standard Simplex relaxation bounds
    // ...
    // Int truncation iteration
    bestCost := math.MaxFloat64
    var bestAllocation []int

    // Recursion traverses the state tree.
    // We break iteration gracefully utilizing context deadlines (default 250ms),
    // returning the tightest valid bound discovered.
    recurseBound(0, make([]int, len(o.Instances)))

    return bestAllocation, bestCost
}

The output array feeds exact instance generation targets to the Tetris Bin Packing engine.