REVIEW 3 major objections 5 minor 1 cited by
MiSSOC solves challenging mixed-integer nonlinear programs by replacing complicated functions with shape-constrained sums of B-spline curves, then exploits the resulting separable structure to find high-quality solutions fast.
Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →
T0 review · deepseek-v4-flash
2026-08-04 09:36 UTC pith:TDU6HUIT
load-bearing objection MiSSOC is a sensible surrogate-MINLP pipeline with a real methodological addition, but the experiments don't yet isolate what the surrogate actually contributes. the 3 major comments →
On leveraging constrained smooth additive regression models for global optimization
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
The central claim is that a nonconvex MINLP, whose bottleneck is a complicated objective or constraint function, can be solved effectively by first sampling that function, fitting a smooth additive B-spline approximation with optional shape constraints, and then solving the resulting surrogate as an MINLP with separable structure. The paper argues that this surrogate is accurate enough that its optimal solution, after a local-search refinement, matches or improves solutions found by general-purpose global solvers on the original problem. In the reported experiments, solving the surrogate with the SC-MINLP algorithm yields near-zero optimality gaps in fractions of a second, while direct solve
What carries the argument
The central object is the smooth additive regression model: each complicated function g is approximated as a constant plus a sum of univariate B-spline functions over the box defined by variable bounds. B-splines are piecewise polynomials joined at knots, so the fitted function is a sum of univariate piecewise polynomials. Expert knowledge enters through conic positive-semidefinite constraints, adapted from univariate shape-constrained smoothing, that enforce bounds, monotonicity, or curvature on each additive component. The surrogate is then written as a mixed-integer program using a multiple-choice formulation, where each knot interval contributes a binary variable; this formulation has se
Load-bearing premise
The whole approach depends on the complicated function being well represented as a sum of univariate B-spline curves across the variable bounds, so that the surrogate's optimum tracks the true optimum; the paper gives no error bound to certify this approximation.
What would settle it
Take a test MINLP whose objective contains a strong interaction term, such as x1*x2*x3, fit the additive B-spline surrogate, and solve it. Then compare the true objective value at the surrogate's solution with the best value found by a reliable global solver on the original problem: if the surrogate's solution is consistently much worse while its in-sample fit is excellent, the additivity assumption is the failure point.
If this is right
- If the central claim holds, hard nonconvex MINLPs with complex objectives can be approached by sampling and spline fitting instead of direct global optimization, often with dramatic time savings.
- Combining surrogate building with SC-MINLP can produce zero or near-zero optimality gaps on the surrogate, meaning the separable structure of B-spline sums is the key to tractability.
- Shape constraints allow practitioners to inject domain knowledge—such as known output bounds or monotonic behavior—into the surrogate, so the optimization respects qualitative physical or economic facts.
- The same machinery extends to approximating constraint functions, opening a route to surrogate-based feasibility recovery for problems where constraints, not just the objective, are the complication.
- The reported improvement over the best known solution of a real hydroelectric scheduling instance suggests the method can yield practically better decisions, not just faster ones.
Where Pith is reading between the lines
- Beyond the paper: the additive form limits MiSSOC to problems where interactions between variables are weak; for interaction-heavy functions, one would expect the surrogate to miss ridges and valleys, so a natural extension is adding bivariate spline terms or an interaction-detection pre-pass.
- Beyond the paper: uniform random sampling may be wasteful; an adaptive sampling strategy that concentrates points near promising regions, as the paper lists as future work, would likely improve both approximation quality and final solution value.
- Beyond the paper: the weights that allocate the global bound among additive components are currently fixed by data; treating them as decision variables in the fitting problem could tighten the bounds and make the surrogate more faithful.
- Beyond the paper: if shape constraints were chosen so the surrogate under- or overestimates the original function, the surrogate would become a certified relaxation or restriction of the original MINLP, turning a heuristic into a method with provable bounds.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper introduces MiSSOC, a surrogate-based algorithm for nonconvex MINLPs. Complicating functions (initially the objective) are approximated by constrained smooth additive B-spline regression models; the resulting surrogate is cast as an MINLP with a multiple-choice formulation and solved with SC-MINLP or general-purpose global solvers, followed by a local NLP polish on the original problem. The methodological contribution includes a conic formulation for shape-constrained additive regression. Experiments are reported on three MINLPlib instances and a Hydro Unit Commitment case study, with comparisons against direct global-solver runs. The central claim is that MiSSOC, especially with SC-MINLP, is a competitive algorithm for challenging MINLPs.
Significance. If the empirical claims are established, the paper offers a useful and original integration of statistical shape-constrained regression into MINLP surrogate construction. The use of additive separable spline surrogates is well matched to the SC-MINLP solver, and the public code/data repositories are a strength. The methodological extension from univariate to additive shape constraints, while sufficient-only for the sum constraint, is a plausible contribution. However, the experimental section as written does not yet support the abstract's and Section 6's competitiveness claim: the reported advantages are not isolated from the effect of the final local search, the optimality gap is reported for the surrogate rather than the original problem, and the randomness of the sampling phase is not controlled. These are fixable with additional experiments and careful reporting.
major comments (3)
- [§5, Algorithm 1 and Tables 2/4] The central competitiveness claim is not supported without a random-multistart + local-search control. Algorithm 1's final step fixes the surrogate's integer decisions and solves an NLP with IPOPT; on the three MINLPlib instances there are no integer variables at all, so the pipeline is surrogate-selection plus local NLP polish. The paper compares only to 600-second runs of global solvers, not to a simple baseline that samples many starting points/integer assignments and applies the same IPOPT local search. Such a baseline is needed to separate the contribution of the additive B-spline surrogate from the contribution of local search and instance structure. The concern is concrete: in Table 2, MiSSOC's value on ex6_2_5 (-70.558) is worse than the MINLPlib best (-70.752) that BARON and COUENNE find directly, so the only reported advantage on that instance is time-to-solution. Without the c
- [§5, Eq. (23)] The optimality gap reported for the surrogate problem is not a gap for the original MINLP. Equation (23) is explicitly 'computed in the solution of the surrogate problem (P~), that is, before the local search phase.' A zero or near-zero gap in Tables 2 and 4 only shows that the fitted surrogate was solved to optimality. Since Section 1 acknowledges that MiSSOC 'cannot guarantee an error bound over the entire domain,' a zero surrogate gap can coexist with substantial suboptimality or infeasibility in the original problem. The narrative in §5.1 and §5.2 repeatedly uses the small surrogate gaps as evidence of solution quality. The paper should report a gap or bound for the original problem (e.g., against a valid dual bound or best-known value), or explicitly and consistently label the reported gap as a surrogate-solving metric only.
- [§5.1 and §5.2] The experiments use one run per configuration despite random training-data sampling. Section 4.3 specifies that the training set T is generated by uniform random sampling, and Section 5.1 states '15 samples per parameter' are drawn. None of the reported times, objective values, or gaps are accompanied by repeated seeds, standard deviations, or median/min-max summaries. This is important because the training sample directly determines the fitted surrogate and hence the final solution. For example, the near-instantaneous SC-MINLP times (0.028s in Table 2) and the degree-dependent HUC results in Table 4 may be particular to one draw. The authors should either report repeated runs with different seeds or justify that the results are stable across sampling.
minor comments (5)
- [§4.2, constraints (21)-(22)] The text says 'Constraints (21), (21) and (22) stated the nature of all the variables.' The duplicate '(21)' should be '(21), (22)' or similar, and 'stated' should be 'state.'
- [§2.3] There is a typo: 'More specifically, (Bj)il = Bl,dj,tj (xij), for i = 1, . . . , n and l = 1, . . . , kk + dj' — 'kk' should be 'kj.'
- [§6] The phrase 'proves that MiSSOC is a competitive algorithm' is too strong given the experimental limitations discussed above. Recommend 'indicates' or 'provides evidence that.'
- [§5.2, Table 4] The claim that degrees 5-7 'improve' the published value 14533.1 should be stated with the sense of the objective (maximization) explicitly in the surrounding text, since the same table is used for the minimization MINLPlib instances. This is clear from context but should be made explicit to avoid confusion.
- [§5, sampling size rule] The rule '15 samples per parameter' is introduced without justification or sensitivity analysis. A brief comment on why 15 is sufficient, or a small sensitivity study, would strengthen the sampling discussion.
Circularity Check
MiSSOC is not a circular derivation overall: the surrogate is fit to samples and final solutions are re-evaluated on the original objective. The main circularity-adjacent flaw is that the surrogate's own zero optimality gap (Eq. 23) is presented as evidence of original solution quality, even though it only certifies that the fitted, separable surrogate was solved.
specific steps
-
fitted input called prediction
[Section 5.1, Eq. (23), Table 2 (~P rows); similar use in Table 4]
"The optimality gap is computed in the solution of the surrogate problem (~P), that is, before the local search phase. We follow the formula as implemented in Gurobi v. 12.0.1: optimality gap= 100·|upper bound−lower bound|/|upper bound|, where the upper bound and lower bound are those reported by the corresponding solver."
Eq. (23)'s upper/lower bounds are bounds on the fitted surrogate objective ~g0, not on the original g0. A zero/near-zero gap therefore means only that the solver optimized the fitted model; this is by construction, since the surrogate was built to be a separable sum of univariate polynomials and SC-MINLP solves such problems to optimality. The paper then uses this tautological value as evidence of high solution quality: 'Of particular interest is SC-MINLP, which achieves a zero or near-zero optimality gap in all three surrogate instances.' Since the paper admits it has no error bound over the entire domain, the surrogate gap cannot certify anything about g0. Thus quality evidence is partly drawn from a metric whose value is forced by the fitting/solving setup.
full rationale
The core derivation chain — sample g0, fit an additive B-spline surrogate, solve the surrogate, then evaluate g0(x*) — is not circular: g0(x*) is always re-evaluated on the original function, and the paper explicitly acknowledges that an optimal solution of the surrogate is only a heuristic solution of the original problem. Self-citations (Navarro-García et al. for univariate shape constraints; D'Ambrosio et al. and Spencer Trindade et al. for SC-MINLP) are used as methodological tools, not as premises that smuggle in the conclusion; the novel additive extension is tested directly. The main weaknesses are experimental and statistical, not circularity: the final local search with IPOPT means the reported g0(x*) is not attributable solely to the surrogate, no random-multistart plus local-search control is provided, and the additivity assumption has no error bound. These are validity concerns rather than derivation circularity. The one partially circular element is the surrogate optimality-gap metric: because it is defined on the fitted model, its value reduces to whether the solver solved the fitted model, and using it as evidence about original-problem solution quality is a fitted-input-called-prediction step. Since direct g0 comparisons provide independent evidence for the competitiveness claim, the overall score is 4 rather than higher.
Axiom & Free-Parameter Ledger
free parameters (5)
- B-spline regression coefficients θ_jl =
estimated by least-squares (Eq. 10) or conic problem (Eq. 14)
- Number of intervals k_j and degree d_j =
k_j=10, d_j=3 for benchmarks; d_j=1..7 and k_j=10 for HUC
- Weight allocation ω_L_j, ω_U_j =
normalized minima/maxima of unconstrained fit (Section 3)
- Training sample size ratio =
15 samples per parameter
- Knot placement =
equidistant knots on each variable range
axioms (6)
- domain assumption Original objective can be approximated as a sum of univariate functions over the box domain.
- domain assumption Uniform random sampling over the box produces a training set representative of regions relevant to optimality.
- standard math B-spline representation and polynomial nonnegativity conditions (Bertsimas & Popescu, 2002) are valid for the piecewise polynomials.
- domain assumption Zero-mean identifiability constraint does not change the optimization-relevant shape of the approximation.
- standard math Sufficient component-wise bounds in Eq. (13) with weights summing to 1 imply the global bound in Eq. (12).
- domain assumption The NLP local search with IPOPT finds a meaningful local optimum from the surrogate warm start.
read the original abstract
Many real-world decision-making processes rely on solving mixed-integer nonlinear programs (MINLPs). However, finding high-quality solutions to MINLPs is often computationally demanding, motivating the development of specialized algorithms to improve their tractability. In this work, we propose Mixed-Integer Smoothing Surrogate Optimization with Constraints (MISSOC), a novel optimization algorithm that builds and solves approximations of challenging MINLPs. MISSOC approximates complicating functions in an MINLP using smooth additive regression models with \unboldmath{$B-$}splines. Expert knowledge can be incorporated into the approximating functions through shape constraints related to bounds, monotonicity and curvature over the observed domain. A surrogate of the original problem is then obtained by replacing the original complicating functions with their approximations, making it more tractable in practice. MISSOC presents an innovative integration of statistical modeling into mathematical optimization and fills a gap in the literature by building surrogates that are both data-driven and knowledge-driven. The proposed algorithm is illustrated on the real-world Water Distribution Network problem and evaluated through a set of experiments that include benchmark instances and the real-world Hydro Unit Commitment problem. Together, they demonstrate that MISSOC handles MINLPs with integer variables and complicating functions appearing in the objective or in the constraints. MISSOC is evaluated with different state-of-the-art solvers and with the Sequential Convex MINLP (SC-MINLP) algorithm. The latter exploits the separable structure of the approximating functions, which are sums of piecewise univariate polynomials. The experiments show that MISSOC can obtain high-quality solutions for challenging MINLPs, particularly when used in combination with the SC-MINLP algorithm.
Figures
Forward citations
Cited by 1 Pith paper
-
Automatic knot selection in smooth additive models
AKSSAM extends adaptive-spline knot selection to generalized additive models with automatic Fellner-Schall penalty tuning, yielding sparse models with comparable fit.
Reference graph
Works this paper leans on
-
[1]
Belotti, P., Kirches, C., Leyffer, S., Linderoth, J., Luedtke, J., & Mahajan, A. (2013). Mixed-integer nonlinear optimization.Acta Numerica,22, 1–131
2013
-
[2]
Belotti, P., Lee, J., Liberti, L., Margot, F., & Wächter, A. (2009). Branching and bounds tightening techniques for non-convex MINLP.Optimization Methods & Software,24(4-5), 597–634
2009
-
[3]
Bertsimas, D., & Margaritis, G. (2025). Global optimization: a machine learning approach.Journal of Global Optimization,91, 1–37. 28
2025
-
[4]
Bertsimas, D., & Öztürk, B. (2023). Global optimization via optimal decision trees. Journal of Global Optimization, 1–41
2023
-
[5]
Bertsimas, D., & Popescu, I. (2002). On the relation between option and stock prices: a convex optimization approach.Operations Research,50(2), 358–374
2002
-
[6]
Bhosekar, A., & Ierapetritou, M. (2018). Advances in surrogate based modeling, fea- sibility analysis, and optimization: A review.Computers & Chemical Engineering, 108, 250–267
2018
-
[7]
A., & Thomas, R
Blekherman, G., Parrilo, P. A., & Thomas, R. R. (2012).Semidefinite optimization and convex algebraic geometry. Philadelphia: SIAM
2012
-
[8]
T., Conn, A
Bonami, P., Biegler, L. T., Conn, A. R., Cornuéjols, G., Grossmann, I. E., Laird, C. D., ... Wächter, A. (2008). An algorithmic framework for convex mixed integer nonlinear programs.Discrete Optimization,5(2), 186–204
2008
-
[9]
Borghetti, A., D’Ambrosio, C., Lodi, A., & Martello, S. (2015). Optimal scheduling of a multiunit hydro power station in a short-term planning horizon. InCase studies in operations research(pp. 167–181). New York: Springer
2015
-
[10]
Boukouvala, F., & Floudas, C. A. (2017, 6 1). Argonaut: Algorithms for global optimization of constrained grey-box computational problems.Optimization Letters, 11(5), 895–913
2017
-
[11]
Burer, S., & Letchford, A. N. (2012). Non-convex mixed-integer nonlinear program- ming: A survey.Surveys in Operations Research and Management Science,17(2), 97–106
2012
-
[12]
R., Drud, A
Bussieck, M. R., Drud, A. S., & Meeraus, A. (2003). MINLPLib—a collection of test models for mixed-integer nonlinear programming.INFORMS Journal on Computing,15(1), 114–119
2003
-
[13]
U., & Gendron, B
Codsi, J., Ngueveu, S. U., & Gendron, B. (2025, 6 1). Lina: a faster approach to piecewise linear approximations using corridors and its application to mixed-integer optimization.Mathematical Programming Computation,17(2), 265–306. Cplex ILOG, I. B. M. (2024).V22.1.2: User’s manual for cplex.(Available from IBM: https://www.ibm.com/products/ilog-cplex-opt...
2025
-
[14]
Curmei, M., & Hall, G. (2025). Shape-constrained regression using sum of squares polynomials.Operations Research,73(1), 543–559. De Boor, C. (1978).A practical guide to splines(Vol. 27). New York: Springer
2025
-
[15]
Duguet, A., & Ngueveu, S. U. (2022). Piecewise linearization of bivariate nonlinear functions: Minimizing the number of pieces under a bounded approximation error. In I. Ljubić, F. Barahona, S. S. Dey, & A. R. Mahjoub (Eds.),Combinatorial optimization(pp. 117–129). Cham: Springer International Publishing. D’Ambrosio, C., Frangioni, A., & Gentile, C. (2019...
2022
-
[16]
O., Maragno, D., & den Hertog, D
Fajemisin, A. O., Maragno, D., & den Hertog, D. (2024). Optimization with constraint learning: A framework and survey.European Journal of Operational Research, 314(1), 1–14
2024
-
[17]
S., Karimi, I
Garud, S. S., Karimi, I. A., & Kraft, M. (2017). Design of computer experiments: A review.Computers & Chemical Engineering,106, 71–95. Geißler, B., Martin, A., Morsi, A., & Schewe, L. (2012). Using piecewise linear functions for solving MINLPs. In J. Lee & S. Leyffer (Eds.),Mixed integer nonlinear programming(Vol. 154, pp. 287–314). New York: Springer
2017
-
[18]
Grimstad, B., & Sandnes, A. (2016). Global optimization with spline constraints: a new branch-and-bound method based on B-splines.Journal of Global Optimization, 65, 401–439. Gurobi Optimization, L. L. C. (2024).Gurobi Optimizer Reference Manual.Retrieved fromhttps://www.gurobi.com Göß, A., Burlacu, R., & Martin, A. (2025).Parabolic approximation & relaxa...
Pith/arXiv arXiv 2016
-
[19]
Hastie, T. J. (2017). Generalized additive models.Statistical models in S, 249–307
2017
-
[20]
I., den Hertog, D., & Fajemisin, A
Maragno, D., Wiberg, H., Bertsimas, D., Birbil, c. I., den Hertog, D., & Fajemisin, A. O. (2025). Mixed-integer optimization with constraint learning.Operations Research,73(2), 1011-1028. MOSEK ApS. (2025). The mosek python fusion api manual. version 11.0. [Computer software manual]. Retrieved fromhttps://docs.mosek.com/latest/ pythonfusion/index.html Nav...
2025
-
[21]
(2015, 10 1)
Rebennack, S., & Kallrath, J. (2015, 10 1). Continuous piecewise linear delta- approximations for bivariate and multivariate functions.Journal of Optimization Theory and Applications,167(1), 102–117
2015
-
[22]
S., & Sahinidis, N
Ryoo, H. S., & Sahinidis, N. V. (1996). A branch-and-reduce approach to global optimization.Journal of Global Optimization,8(2), 107–138
1996
-
[23]
Sahinidis, N. V. (1996). BARON: A general purpose global optimization software package.Journal of Global Optimization,8(2), 201–205
1996
-
[24]
Schimek, M. G. (2013).Smoothing and regression: approaches, computation, and 30 application. New York: John Wiley & Sons
2013
-
[25]
M., & Pantelides, C
Smith, E. M., & Pantelides, C. C. (1997). Global optimisation of nonconvex MINLPs. Computers & Chemical Engineering,21, S791-S796
1997
-
[26]
SpencerTrindade, R., D’Ambrosio, C., Frangioni, A.,&Gentile, C. (2023). Comparing perspective reformulations for piecewise-convex optimization.Operations Research Letters,51(6), 702–708
2023
-
[27]
(2017, 2)
Taktak, R., & D’Ambrosio, C. (2017, 2). An overview on mathematical programming approaches for the deterministic unit commitment problem in hydro valleys.Energy Systems,8(1), 57–79
2017
-
[28]
Tawarmalani, M., & Sahinidis, N. V. (2002).Convexification and global optimization in continuous and. USA: Kluwer Academic Publishers
2002
-
[29]
Tawarmalani, M., & Sahinidis, N. V. (2004, apr). Global optimization of mixed- integer nonlinear programs: A theoretical and computational study.Mathematical Programming,99(3), 563–591. ten Eikelder, S. C. M., & van Amerongen, J. H. M. (2023). Resource allocation problems with expensive function evaluations.European Journal of Operational Research,306(3),...
2004
-
[30]
P., Ahmed, S., & Nemhauser, G
Vielma, J. P., Ahmed, S., & Nemhauser, G. (2009). Mixed-integer models for nonseparable piecewise-linear optimization: Unifying framework and extensions. Operations Research,58(2), 303–315
2009
-
[31]
Vigerske, S., & Gleixner, A. (2018). SCIP: Global optimization of mixed-integer nonlinear programs in a branch-and-cut framework.Optimization Methods and Software,33(3), 563–593. Wächter, A., & Biegler, L. T. (2006). On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming.Mathematical Programming,106, 25–57
2018
-
[32]
P., & Ormerod, J
Wand, M. P., & Ormerod, J. T. (2008). On semiparametric regression with o’sullivan penalized splines.Australian & New Zealand Journal of Statistics,50(2), 179–198
2008
-
[33]
A., & Rebennack, S
Warwicker, J. A., & Rebennack, S. (2024). Efficient continuous piecewise linear regression for linearising univariate non-linear functions.IISE Transactions,57(3), 231–245
2024
-
[34]
Wood, S. N. (2020). Inference and computation with generalized additive models and their extensions.Test,29(2), 307–339. 31
2020
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.