Pith. sign in

REVIEW 2 major objections 5 minor 69 references

Coordinate Optimality Reformulation for Mixed-Integer Convex Programs with Indicators

T0 review · 2 major / 5 minor · reviewed 2026-08-06 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read Per-coordinate optimality rules shrink branch trees

desk verdict CORe is a promising idea with strong computational results, but the preservation claim fails for finite big-M because coordinate minimizers can lie outside the bounds; needs a fix or an explicit large-M condition. read the letter →

arxiv 2608.01385 v1 pith:Q4L2CPVW submitted 2026-08-02 math.OC stat.ML

Tong Xu , Salar Fattahi , Andrés Gómez , Simge Küçükyavuz This is my paper
classification math.OCstat.ML MSC 90C1190C20
keywords mixed-integerconvexoptimizationindicatorconstraintscoordinate-wiseoptimalitydisjunctivereformulationbranch-and-boundquadraticprogramswithindicatorsrobustsingle-indexmodelssparsity
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper introduces a reformulation principle for mixed-integer convex programs in which binary indicators switch continuous variables on or off. The idea is to fix all variables except one coordinate, solve the resulting one-dimensional subproblem exactly, compare the cost of leaving that coordinate off with the cost of turning it on, and then add constraints that encode which regime can actually occur at an optimum. Because every global optimum passes this coordinate-wise test, the added constraints never remove optimal solutions, only activation patterns that cannot occur at any optimum. The paper shows that for convex quadratic programs whose interaction graph is a star, or an unbalanced bipartite graph with fixed dimension, and for robust single-index models with fixed covariate dimension, branch-and-bound trees become polynomial in the number of variables rather than exponential.

What carries the argument

The coordinate subproblem and its exact closed-form solution. For each coordinate $i$, after fixing the other variables, define $g_i = c_i + \sum_{j \ne i} Q_{ij} x_j$. With $Q_{ii} > 0$, the on-regime minimizer is $x_i^* = -g_i/Q_{ii}$ and the off/on comparison reduces to $|g_i| \le \tau_i = \sqrt{2\lambda_i Q_{ii}}$. CORe writes the resulting three-term disjunction (off, on with $g_i \ge \tau_i$, on with $g_i \le -\tau_i$) as linear constraints via disaggregated variables, i.e., the extended convex hull of the local disjunction. The same regime logic---an interval $S_i(\lambda_i)$ of indices consistent with fitting observation $i$---drives the robust single-index extension.

What would settle it

Construct the path-graph instance in Proposition 3 with $Q_{ii}=1$, $Q_{i,i+1}=Q_{i+1,i}=1/2$, $c_i=-1$, $\lambda_i=\tau^2/2$ for $\tau\in(0.5,1)$, and count feasible integer leaves of the CORe formulation under regime branching. The proof predicts the count grows at least as fast as the number of maximal independent sets of the path, roughly $1.3247^n$; observing polynomial growth for fixed $\tau$ would refute the exponential lower bound. Alternatively, check whether a star-graph instance with $n=10^4$ ever requires more than a linear number of nodes.

Watch

Extended reading notes

Core claim

The central claim is the Coordinate Optimality Principle (Proposition 1): at any global optimum, each coordinate's on/off choice must be locally optimal against the one-dimensional subproblem obtained by fixing all other variables. CORe encodes the resulting regimes as disjunctive constraints. In the quadratic case with positive diagonal entries, the on-regime minimizer is $x_i^* = -g_i/Q_{ii}$ and the off/on comparison reduces to $|g_i| \le \tau_i = \sqrt{2\lambda_i Q_{ii}}$, so the three regimes (off, on with $g_i \ge \tau_i$, on with $g_i \le -\tau_i$) become linear constraints through disaggregated variables. This preserves all global optima while removing suboptimal activation patterns.

Load-bearing premise

The approach needs each coordinate's one-variable subproblem to have a strictly convex closed-form minimizer---in the quadratic case $Q_{ii} > 0$ for every $i$---so that the threshold $\tau_i$ and the disjunction are well defined; without strict convexity in that coordinate, the reformulation is undefined.

Editorial extensions

