Optimal Solver (MIP-based)

The Optimal solver uses Mixed Integer Programming (MIP) to find provably optimal solutions. It's recommended for small to medium problems (<10,000 objects) where solution quality is critical.

How It Works

The Optimal solver:

Formulates the problem as a Mixed Integer Program (MIP)
- Binary variables: Is object X assigned to container Y?
- Linear constraints: Capacity, diversity, etc.
- Objective function: Minimize goals
Solves using external MIP solver (HiGHS, Gurobi, or XPRESS)
- Branch-and-bound search
- Cutting planes
- Presolving and heuristics
Returns optimal solution (or best found within time limit)
- Proven optimal if solved to completion
- Otherwise provides optimality gap

Supported MIP Solvers

Rebalancer supports three MIP solvers:

Solver	License	Performance	Scale	Best For
HiGHS	Open source (MIT)	Good	<5K objects	Free, open source, small problems
XPRESS	Commercial + Community	Excellent	<10K objects	Community license available
Gurobi	Commercial + Academic	Excellent	<10K objects	Academic license, best performance

HiGHS (Open Source)

Pros:

Completely free and open source (MIT license)
No license required
Good for experimentation and small problems
Active development and community

Cons:

Slower than commercial solvers
May not scale to 10K+ objects

Installation:

conda install conda-forge::highs
# or
pip install highspy

Enable in CMake following the README.md instructions.

XPRESS (Community License)

Pros:

Free community license available
Excellent performance
Scales well to 10K objects

Cons:

Requires registration
Community license has size limits
Commercial license for large-scale use

Getting Started:

Download from FICO XPRESS website
Get community license (free)
Install and add to PATH
Enable in CMake according to the README.md instructions.

Gurobi (Commercial/Academic)

Pros:

Best MIP performance
Free academic licenses
Excellent documentation and support

Cons:

Requires license
Commercial licenses expensive
Academic licenses need verification

Getting Started:

Download from Gurobi website
Get academic license (free) or purchase commercial license
Install and set license file
Enable in CMake according to the README.md instructions.

Quick Example

Python
C++

solver.addSolver(
    SolverSpecs(
        optimalSolverSpec=OptimalSolverSpec(
            solverPackage=OptimalSolverPackage.HIGHS,
            timeLimitMs=300000,  # 5 minute time limit
            mipGap=0.01,  # Stop when within 1% of optimal
        )
    )
)

solution = solver.solve()

# Check if optimal
if solution.profile.optimal:
    print("Proven optimal solution!")
else:
    gap = solution.profile.mipGap
    print(f"Solution within {gap * 100:.2f}% of optimal")

OptimalSolverSpec spec;
spec.solverPackage() = OptimalSolverPackage::HIGHS;
spec.solveTime() = 300; // 5 minute time limit

solver.addSolver(spec);

auto solution = solver.solve();

// Check if optimal solver profile is available
if (solution.problemProfile()->optimalSolverProfile().has_value()) {
  std::cout << "Optimal solver profile available!\n";
} else {
  std::cout << "No optimal solver profile\n";
}

Configuration Parameters

Parameter	Type	Default	Description
`solveTime`	int	No limit	Maximum solve time in milliseconds
`solverPackage`	enum	XPRESS	MIP solver to use (XPRESS, GUROBI, HIGHS)
`xpressArgs`	map<string, double>		Solver-specific parameters (e.g., XPRS_MIPRELSTOP, XPRS_THREADS)
`printFullLp`	bool	false	Print full LP formulation for debugging
`skipInitialAssignmentHint`	bool	false	Skip using initial assignment as warm start
`enablePartitionHeuristic`	bool	false	Enable partition-based heuristic
`simplifyLpProblem`	bool	false	Simplify LP before solving

Understanding MIP Gap

The MIP gap measures solution quality:

MIP Gap = (Upper Bound - Lower Bound) / Lower Bound

Lower Bound: Best solution found so far (feasible)
Upper Bound: Proven best possible objective (may be infeasible)
Gap = 0: Proven optimal
Gap = 0.01: Solution is within 1% of optimal

Example

Python
C++

solution = solver.solve()

if solution["profile"].optimal:
    print("Exactly optimal")
elif solution["profile"].mipGap == 0.0:
    print("Proven optimal (gap closed)")
elif solution["profile"].mipGap <= 0.05:
    print(f"Very good: within {solution["profile"].mipGap*100:.1f}% of optimal")
elif solution["profile"].mipGap <= 0.20:
    print(f"Acceptable: within {solution["profile"].mipGap*100:.1f}% of optimal")
else:
    print(f"Poor: {solution["profile"].mipGap*100:.1f}% gap - may want to increase time limit")

