Bayesian Mixed-Integer Programming — Surrogate-Assisted Optimization over Mixed-Integer Search Spaces
Also known as: Bayesian MIP, BO-MIP, Bayesian Combinatorial Optimization, Mixed-Integer Bayesian Optimization
Bayesian Mixed-Integer Programming (BO-MIP) couples a probabilistic surrogate model — typically a Gaussian process — with a mixed-integer programming solver to efficiently optimize expensive black-box objectives defined over spaces that contain both continuous and discrete or integer-valued decision variables. It is especially valuable when each function evaluation is costly and exhaustive search is infeasible.
Read the full method
Sign in with a free account to read this section.
Method map
The neighbourhood of related methods — select a node to explore.
When to use it
Use Bayesian MIP when the objective function is expensive to evaluate (each query costs significant time or money), the search space contains integer or categorical variables alongside continuous ones, and the total evaluation budget is small (tens to low hundreds of runs). It suits hyperparameter optimization in machine learning, chemical process design, facility layout, and experimental design with discrete factors. Do NOT use it when the objective is cheap to evaluate and thousands of calls are affordable — classical MIP solvers or evolutionary methods will be faster. Avoid it when the search space has very high dimensionality (>30 variables) and the surrogate becomes unreliable, or when strong problem structure (linearity, convexity) makes deterministic MIP directly tractable.
Strengths & limitations
- Sample efficiency: achieves good solutions with far fewer objective evaluations than evolutionary or random methods, making it ideal for expensive black-box problems.
- Principled uncertainty quantification: the GP surrogate provides credible intervals around predictions, supporting informed stopping and risk assessment.
- Handles mixed-integer domains natively without requiring continuous relaxation or rounding heuristics.
- Flexible acquisition functions allow explicit incorporation of constraints, multi-fidelity information, and batch parallelism.
- Works with noisy observations by modeling noise variance in the GP likelihood.
- Scalability: GP fitting scales cubically with the number of observations; performance degrades in high-dimensional spaces and with large evaluation budgets.
- Acquisition MIP complexity: the inner MIP can itself be hard to solve if the surrogate induces a non-convex or large-scale subproblem.
- Surrogate misspecification: if the GP kernel is poorly chosen, the surrogate may be an inaccurate proxy, leading to suboptimal exploration.
- Requires careful hyperparameter tuning of the surrogate (kernel, noise level) and acquisition function parameters.
- Limited theoretical guarantees for general non-convex integer domains compared to continuous Bayesian optimization.
Frequently asked
How is Bayesian MIP different from stochastic MIP?
Stochastic MIP models explicit probabilistic uncertainty in problem parameters (demands, costs) and optimizes expected or robust objectives over scenarios. Bayesian MIP uses a Bayesian surrogate to approximate an expensive black-box objective function and guides which integer-feasible points to evaluate next. The uncertainty in Bayesian MIP is epistemic — about the function value — not aleatoric uncertainty in problem data.
Can Bayesian MIP handle constraints beyond integrality?
Yes. Linear constraints can be encoded directly in the acquisition MIP. Unknown black-box constraints can be handled by fitting separate surrogate models for each constraint and incorporating constraint satisfaction probability into the acquisition function (constrained Bayesian optimization).
How many initial evaluations are typically needed before Bayesian MIP reliably guides search?
A common heuristic is max(5, 2d) initial points where d is the number of decision variables. In practice, 10–20 initial random or latin hypercube samples are often used before the acquisition loop begins, though this should be adapted to the total budget.
Which acquisition function works best for mixed-integer problems?
Expected Improvement (EI) is the most widely used baseline and often performs well. For noisy evaluations, Knowledge Gradient or Thompson Sampling can be more robust. The right choice depends on the noise level, the cost of the acquisition MIP, and whether batch evaluations are desired.
Is Bayesian MIP suitable for very large integer programs with thousands of binary variables?
Generally no. Both the GP surrogate and the acquisition MIP become intractable at very high dimension. For large-scale combinatorial problems, decomposition methods, graph neural network surrogates, or learning-to-branch approaches are more appropriate alternatives.
Sources
- Baptista, R., Poloczek, M. (2018). Bayesian Optimization of Combinatorial Structures. Proceedings of the 35th International Conference on Machine Learning (ICML), PMLR 80:462–471. link ↗
- Bonami, P., Biegler, L. T., Conn, A. R., Cornuejols, G., Grossmann, I. E., Laird, C. D., Lee, J., Lodi, A., Margot, F., Sawaya, N., Wächter, A. (2008). An algorithmic framework for convex mixed integer nonlinear programs. Discrete Optimization, 5(2), 186–204. DOI: 10.1016/j.disopt.2006.10.011 ↗
How to cite this page
ScholarGate. (2026, June 3). Bayesian Mixed-Integer Programming — Surrogate-Assisted Optimization over Mixed-Integer Search Spaces. ScholarGate. https://scholargate.app/en/simulation/bayesian-mixed-integer-programming
Which method?
Set this method beside its closest kin and read them side by side — the library lays the books on the table; the choice is yours.
- Bayesian OptimizationOptimization↔ compare
- Mixed-Integer ProgrammingSimulation↔ compare
- Multi-objective mixed-integer programmingSimulation↔ compare
- Robust Mixed-Integer ProgrammingSimulation↔ compare
- Stochastic Mixed-Integer ProgrammingSimulation↔ compare