If this is right

  • For star-graph quadratic indicator programs, a branch-and-bound that fully resolves CORe disjunctions terminates after $O(n)$ nodes; experiments solve $n = 10^4$ instances at the root, faster than a specialized parametric tree algorithm.
  • For unbalanced bipartite quadratic programs with $m$ continuous coupling variables, the CORe branch-and-bound tree has $O(n^{m+1})$ nodes for fixed $m$, and Appendix B gives an explicit geometric-pruning algorithm with $O(n^{m+1})$ time and memory.
  • For robust single-index models with $d$ covariates---including penalized least trimmed squares and robust logistic regression---only $O(n^d)$ trimming patterns are consistent with coordinate optimality; with convex loss composed with the link, the problem is solvable by solving $O(n^d)$ convex subproblems, hence polynomial time when $d$ is fixed.
  • Path graphs can defeat CORe: Proposition 3 constructs instances with exponentially many feasible CORe leaves, so sparsity alone does not guarantee polynomial behavior.
  • Every CORe reformulation preserves all global optima of the original problem; it only prunes activation patterns that violate coordinate-wise optimality, so the reformulation can be layered on top of any solver.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Extension not tested in the paper: CORe's disjunctive constraints could be combined with perspective or conic strengthening, since the two attack different weaknesses---regime selection versus continuous relaxation.
  • Extension not in the paper: for nonlinear-link robust models, the closed-form strengthening is unavailable as the paper notes in Remark 3; relaxing the nonlinear stationarity equality with piecewise-linear or conic approximations might recover some of the quadratic-model gains.
  • Testable prediction implied by the threshold logic: instance difficulty under CORe should track the fraction of coordinates whose $|g_i|$ at the optimum lies close to $\tau_i$; the adversarial path instances support this boundary-margin mechanism over raw sparsity.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 5 minor

Summary. The paper introduces the Coordinate Optimality Reformulation (CORe) framework for mixed-integer convex programs with indicator constraints. For a canonical complementarity formulation (1), the authors derive coordinate-wise optimality conditions (Proposition 1) and use them to build optimality-condition, closed-form, and disjunctive reformulations. For convex quadratic programs with indicators and Q_ii > 0, this yields a three-regime disjunctive formulation (11) with explicit thresholds tau_i = sqrt(2 lambda_i Q_ii). The framework is extended to unbalanced bipartite quadratic programs (Section 3.3) and to robust single-index models including penalized least trimmed squares and robust logistic regression (Section 4), with polynomial branch-and-bound tree bounds for fixed low-dimensional control variables. Computational experiments on synthetic and real datasets report large improvements over standard big-M formulations and, on tree-structured instances, over a specialized parametric algorithm.

Significance. If the preservation claim is correct, CORe is a valuable and broadly applicable reformulation principle: it turns local coordinate-wise optimality into explicit mixed-integer constraints and exposes structure that big-M formulations hide. The derivations are self-contained, the threshold rules are parameter-free, and the polynomial bounds for star, unbalanced bipartite, and fixed-dimension robust single-index models are interesting. The paper also provides code and data. However, a load-bearing correctness gap exists for the finite big-M formulation: the proof of preservation is given for the unconstrained canonical form, not for the bounded formulation used in the QP specialization and in the experiments. This issue must be resolved before the main claims can be accepted.

major comments (2)
  1. [Section 3.1, Eq. (11)] Proposition 1 is stated and proved for the unconstrained complementarity form (1). In the QP specialization, the coordinate subproblem is solved over xi in R after Eq. (6), ignoring the bounds -M_i z_i <= x_i <= M_i z_i of (2). The CF disjunction then enforces x_i = -g_i/Q_ii whenever z_i = 1. If a global optimum of (2) has z_i = 1 and x_i at a bound because the unconstrained minimizer lies outside [-M_i, M_i], that point satisfies (2) but violates the CORe formulation, so (11) can exclude global optima or become infeasible. The paper never states a sufficient largeness condition for M_i that rules this out, nor does it prove preservation for the finite-M formulation. The proof needs either a hypothesis that at every optimal solution with z_i = 1 the unconstrained coordinate minimizer is feasible, or a re-derivation of the disjunction using the box-constrained coordinate subproblem.
  2. [Section 5.1, M-tightening] The M-tightening heuristic M <- min{M, 2 max_i |x_relax_i|} can produce exactly the binding case described above. Concrete counterexample: n = 1, Q = [1], c = -10, lambda = 1, M = 1. The bounded problem (2) has optimal solution x = 1, z = 1 with objective -8.5. In formulation (11), z = 0 forces g_1 = -10 into the interval [-sqrt(2), sqrt(2)], which is impossible. If z = 1, the plus branch requires g^+ >= sqrt(2) and x^+ = -g^+ <= -sqrt(2), violating x^+ >= -1; the minus branch similarly requires x^- >= sqrt(2), violating x^- <= 1. Thus (11) is infeasible. This shows the abstract and Section 2 preservation claims are false for the formulation as stated, and the issue is not merely formal because the paper's own preprocessing can create binding M_i.