#include <iostream>
#include <iomanip>

auto solution = solver.solve();

if (solution.profile.optimal) {
    std::cout << "Exactly optimal\n";
} else if (solution.profile.mipGap == 0.0) {
    std::cout << "Proven optimal (gap closed)\n";
} else if (solution.profile.mipGap <= 0.05) {
    std::cout << std::fixed << std::setprecision(1);
    std::cout << "Very good: within " << solution.profile.mipGap * 100
              << "% of optimal\n";
} else if (solution.profile.mipGap <= 0.20) {
    std::cout << std::fixed << std::setprecision(1);
    std::cout << "Acceptable: within " << solution.profile.mipGap * 100
              << "% of optimal\n";
} else {
    std::cout << std::fixed << std::setprecision(1);
    std::cout << "Poor: " << solution.profile.mipGap * 100
              << "% gap - may want to increase time limit\n";
}

Performance Characteristics

Scalability

Problem Size	Typical Time	Notes
10 objects, 5 containers	<1 second	Trivial
100 objects, 20 containers	1-10 seconds	Easy
1,000 objects, 100 containers	10 seconds - 5 minutes	Moderate
5,000 objects, 500 containers	Minutes to hours	Hard
10,000 objects, 1,000 containers	Hours or timeout	Very hard
>10,000 objects	Usually infeasible	Use Local Search

Note: Times vary significantly based on:

Problem structure
Number/complexity of goals and constraints
MIP solver used (Gurobi > XPRESS > HiGHS)
Initial assignment quality

Memory Usage

MIP solvers are memory-intensive:

Small problem (100 objects): ~100 MB
Medium problem (1,000 objects): ~1-5 GB
Large problem (10,000 objects): ~10-50 GB (may OOM)

Recommendation: Monitor memory usage for problems >1,000 objects.

Solution Quality Guarantees

Proven Optimal

When mipGap == 0 and optimal == true:

Solution is provably optimal
No other solution can be better
Mathematically guaranteed

Within Gap

When mipGap > 0:

Solution is within (mipGap × 100)% of optimal
Example: mipGap = 0.05 means solution is at most 5% worse than optimal

No Solution Found

If timeout before finding any feasible solution:

Problem may be infeasible
Or just needs more time
Check solver logs

Common Patterns

Small Problem, Need Optimal

Python
C++

# Small problem, can wait for optimal
solver.addSolver(
    SolverSpecs(
        optimalSolverSpec=OptimalSolverSpec(
            solverPackage=OptimalSolverPackage.HIGHS,
            timeLimitMs=600000,  # 10 minutes
            mipGap=0.0,  # Don't stop until proven optimal
        )
    )
)

// Small problem, can wait for optimal
OptimalSolverSpec spec;
spec.solverPackage() = OptimalSolverPackage::HIGHS;
spec.solveTime() = 600; // 10 minutes

solver.addSolver(spec);

Medium Problem, Time Limited

Python
C++

# Medium problem, accept "good enough"
solver.addSolver(
    SolverSpecs(
        optimalSolverSpec=OptimalSolverSpec(
            solverPackage=OptimalSolverPackage.HIGHS,
            timeLimitMs=300000,  # 5 minutes
            mipGap=0.05,  # Stop when within 5%
        )
    )
)

// Medium problem, accept "good enough"
OptimalSolverSpec spec;
spec.solverPackage() = OptimalSolverPackage::HIGHS;
spec.solveTime() = 300; // 5 minutes

solver.addSolver(spec);

Quick Optimality Check

Python
C++

# See if we can solve quickly
solver.addSolver(
    SolverSpecs(
        optimalSolverSpec=OptimalSolverSpec(
            solverPackage=OptimalSolverPackage.HIGHS,
            timeLimitMs=60000,  # 1 minute
            mipGap=0.10,  # Accept 10% gap
        )
    )
)

// See if we can solve quickly
OptimalSolverSpec spec;
spec.solverPackage() = OptimalSolverPackage::HIGHS;
spec.solveTime() = 60; // 1 minute

solver.addSolver(spec);

Validate Local Search

Python
C++

# Run Local Search first
solver1 = ProblemSolver(service_name="example", service_scope="test")
# ... set up problem ...
solver1.addSolver(SolverSpecs(localSearchSolverSpec=LocalSearchSolverSpec()))
ls_solution = solver1.solve()

# Then run Optimal on same problem
solver2 = ProblemSolver(service_name="example", service_scope="test")
# ... set up same problem ...
solver2.addSolver(
    SolverSpecs(
        optimalSolverSpec=OptimalSolverSpec(
            solverPackage=OptimalSolverPackage.HIGHS,
            timeLimitMs=300000,
        )
    )
)
opt_solution = solver2.solve()

# Compare
gap = (
    ls_solution.objectiveValue - opt_solution.objectiveValue
) / opt_solution.objectiveValue
print(f"Local Search was {gap * 100:.1f}% from optimal")

// Run Local Search first
auto executor = std::make_shared<folly::CPUThreadPoolExecutor>(4);
ProblemSolver solver1(executor, "example", "test");
setupMinimalProblem(solver1);
LocalSearchSolverSpec lsSpec;
lsSpec.moveTypeList()->push_back(
    ProblemSolver::makeMoveTypeSpec(SingleMoveTypeSpec()));
solver1.addSolver(lsSpec);
auto ls_solution = solver1.solve();

// Then run Optimal on same problem
ProblemSolver solver2(executor, "example", "test");
setupMinimalProblem(solver2);
OptimalSolverSpec optSpec;
optSpec.solverPackage() = OptimalSolverPackage::HIGHS;
optSpec.solveTime() = 300;
solver2.addSolver(optSpec);
auto opt_solution = solver2.solve();

// Compare
const double ls_val = *ls_solution.finalObjective()->value();
const double opt_val = *opt_solution.finalObjective()->value();
const double gap = (ls_val - opt_val) / opt_val;
std::cout << "Local Search was " << (gap * 100) << "% from optimal\n";

Warm Starting

Provide an initial solution to help the MIP solver:

Python
C++

# Run Local Search first, then Optimal
solver.addSolver(
    SolverSpecs(localSearchSolverSpec=LocalSearchSolverSpec(timeLimitMs=10000))
)
solver.addSolver(
    SolverSpecs(
        optimalSolverSpec=OptimalSolverSpec(
            solverPackage=OptimalSolverPackage.HIGHS,
            timeLimitMs=60000,
        )
    )
)
# Optimal will use Local Search result as warmstart

// Run Local Search first, then Optimal
LocalSearchSolverSpec lsSpec;
lsSpec.moveTypeList()->push_back(
    ProblemSolver::makeMoveTypeSpec(SingleMoveTypeSpec()));
lsSpec.solveTime() = 10;
solver.addSolver(lsSpec);

OptimalSolverSpec optSpec;
optSpec.solverPackage() = OptimalSolverPackage::HIGHS;
optSpec.solveTime() = 60;
solver.addSolver(optSpec);
// Optimal will use Local Search result as warmstart

Warm starting can significantly speed up solving.

Debugging Slow Solving

Problem: Takes forever, no progress

Diagnosis:

Python
C++

# Check if solver is making progress
# Look at logs for bound improvements

// Check if solver is making progress
// Look at logs for bound improvements

Solutions:

Reduce problem size (fewer objects, containers)
Simplify goals/constraints (remove non-essential ones)
Increase mipGap (accept worse solution)
Use Local Search instead

Problem: Runs out of memory

Diagnosis:

Solver crashes or system OOM
Large problem (>5K objects)

Solutions:

Reduce problem size
Use Local Search instead
Add more RAM
Reduce threads (less parallel memory usage)

Problem: Can't find feasible solution

Diagnosis:

Timeout with no solution found
"Infeasible problem" error

Solutions:

Check constraints for conflicts
Relax some constraints (use as goals instead)
Increase time limit
Check initial assignment violates constraints

Problem: Gap not closing

Diagnosis:

MIP gap stuck at high value
Bounds not improving

Solutions:

Increase time limit (may take hours)
Accept current gap (stop early)
Try different MIP solver (Gurobi often better)
Simplify problem

Solver Selection

Which MIP solver to use?

Use HiGHS if:

✅ You want completely open source
✅ Small problems (<1,000 objects)
✅ Just experimenting
✅ Don't want to deal with licenses

Use XPRESS if:

✅ You have community license
✅ Medium problems (1,000-10,000 objects)
✅ Need good performance
✅ Willing to register for license

Use Gurobi if:

✅ You have academic/commercial license
✅ Need best performance
✅ Medium to large problems
✅ Already using Gurobi for other work

Note: All three use the same Rebalancer API - switching solvers is just a matter of installation.

Comparison with Local Search

Aspect	Optimal	Local Search
Solution quality	100% optimal*	95-99% of optimal
Speed	Slow (minutes-hours)	Fast (seconds)
Scalability	<10K objects	1M+ objects
Guarantees	Optimality gap	None
Memory	High (GBs)	Low (MBs)
Best for	Small problems, validation	Production, large problems

* Given enough time

Advanced Settings

Thread Control

Python
C++