minor comments (5)
  1. [Section 5.2] The experiments compare CORe against a standard big-M formulation only. For convex quadratic indicator problems, perspective reformulations are the standard strengthening and are discussed in Section 1.2; adding this baseline would significantly strengthen the empirical claims and help locate CORe relative to existing relaxations.
  2. [Section 5.1, Tables 1-9] All results are averages over five trials without variance or error bars. Since node counts and solution times can be highly variable, reporting standard deviations or per-instance values would improve reproducibility and the interpretation of the timing comparisons.
  3. [Propositions 2 and 4] The polynomial tree bounds are proved for a tailored regime-branching scheme, while the experiments use Gurobi's default branching. The paper states this caveat for stars but should state it equally clearly for Proposition 4 and Proposition 5; the empirical node counts are not direct evidence for the theoretical bounds.
  4. [Section 4.3(ii)] The proof of Proposition 5(ii) refers to Appendix B for polynomial enumeration of cells, but Appendix B is written specifically for the quadratic unbalanced bipartite model. A self-contained enumeration argument for the general hyperplane arrangement in fixed dimension d would make this part easier to verify.
  5. [Table 7] Root gaps above 100% (e.g., 465.1% and 627.1%) are unusual; the definition of root gap should be restated so the reader understands how a lower bound of opposite sign is handled.

Circularity Check

0 steps flagged · score 1.0 of 10

No significant circularity: CORe's constraints are derived necessary conditions, thresholds are computed from model data, and polynomial bounds use classical hyperplane counting. Self-citations appear only as benchmarks/related work and are not load-bearing.

full rationale

The paper's derivation chain is self-contained rather than circular. Proposition 1 establishes a necessary condition for global optimality: at any global optimum, each coordinate must be in one of two regimes (off/on), with the on-regime requiring the coordinate to minimize the one-dimensional subproblem and the off/on comparison satisfied. The OC, CF, and disjunctive components (formulations (4), (5), (11), (14), (20), (23)) are simply encodings of this necessary condition, so they preserve global optima by construction but do not presuppose the conclusion. The quadratic thresholds τ_i = sqrt(2λ_i Q_ii) are derived algebraically from the model parameters (Q, c, λ), not fitted to solution data, and the star/bipartite/single-index tree bounds (Propositions 2, 4, 5) follow by counting cells of hyperplane arrangements of these derived thresholds using the classical bound of Zaslavsky [67]. The paper cites prior work by overlapping authors ([7], [54]) but only as related work, experimental benchmarks, or context; the preservation and polynomiality proofs do not rest on those citations. The most notable issue is a correctness gap, not circularity: the CF equality x_i = -g_i/Q_ii is derived from the unconstrained coordinate subproblem, and when applied to the bounded big-M formulation (2), a global optimum with x_i at a bound can be excluded, as the skeptic's example shows. This is an invalid application of Proposition 1 to the bounded problem, not a tautology or fitted-input prediction. Overall, the central claims have independent mathematical content, and no step reduces to its own inputs by definition.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

The paper introduces no fitted free parameters or new entities. The thresholds, closed-form minimizers, and cell counts all follow from the stated model data and standard mathematics. The main axiomatic inputs are the strict convexity per coordinate, the monotone-link/convex-loss conditions in the robust single-index section, and the usual big-M sufficiency assumption.

assumptions (4)
  • domain assumption In the quadratic specialization, every diagonal entry Q_ii is strictly positive (Section 3.1).
    Needed for the closed-form coordinate minimizer x_i^* = -g_i/Q_ii and the threshold tau_i = sqrt(2 lambda_i Q_ii).
  • domain assumption Assumption 1: each loss ell_i is convex, nonnegative, and satisfies ell_i(r_i)=0; the link f is monotone (Section 4).
    Ensures the sublevel set S_i(lambda_i) is an interval, so the CORe regime disjunctions can be encoded with linear constraints.
  • domain assumption The big-M constants M_i are chosen large enough that the big-M formulation is equivalent to the original indicator constraints.
    Standard assumption in indicator MIPs; CORe inherits it and also needs M_i to cover the coordinate minimizers in the on-regime.
  • standard math Zaslavsky's hyperplane arrangement bound (cited as [67]) is used to count cells (Propositions 4 and 5).
    Provides the O(n^d) cell count for arrangements of 2n hyperplanes in dimension d.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Coordinate Optimality Reformulation for Mixed-Integer Convex Programs with Indicators." pith.science (2026). https://pith.science/paper/Q4L2CPVW

@misc{pith2026260801385,
  author       = {Pith},
  title        = {Pith review of: Coordinate Optimality Reformulation for Mixed-Integer Convex Programs with Indicators},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/Q4L2CPVW}},
  note         = {Machine review of arXiv:2608.01385}
}
abstract

We consider mixed-integer convex optimization problems in which binary indicators control continuous variables. We introduce the \emph{Coordinate Optimality Reformulation} (CORe) framework, which augments standard indicator formulations by incorporating coordinate-wise optimality information. The resulting reformulations preserve global optimality while substantially improving branch-and-bound performance, particularly in sparse and structured settings where the coordinate-wise optimality conditions expose exploitable problem structure. We first develop the main components of CORe, including coordinate-wise optimality conditions, closed-form characterizations, and disjunctive reformulations. We then demonstrate the framework across multiple problem families, including quadratic problems and robust single-index models. Computational experiments show that CORe can substantially improve solver performance compared with standard big-$M$ formulations.

Figures