# Use specific number of threads
solver.addSolver(
    SolverSpecs(
        optimalSolverSpec=OptimalSolverSpec(
            solverPackage=OptimalSolverPackage.HIGHS,
            threads=4,  # Use 4 cores
        )
    )
)

// Use specific number of threads
OptimalSolverSpec spec;
spec.solverPackage() = OptimalSolverPackage::HIGHS;

solver.addSolver(spec);

Solver Tuning

Python
C++

# Configure solver-specific parameters via xpressArgs
solver.add_solver(
        SolverSpec(
            optimalSolverSpec=OptimalSolverSpec(
    solveTime=300000,  # 5 minutes
    xpressArgs={
        "XPRS_MIPRELSTOP": 0.01,  # Stop at 1% MIP gap
        "XPRS_THREADS": 8,  # Use 8 threads
        "XPRS_PRESOLVE": 2,  # Aggressive presolving
        "XPRS_CUTSTRATEGY": 3,  # Aggressive cuts
        "XPRS_HEURSTRATEGY": 3,  # Aggressive heuristics
    },
    enablePartitionHeuristic=True,  # Enable rebalancer heuristic
)
        ))

// Configure solver-specific parameters via xpressArgs
OptimalSolverSpec spec;
spec.solveTime_ref() = 300000;  // 5 minutes
spec.xpressArgs_ref() = {
    {"XPRS_MIPRELSTOP", 0.01},  // Stop at 1% MIP gap
    {"XPRS_THREADS", 8},  // Use 8 threads
    {"XPRS_PRESOLVE", 2},  // Aggressive presolving
    {"XPRS_CUTSTRATEGY", 3},  // Aggressive cuts
    {"XPRS_HEURSTRATEGY", 3},  // Aggressive heuristics
};
spec.enablePartitionHeuristic_ref() = true;  // Enable rebalancer heuristic
solver.addSolver(spec);

Note: The xpressArgs keys depend on your chosen solver package. See XPRESS docs or Gurobi docs for available parameters.

Licensing Notes

HiGHS

MIT license
Completely free
No restrictions

XPRESS Community License

Free registration required
Size limits (check FICO website for current limits)
For academic and small commercial use
Full commercial license available for purchase

Gurobi Academic License

Free for academic use
Requires .edu email
Annual renewal
Cannot be used for commercial purposes

Gurobi Commercial License

Paid license
No restrictions
Pricing based on usage/features
Contact Gurobi for pricing

Next Steps

Learn Local Search: Local Search Guide
Performance Tuning: Performance Guide
Solver Strategies: Strategies Guide
Compare Solvers: Solver Overview

Installation - Installing MIP solvers

How It Works​

Supported MIP Solvers​

HiGHS (Open Source)​

XPRESS (Community License)​

Gurobi (Commercial/Academic)​

Quick Example​

Configuration Parameters​

Understanding MIP Gap​

Example​

Performance Characteristics​

Scalability​

Memory Usage​

Solution Quality Guarantees​

Proven Optimal​

Within Gap​

No Solution Found​

Common Patterns​

Small Problem, Need Optimal​

Medium Problem, Time Limited​

Quick Optimality Check​

Validate Local Search​

Warm Starting​

Debugging Slow Solving​

Problem: Takes forever, no progress​

Problem: Runs out of memory​

Problem: Can't find feasible solution​

Problem: Gap not closing​

Solver Selection​

Use HiGHS if:​

Use XPRESS if:​

Use Gurobi if:​

Comparison with Local Search​

Advanced Settings​

Thread Control​

Solver Tuning​

Licensing Notes​

HiGHS​

XPRESS Community License​

Gurobi Academic License​

Gurobi Commercial License​

Next Steps​

Related Documentation​

How It Works

Supported MIP Solvers

HiGHS (Open Source)

XPRESS (Community License)

Gurobi (Commercial/Academic)

Quick Example

Configuration Parameters

Understanding MIP Gap

Example

Performance Characteristics

Scalability

Memory Usage

Solution Quality Guarantees

Proven Optimal

Within Gap

No Solution Found

Common Patterns

Small Problem, Need Optimal

Medium Problem, Time Limited

Quick Optimality Check

Validate Local Search

Warm Starting

Debugging Slow Solving

Problem: Takes forever, no progress

Problem: Runs out of memory

Problem: Can't find feasible solution

Problem: Gap not closing

Solver Selection

Use HiGHS if:

Use XPRESS if:

Use Gurobi if:

Comparison with Local Search

Advanced Settings

Thread Control

Solver Tuning

Licensing Notes

HiGHS

XPRESS Community License

Gurobi Academic License

Gurobi Commercial License

Next Steps

Related Documentation