Figures reproduced from arXiv: 2608.01385 by the authors.

Figure 1
Figure 1. Log-log plot of solution time versus problem size for the CORe formulation and parametric [PITH_FULL_IMAGE:figures/full_fig_p026_1.png] view at source ↗
Figure 2
Figure 2. Log-log plot of solution time versus problem size for the CORe formulation and parametric [PITH_FULL_IMAGE:figures/full_fig_p027_2.png] view at source ↗
Figure 3
Figure 3. Signal recovery on the real-world accelerometer dataset. [PITH_FULL_IMAGE:figures/full_fig_p029_3.png] view at source ↗

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

69 extracted references · 65 canonical work pages

  1. [1]

    A strong conic quadratic reformulation for machine- job assignment with controllable processing times.Operations Research Letters, 37(3):187–191, 2009

    M Selim Aktürk, Alper Atamtürk, and Sinan Gürel. A strong conic quadratic reformulation for machine- job assignment with controllable processing times.Operations Research Letters, 37(3):187–191, 2009

    work page 2009

  2. [2]

    Strong formulations for quadratic optimization with m-matrices and indicator variables.Mathematical Programming, 170(1):141–176, 2018

    Alper Atamtürk and Andrés Gómez. Strong formulations for quadratic optimization with m-matrices and indicator variables.Mathematical Programming, 170(1):141–176, 2018

    work page 2018

  3. [3]

    Rank-one convexification for sparse regression.Journal of Machine Learning Research, 26(35):1–50, 2025

    Alper Atamtürk and Andres Gómez. Rank-one convexification for sparse regression.Journal of Machine Learning Research, 26(35):1–50, 2025

    work page 2025

  4. [4]

    Disjunctive programming: Properties of the convex hull of feasible points.Discrete Applied Mathematics, 89(1-3):3–44, 1998

    Egon Balas. Disjunctive programming: Properties of the convex hull of feasible points.Discrete Applied Mathematics, 89(1-3):3–44, 1998

    1998

  5. [5]

    Bestsubsetselectionviaamodernoptimization lens.Annals of Statistics, pages 813–852, 2016

    DimitrisBertsimas, AngelaKing, andRahulMazumder. Bestsubsetselectionviaamodernoptimization lens.Annals of Statistics, pages 813–852, 2016

    work page 2016

  6. [6]

    Sparse high-dimensional regression.The Annals of Statistics, 48(1):300–323, 2020

    Dimitris Bertsimas and Bart Van Parys. Sparse high-dimensional regression.The Annals of Statistics, 48(1):300–323, 2020

    work page 2020

  7. [7]

    A parametric approach for solving convex quadratic optimization with indicators over trees.Mathematical Programming, pages 1–46, 2025

    Aaresh Bhathena, Salar Fattahi, Andrés Gómez, and Simge Küçükyavuz. A parametric approach for solving convex quadratic optimization with indicators over trees.Mathematical Programming, pages 1–46, 2025. Article in Advance

    work page 2025

  8. [8]

    Solving convex quadratic optimization with indicators over structured graphs.arXiv preprint arXiv:2603.02103, 2026

    Aaresh Bhathena, Salar Fattahi, Andrés Gómez, and Simge Küçükyavuz. Solving convex quadratic optimization with indicators over structured graphs.arXiv preprint arXiv:2603.02103, 2026. 30

    work page arXiv 2026

Show all 69 references
  1. [9]

    Computational study of a family of mixed-integer quadratic programming problems

    Daniel Bienstock. Computational study of a family of mixed-integer quadratic programming problems. Mathematical Programming, 74(2):121–140, 1996

    1996

  2. [10]

    Solving convex QPs with structured sparsity under indicator conditions.arXiv preprint arXiv:2411.11722, 2024

    Daniel Bienstock and Tongtong Chen. Solving convex QPs with structured sparsity under indicator conditions.arXiv preprint arXiv:2411.11722, 2024

    2024 arXiv

  3. [11]

    LP formulations for polynomial optimization problems.SIAM Journal on Optimization, 28(2):1121–1150, 2018

    Daniel Bienstock and Gonzalo Muñoz. LP formulations for polynomial optimization problems.SIAM Journal on Optimization, 28(2):1121–1150, 2018

    2018

  4. [12]

    An algorithmic framework for convex mixed integer nonlinear programs.Discrete optimization, 5(2):186–204, 2008

    Pierre Bonami, Lorenz T Biegler, Andrew R Conn, Gérard Cornuéjols, Ignacio E Grossmann, Carl D Laird, Jon Lee, Andrea Lodi, François Margot, Nicolas Sawaya, et al. An algorithmic framework for convex mixed integer nonlinear programs.Discrete optimization, 5(2):186–204, 2008

    2008

  5. [13]

    Algorithms and software for convex mixed integer nonlinear programs

    Pierre Bonami, Mustafa Kılınç, and Jeff Linderoth. Algorithms and software for convex mixed integer nonlinear programs. InMixed integer nonlinear programming, pages 1–39. Springer, 2011

    2011

  6. [14]

    Human activity recognition from accelerometer data using a wearable device

    Pierluigi Casale, Oriol Pujol, and Petia Radeva. Human activity recognition from accelerometer data using a wearable device. InIberian conference on pattern recognition and image analysis, pages 289–296. Springer, 2011

    2011

  7. [15]

    Personalization and user verification in wearable systems using biometric walking patterns.Personal and Ubiquitous Computing, 16(5):563–580, 2012

    Pierluigi Casale, Oriol Pujol, and Petia Radeva. Personalization and user verification in wearable systems using biometric walking patterns.Personal and Ubiquitous Computing, 16(5):563–580, 2012

    2012

  8. [16]

    Convex programming for disjunctive convex optimization.Mathemat- ical Programming, 86(3):595–614, 1999

    Sebastián Ceria and João Soares. Convex programming for disjunctive convex optimization.Mathemat- ical Programming, 86(3):595–614, 1999

    1999

  9. [17]

    Complexity of unconstrained minimization

    Xiaojun Chen, Dongdong Ge, Zizhuo Wang, and Yinyu Ye. Complexity of unconstrained minimization. Mathematical Programming, 143(1):371–383, 2014

    2014

  10. [18]

    Outer approximation with conic certificates for mixed-integer convex problems.Mathematical Programming Computation, 12:249–293, 2020

    Chris Coey, Miles Lubin, and Juan Pablo Vielma. Outer approximation with conic certificates for mixed-integer convex problems.Mathematical Programming Computation, 12:249–293, 2020

    2020

  11. [19]

    Learning sparse classifiers: Continuous and mixed integer optimization perspectives.Journal of Machine Learning Research, 22(135):1–47, 2021

    Antoine Dedieu, Hussein Hazimeh, and Rahul Mazumder. Learning sparse classifiers: Continuous and mixed integer optimization perspectives.Journal of Machine Learning Research, 22(135):1–47, 2021

    2021

  12. [20]

    Subset selection in sparse matrices.SIAM Journal on Optimization, 30(2):1173–1190, 2020

    Alberto Del Pia, Santanu S Dey, and Robert Weismantel. Subset selection in sparse matrices.SIAM Journal on Optimization, 30(2):1173–1190, 2020

    2020

  13. [21]

    Regularization vs

    Hongbo Dong, Kun Chen, and Jeff Linderoth. Regularization vs. relaxation: A conic optimization perspective of statistical variable selection.arXiv preprint arXiv:1510.06083, 2015

    2015 arXiv

  14. [22]

    An outer-approximation algorithm for a class of mixed- integer nonlinear programs.Mathematical programming, 36(3):307–339, 1986

    Marco A Duran and Ignacio E Grossmann. An outer-approximation algorithm for a class of mixed- integer nonlinear programs.Mathematical programming, 36(3):307–339, 1986

    1986

  15. [23]

    Scalable inference of sparsely-changing Gaussian Markov random fields.Advances in Neural Information Processing Systems, 34:6529–6541, 2021

    Salar Fattahi and Andres Gómez. Scalable inference of sparsely-changing Gaussian Markov random fields.Advances in Neural Information Processing Systems, 34:6529–6541, 2021

    2021

  16. [24]

    Solution path of time-varying Markov random fields with discrete regularization.arXiv preprint arXiv:2307.13750, 2023

    Salar Fattahi and Andrés Gómez. Solution path of time-varying Markov random fields with discrete regularization.arXiv preprint arXiv:2307.13750, 2023

    2023 arXiv

  17. [25]

    Approximated perspective relaxations: a project and lift approach.Computational Optimization and Applications, 63(3):705–735, 2016

    Antonio Frangioni, Fabio Furini, and Claudio Gentile. Approximated perspective relaxations: a project and lift approach.Computational Optimization and Applications, 63(3):705–735, 2016

    2016

  18. [26]

    Improving the approximated projected perspec- tive reformulation by dual information.Operations Research Letters, 45(5):519–524, 2017

    Antonio Frangioni, Fabio Furini, and Claudio Gentile. Improving the approximated projected perspec- tive reformulation by dual information.Operations Research Letters, 45(5):519–524, 2017

    2017

  19. [27]

    Perspective cuts for a class of convex 0–1 mixed integer pro- grams.Mathematical Programming, 106(2):225–236, 2006

    Antonio Frangioni and Claudio Gentile. Perspective cuts for a class of convex 0–1 mixed integer pro- grams.Mathematical Programming, 106(2):225–236, 2006

    2006

  20. [28]

    SDP diagonalizations and perspective cuts for a class of non- separable MIQP.Operations Research Letters, 35(2):181–185, 2007

    Antonio Frangioni and Claudio Gentile. SDP diagonalizations and perspective cuts for a class of non- separable MIQP.Operations Research Letters, 35(2):181–185, 2007. 31

    2007

  21. [29]

    Projected perspective refor- mulations with applications in design problems.Operations research, 59(5):1225–1232, 2011

    Antonio Frangioni, Claudio Gentile, Enrico Grande, and Andrea Pacifici. Projected perspective refor- mulations with applications in design problems.Operations research, 59(5):1225–1232, 2011

    2011

  22. [30]

    Decompositions of semidefinite matrices and the perspective reformulation of nonseparable quadratic programs.Mathematics of Operations Research, 45(1):15–33, 2020

    Antonio Frangioni, Claudio Gentile, and James Hungerford. Decompositions of semidefinite matrices and the perspective reformulation of nonseparable quadratic programs.Mathematics of Operations Research, 45(1):15–33, 2020

    2020

  23. [31]

    The number of maximal independent sets in connected graphs.Journal of Graph Theory, 11(4):463–470, 1987

    Zoltán Füredi. The number of maximal independent sets in connected graphs.Journal of Graph Theory, 11(4):463–470, 1987

    1987

  24. [32]

    Improved linear integer programming formulations of nonlinear integer problems.Man- agement Science, 22(4):455–460, 1975

    Fred Glover. Improved linear integer programming formulations of nonlinear integer problems.Man- agement Science, 22(4):455–460, 1975

    1975

  25. [33]

    Outlier detection in time series via mixed-integer conic quadratic optimization.SIAM Journal on Optimization, 31(3):1897–1925, 2021

    Andres Gomez. Outlier detection in time series via mixed-integer conic quadratic optimization.SIAM Journal on Optimization, 31(3):1897–1925, 2021

    1925

  26. [34]

    Real-time solution of quadratic optimization problems with banded matrices and indicator variables.arXiv preprint arXiv:2405.03051, 2024

    Andres Gómez, Shaoning Han, and Leonardo Lozano. Real-time solution of quadratic optimization problems with banded matrices and indicator variables.arXiv preprint arXiv:2405.03051, 2024

    2024 arXiv

  27. [35]

    Outlier detection in regression: conic quadratic formulations.INFORMS Journal on Computing, 2025

    Andrés Gómez and José Neto. Outlier detection in regression: conic quadratic formulations.INFORMS Journal on Computing, 2025

    2025

  28. [36]

    Generalized convex disjunctive programming: Nonlinear convex hull relaxation.Computational optimization and applications, 26(1):83–100, 2003

    Ignacio E Grossmann and Sangbum Lee. Generalized convex disjunctive programming: Nonlinear convex hull relaxation.Computational optimization and applications, 26(1):83–100, 2003

    2003

  29. [37]

    Perspective reformulations of mixed integer nonlinear programs with indicator variables.Mathematical Programming, 124(1):183–205, 2010

    Oktay Günlük and Jeff Linderoth. Perspective reformulations of mixed integer nonlinear programs with indicator variables.Mathematical Programming, 124(1):183–205, 2010

    2010

  30. [38]

    2×2-convexifications for convex quadratic opti- mization with indicator variables.Mathematical Programming, 202(1):95–134, 2023

    Shaoning Han, Andrés Gómez, and Alper Atamtürk. 2×2-convexifications for convex quadratic opti- mization with indicator variables.Mathematical Programming, 202(1):95–134, 2023

    2023

  31. [39]

    Fast best subset selection: Coordinate descent and local combinatorial optimization algorithms.Operations Research, 68(5):1517–1537, 2020

    Hussein Hazimeh and Rahul Mazumder. Fast best subset selection: Coordinate descent and local combinatorial optimization algorithms.Operations Research, 68(5):1517–1537, 2020

    2020

  32. [40]

    Sparse regression at scale: Branch-and-bound rooted in first-order optimization.Mathematical Programming, 196(1):347–388, 2022

    Hussein Hazimeh, Rahul Mazumder, and Ali Saab. Sparse regression at scale: Branch-and-bound rooted in first-order optimization.Mathematical Programming, 196(1):347–388, 2022

    2022

  33. [41]

    Comparing solution paths of sparse quadratic minimization with a Stieltjes matrix.Mathematical Programming, 204(1):517–566, 2024

    Ziyu He, Shaoning Han, Andrés Gómez, Ying Cui, and Jong-Shi Pang. Comparing solution paths of sparse quadratic minimization with a Stieltjes matrix.Mathematical Programming, 204(1):517–566, 2024

    2024

  34. [42]

    A combinatorial approach for small and strong formulations of disjunctive constraints.Mathematics of Operations Research, 44(3):793–820, 2019

    Joey Huchette and Juan Pablo Vielma. A combinatorial approach for small and strong formulations of disjunctive constraints.Mathematics of Operations Research, 44(3):793–820, 2019

    2019

  35. [43]

    A geometric way to build strong mixed-integer programming formulations.Operations Research Letters, 47(6):601–606, 2019

    Joey Huchette and Juan Pablo Vielma. A geometric way to build strong mixed-integer programming formulations.Operations Research Letters, 47(6):601–606, 2019

    2019

  36. [44]

    Mustafa R Kılınç, Jeff Linderoth, and James Luedtke. Lift-and-project cuts for convex mixed integer nonlinear programs: Linear programming based separation and extended formulations.Mathematical Programming Computation, 9(4):499–526, 2017

    2017

  37. [45]

    On minimal valid inequalities for mixed integer conic programs.Mathematics of Operations Research, 41(2):477–510, 2016

    Fatma Kılınç-Karzan. On minimal valid inequalities for mixed integer conic programs.Mathematics of Operations Research, 41(2):477–510, 2016

    2016

  38. [46]

    Two-term disjunctions on the second-order cone.Mathematical Programming, 154(1):463–491, 2015

    Fatma Kılınç-Karzan and Sercan Yıldız. Two-term disjunctions on the second-order cone.Mathematical Programming, 154(1):463–491, 2015

    2015

  39. [47]

    Consistent second-order conic integer programming for learning Bayesian networks.Journal of Machine Learning Research, 24(322):1–38, 2023

    Simge Küçükyavuz, Ali Shojaie, Hasan Manzour, Linchuan Wei, and Hao-Hsiang Wu. Consistent second-order conic integer programming for learning Bayesian networks.Journal of Machine Learning Research, 24(322):1–38, 2023. 32

    2023

  40. [48]

    Polyhedral analysis of quadratic optimization problems with Stieltjes matrices and indicators.Mathematical Programming, pages 1–27,

    Peijing Liu, Alper Atamtürk, Andrés Gómez, and Simge Küçükyavuz. Polyhedral analysis of quadratic optimization problems with Stieltjes matrices and indicators.Mathematical Programming, pages 1–27,

  41. [49]

    A graph-based decomposition method for convex quadratic optimization with indicators.Mathematical Programming, 200(2):669– 701, 2023

    Peijing Liu, Salar Fattahi, Andrés Gómez, and Simge Küçükyavuz. A graph-based decomposition method for convex quadratic optimization with indicators.Mathematical Programming, 200(2):669– 701, 2023

    2023

  42. [50]

    Polyhedral approximation in mixed-integer convex optimization.Mathematical Programming, 172(1):139–168, 2018

    Miles Lubin, Emre Yamangil, Russell Bent, and Juan Pablo Vielma. Polyhedral approximation in mixed-integer convex optimization.Mathematical Programming, 172(1):139–168, 2018

    2018

  43. [51]

    Finding low-rank solutions of sparse linear matrix inequalities using convex optimization.SIAM Journal on Optimization, 27(2):725– 758, 2017

    Ramtin Madani, Somayeh Sojoudi, Ghazal Fazelnia, and Javad Lavaei. Finding low-rank solutions of sparse linear matrix inequalities using convex optimization.SIAM Journal on Optimization, 27(2):725– 758, 2017

    2017

  44. [52]

    Integer programming for learning directed acyclic graphs from continuous data.INFORMS Journal on Optimization, 3(1):46–73, 2021

    Hasan Manzour, Simge Küçükyavuz, Hao-Hsiang Wu, and Ali Shojaie. Integer programming for learning directed acyclic graphs from continuous data.INFORMS Journal on Optimization, 3(1):46–73, 2021

    2021

  45. [53]

    Subset selection with shrinkage: Sparse linear modeling when the snr is low.Operations Research, 71(1):129–147, 2023

    Rahul Mazumder, Peter Radchenko, and Antoine Dedieu. Subset selection with shrinkage: Sparse linear modeling when the snr is low.Operations Research, 71(1):129–147, 2023

    2023

  46. [54]

    Computation of least trimmed squares: A branch- and-bound framework with hyperplane arrangement enhancements.arXiv preprint arXiv:2604.11584, 2026

    Xiang Meng, Andrés Gómez, and Rahul Mazumder. Computation of least trimmed squares: A branch- and-bound framework with hyperplane arrangement enhancements.arXiv preprint arXiv:2604.11584, 2026

    2026 arXiv

  47. [55]

    A mixed- integer programming approachfor unit commitment inmicro-grid with incentive-based demand response and battery energy storage system.Energies, 15(19):7192, 2022

    Tuyen Nguyen-Duc, Linh Hoang-Tuan, Hung Ta-Xuan, Long Do-Van, and Hirotaka Takano. A mixed- integer programming approachfor unit commitment inmicro-grid with incentive-based demand response and battery energy storage system.Energies, 15(19):7192, 2022

    2022

  48. [56]

    Bayesian network learning via topological order.Journal of Machine Learning Research, 18(99):1–32, 2017

    Young Woong Park and Diego Klabjan. Bayesian network learning via topological order.Journal of Machine Learning Research, 18(99):1–32, 2017

    2017

  49. [57]

    An LP/NLP based branch and bound algorithm for convex minlp optimization problems.Computers & chemical engineering, 16(10-11):937–947, 1992

    Ignacio Quesada and Ignacio E Grossmann. An LP/NLP based branch and bound algorithm for convex minlp optimization problems.Computers & chemical engineering, 16(10-11):937–947, 1992

    1992

  50. [58]

    Efficient inference of dynamic gene regulatory networks using discrete penalty.arXiv preprint arXiv:2507.23106, 2025

    Visweswaran Ravikumar, Aaresh Bhathena, Wajd N Al-Holou, Salar Fattahi, and Arvind Rao. Efficient inference of dynamic gene regulatory networks using discrete penalty.arXiv preprint arXiv:2507.23106, 2025

    2025 arXiv

  51. [59]

    Mixed integer linear programming formulation techniques.SIAM Review, 57(1):3– 57, 2015

    Juan Pablo Vielma. Mixed integer linear programming formulation techniques.SIAM Review, 57(1):3– 57, 2015

    2015

  52. [60]

    Sums of squares and semidefinite program relaxations for polynomial optimization problems with structured sparsity.SIAM Journal on Optimization, 17(1):218–242, 2006

    Hayato Waki, Sunyoung Kim, Masakazu Kojima, and Masakazu Muramatsu. Sums of squares and semidefinite program relaxations for polynomial optimization problems with structured sparsity.SIAM Journal on Optimization, 17(1):218–242, 2006

    2006

  53. [61]

    On the convexification of constrained quadratic optimization problems with indicator variables

    Linchuan Wei, Andrés Gómez, and Simge Küçükyavuz. On the convexification of constrained quadratic optimization problems with indicator variables. InInternational Conference on Integer Programming and Combinatorial Optimization, pages 433–447. Springer, 2020

    2020

  54. [62]

    Ideal formulations for constrained convex optimization problems with indicator variables.Mathematical Programming, 192(1):57–88, 2022

    Linchuan Wei, Andrés Gómez, and Simge Küçükyavuz. Ideal formulations for constrained convex optimization problems with indicator variables.Mathematical Programming, 192(1):57–88, 2022

    2022

  55. [63]

    The number of maximal independent sets in a tree.SIAM Journal on Algebraic Discrete Methods, 7(1):125–130, 1986

    Herbert S Wilf. The number of maximal independent sets in a tree.SIAM Journal on Algebraic Discrete Methods, 7(1):125–130, 1986

    1986

  56. [64]

    Scalable algorithms for the sparse ridge regression.SIAM Journal on Optimization, 30(4):3359–3386, 2020

    Weijun Xie and Xinwei Deng. Scalable algorithms for the sparse ridge regression.SIAM Journal on Optimization, 30(4):3359–3386, 2020. 33

    2020

  57. [65]

    An asymptotically optimal coordinate descent algorithm for learning Bayesian networks from Gaussian models.Journal of Machine Learning Research, 26(250):1–30, 2025

    Tong Xu, Simge Küçükyavuz, Ali Shojaie, and Armeen Taeb. An asymptotically optimal coordinate descent algorithm for learning Bayesian networks from Gaussian models.Journal of Machine Learning Research, 26(250):1–30, 2025

    2025

  58. [66]

    Integer programming for learning directed acyclic graphs from nonidentifiable Gaussian models.Biometrika, 112(3):asaf032, 04 2025

    Tong Xu, Armeen Taeb, Simge Küçükyavuz, and Ali Shojaie. Integer programming for learning directed acyclic graphs from nonidentifiable Gaussian models.Biometrika, 112(3):asaf032, 04 2025

    2025

  59. [67]

    Facing up to arrangements: Face-count formulas for partitions of space by hyper- planes.Memoirs of the American Mathematical Society, 1(154):1–102, 1975

    Thomas Zaslavsky. Facing up to arrangements: Face-count formulas for partitions of space by hyper- planes.Memoirs of the American Mathematical Society, 1(154):1–102, 1975

    1975

  60. [68]

    Xiaojin Zheng, Xiaoling Sun, and Duan Li. Improving the performance of MIQP solvers for quadratic programs with cardinality and minimum threshold constraints: A semidefinite program approach.IN- FORMS Journal on Computing, 26(4):690–703, 2014

    2014

  61. [69]

    Deleting outliers in robust regression with mixed integer programming.Acta Mathematicae Applicatae Sinica, 21(2):323–334, 2005

    Georgios Zioutas and Antonios Avramidis. Deleting outliers in robust regression with mixed integer programming.Acta Mathematicae Applicatae Sinica, 21(2):323–334, 2005. A Proof of Proposition 3 Proof. LetQ∈R n×n be the tridiagonal matrix Qii = 1 (i= 1, . . . , n), Q i,i+1 =Q i...

    2005

Pith tools

Reviewed August 6, 2026 · model on record in the stance chip above.