Pith. sign in

REVIEW 4 major objections 9 minor 39 references

BIPNN: Learning to Solve Binary Integer Programming via Hypergraph Neural Networks

T0 review · 4 major / 9 minor · reviewed 2026-08-07 · deepseek-v4-flash

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

Pith's one-line read BIPNN shows that large nonlinear 0-1 programs can be learned end-to-end by a hypergraph neural network, beating linearization-based solvers.

desk verdict The penalty construction for constraints is broken for non-monotone inequalities, so the paper's central generality claim isn't supported; the GPU loss trick is the salvageable part. read the letter →

arxiv 2505.20997 v1 pith:XTFRM6W3 submitted 2025-05-27 cs.LG cs.AI

Sen Bai , Chunqi Yang , Xin Bai , Xin Zhang , Zhengang Jiang This is my paper
classification cs.LGcs.AI MSC 90C1090C2768T07
keywords binaryintegerprogramminghypergraphneuralnetworkspolynomialunconstrainedoptimizationunsupervisedlearningcombinatorialGPUaccelerationpenaltymethodmax-cut
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

BIPNN is an unsupervised learning framework that solves binary integer programs (BIPs) directly in their nonlinear form, without converting nonlinearities into many auxiliary linear variables. The paper's central claim is that a large class of constrained, discrete, nonlinear 0-1 optimization problems can be reformulated as polynomial unconstrained binary optimization (PUBO) losses, which correspond one-to-one to hypergraphs, and then minimized by a hypergraph neural network via gradient descent. On synthetic instances and hypergraph max-cut benchmarks, the trained network produces approximate solutions that match or beat SCIP and Tabu search once the problem size grows past roughly a thousand variables, while its solve time grows roughly linearly instead of exponentially. If the claim holds, it offers a scalable GPU-friendly route to approximate nonlinear BIP solving where classical linearization explodes.

What carries the argument

The central object is the PUBO-to-hypergraph encoding: each monomial x_i x_j ... becomes a hyperedge, and the incidence matrix H together with the coefficient vector Q evaluates the loss as ColM(x⊙^(B)H + (1−H)) Q^T, an expression dominated by parallelizable element-wise operations. Around this sit two reformulation tools: an inclusion-exclusion polynomial fitting that exactly matches any nonlinear function (sin, log, exp) on {0,1}^m, and a penalty construction that encodes each violated constraint as a sum of monomials over its minimal violation subsets. The continuous relaxation annealing schedule (negative then positive penalty strength) is what pushes the relaxed output back to discrete values.

What would settle it

Run BIPNN on a nonlinear BIP instance whose only constraint couples 30 otherwise unrelated variables (for example, sum x_i ≤ 5), so minimal violation subsets are numerous and non-local; if the penalty enumeration does not finish in practical time, or if for every lambda the returned solution violates the constraint, the central scalability claim fails.

Watch

Extended reading notes

Core claim

The paper proposes a precise structural correspondence: any polynomial objective on 0-1 variables, written as a sum of monomial terms, can be encoded as a hypergraph whose hyperedges are the monomials, with the incidence matrix providing a compact GPU-friendly way to evaluate the loss. Using this mapping, BIPNN relaxes the discrete variables to [0,1], trains a hypergraph neural network without labels to minimize the PUBO loss plus constraint penalties, and anneals the relaxation to force binary outputs. The authors report that this end-to-end learned optimizer scales to thousands of variables, outperforming SCIP and Tabu on large synthetic BIPs with quartic and sextic terms and on real-world hypergraph max-cut problems.

Load-bearing premise

The penalty construction assumes that, for every constraint, the minimal variable subsets that violate it can be enumerated in acceptable time (cost exponential in the constraint's arity) and that one scalar penalty weight is enough to make all violations unprofitable without distorting the objective.

Editorial extensions

If this is right

  • For nonlinear BIPs with thousands of variables, solution quality can improve as problem size grows, whereas linearization-based solvers degrade both in time and solution quality under a fixed time budget.
  • GPU-accelerated evaluation of the PUBO loss makes training cost nearly flat in the number of variables up to the tested range, unlike CPU-based loss loops.
  • The same hypergraph loss machinery applies to any problem expressible as PUBO, including hypergraph max-cut, giving neural solvers a direct benchmark in combinatorial optimization.
  • Trained on an instance rather than a dataset, BIPNN offers an unsupervised alternative: no labeled optimal solutions are needed, only the problem's own objective and constraints.

Reading between the lines

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

  • If the one-to-one PUBO-hypergraph mapping is as general as claimed, it suggests a template for other discrete structures, such as higher-order constraints or cardinality constraints, to be folded into hypergraph losses as long as minimal violation subsets remain enumerable.
  • The method's reported advantage over Tabu on large instances could be tested further on standard benchmark suites; a natural extension is to compare against learned solvers that use supervision or search guidance.
  • The paper's locality assumption for penalty enumeration implies a testable boundary: instances with dense, high-arity constraints (large Delta) would expose whether the 2^Delta enumeration is the real bottleneck in practice.
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

4 major / 9 minor

Summary. The paper proposes BIPNN, an unsupervised hypergraph neural network solver for binary integer programs (BIPs). The method reformulates a constrained, nonlinear BIP into a polynomial unconstrained binary optimization (PUBO) objective via two steps: (i) exact polynomial interpolation of Boolean functions (Sec. 4.1) and (ii) a penalty method that converts inequality and equality constraints into polynomial penalty terms (Sec. 4.2). The PUBO objective is then encoded as a hypergraph and used as a differentiable loss to train a HyperGNN, with a GPU-accelerated matrix formulation (Eq. 4) and a continuous-annealing schedule. Experiments on synthetic and real-world max-cut benchmarks compare BIPNN against SCIP and Tabu search, reporting competitive or better solution quality on several datasets and faster scaling on large instances.

Significance. The paper contributes a clean hypergraph encoding of PUBO monomials and a correct, parallelizable GPU formulation of the PUBO loss (Eq. 4), which are useful building blocks for neural combinatorial optimization. The polynomial interpolation in Sec. 4.1 is standard and correctly applied. The empirical results on hypergraph max-cut show that an unsupervised HyperGNN can match or beat classical solvers on several real-world datasets within a 1-hour limit, which is a nontrivial positive result. However, the central claim of solving general constrained nonlinear BIPs is not supported as written: the polynomial penalty construction has a correctness gap, and the experiments do not exercise the constrained pipeline at all. The significance of the paper in its current form is therefore limited to the unconstrained PUBO/max-cut setting.

major comments (4)
  1. [Sec. 4.2, Eqs. (8)-(9)] The polynomial penalty construction is not equivalent to the original constraint for general nonlinear functions. The monomial \prod_{i\in S} x_i evaluates to 1 on every binary assignment that contains S as a subset, not only on the exact assignment used to define S. If a superset of a minimal violation is feasible, the penalty is positive on a feasible point. For example, for the constraint g(x)=x1-x2\le 0, the minimal violation subset is {x1}, giving P(x)=λx1; the feasible assignment (1,1) satisfies g=0 but is penalized with λ. Thus the transformed objective's minimizers need not coincide with the original BIP's minimizers. The paper neither restricts to constraints whose violation sets are upward-closed nor proves that supersets of minimal violations remain violations. This is a load-bearing gap because this construction is the bridge from constrained BIPs to the PUBO/hypergraph loss used for training. The ReLU-based penalty avoids this issue but is not polynomial and is not the construction used in the PUBO pipeline.
  2. [Sec. 6] The experimental validation does not test the constrained-reformulation pipeline. All main benchmarks (Fig. 4, Fig. 5, Table 1, Sec. 6.3) are unconstrained PUBO or hypergraph max-cut objectives. The synthetic benchmark description only states that "several constraints (penalty terms) were randomly incorporated" without specifying how the constraints were generated, whether the polynomial penalty was actually used, what penalty coefficients were chosen, or whether the reported solutions satisfied all constraints. To support the paper's central claim of solving constrained nonlinear BIPs, the experiments must include constrained instances and report feasibility rates and objective gaps relative to SCIP on the original constrained formulation.
  3. [Sec. 4.2, Eq. (8)] The enumeration of minimal violation subsets requires evaluating ψ on all 2^Δ assignments for a constraint of arity Δ. The paper claims locality makes this manageable in real problems but provides no instance statistics (e.g., the distribution of Δ) and no complexity bounds. Without such evidence, the method is demonstrated only for small-arity constraints, and the claim of scalability to general nonlinear BIPs is unsupported. The paper should either quantify the typical arity in its benchmarks and report enumeration times, or explicitly restrict the method to constraints with small Δ.
  4. [Secs. 3.2 and 4.2] The choice of penalty coefficients λ_k and μ_l and the annealing schedule (initial γ, ramp epochs, final value) are left unspecified. The paper says "sufficiently large" without a selection rule, and in classical penalty methods too-small λ admits infeasible points while too-large λ can degrade conditioning and optimization. The annealing schedule in Sec. 6.4 is described only by initial γ=-2.5 and reaching 0 after 500 epochs; the update rule and final value are missing. Providing these details is necessary for reproducibility and for assessing whether the reported results are robust to these hyperparameters.
minor comments (9)
  1. [Sec. 3.2, Eq. (4)] Define the notation "⊙(B)" (broadcasting Hadamard product) and the "ColM" operation explicitly; the GPU-accelerated algorithm is a key contribution but the current notation is nonstandard and only informally illustrated in Fig. 1.
  2. [Sec. 4.1, Eq. (6)] Clarify that the Möbius inversion formula c_S = Σ_{T⊆S} (−1)^{|S|−|T|} f(T) can be computed by evaluating f on all 2^m Boolean points once; the current phrasing "For each subset S, it needs to calculate 2^{|S|} values of f(T)" is confusing because a single evaluation on each of the 2^m points yields all coefficients.
  3. [Sec. 4.1] The paper states that nonlinear terms such as sin, log, exp may be "opt to retain the original nonlinear term" if the polynomial reformulation is too complex, but does not explain how such non-polynomial terms are handled in the hypergraph encoding and in the GPU-accelerated loss Eq. (4). Clarify this hybrid case or restrict the method to polynomial objectives.
  4. [Sec. 6.1] "We generate a specific BIP instance for each size of variables" suggests a single instance per size. This makes the reported solution-time ratios and quality ratios in Fig. 4 sensitive to instance-specific effects; please report results over multiple random instances with error bars or confidence intervals.
  5. [Table 1] The numbers in Table 1 are typeset without separating spaces (e.g., "6513,978"), making the table difficult to read. Please reformat and, ideally, include the objective values in consistent notation (number of cuts vs. the minimized PUBO objective of Eq. (15)).
  6. [Sec. 6.1] The comparative ratio is defined as Os_BIPNN / Os_SCIP, but since the problems are minimization the text should explicitly state that lower values are better; also label the y-axis of Figs. 4c-4f accordingly.
  7. [Figures 4 and 5] No error bars or confidence intervals are shown. Given the stochastic nature of neural-network training and the possible variance across problem instances, please add repetitions and report standard deviations.
  8. [Reference [20] and Sec. 3.2] The annealing strategy (CRA) is described only in words; include the update rule for γ (e.g., linear or exponential ramp, final value) so that the schedule is reproducible without consulting the external reference.
  9. [Sec. 1 and 3.1] The phrase "one-to-one mapping between polynomial BIP objectives and hypergraph structures" is imprecise: a hypergraph alone does not determine the coefficients in the PUBO objective; rather, a PUBO is encoded by a hypergraph together with a coefficient vector Q. Consider rephrasing to reflect the role of the coefficients.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the reformulations are explicit constructions, and no load-bearing self-citations or fitted predictions are present.

full rationale

The paper's derivation chain is self-contained. In Sec. 4.1, the polynomial reformulation (Eqs. 5-6) is an explicit interpolation construction: the coefficients c_S are computed from function values by inclusion-exclusion, so the polynomial exactly matches the original binary function by construction rather than by assuming the target result. In Sec. 4.2, the polynomial penalty is constructed from enumerated minimal violation subsets (Eqs. 8-9); although this construction has a substantive correctness gap for non-monotone constraints (e.g., g = x1 - x2 <= 0 would be penalized at the feasible point (1,1)), that is a validity issue, not circularity, because the penalty is not fitted to the solution being predicted and no equation is assumed equal to itself. The hypergraph/PUBO correspondence (Fig. 2 and Eq. 4) is a representational encoding of monomials as hyperedges, not a derived prediction. The external components are third-party methods (HGNN+ [17], CRA [20]) used as building blocks, and the paper contains no self-citations that carry argumentative weight. No fitted parameters are presented as predictions, and no known result is merely renamed as a new derivation. Therefore the circularity score is 0.

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

The central claim rests on classical interpolation and standard penalty theory, plus three empirical assumptions: that violation subsets are enumerable, that annealing produces binary solutions, and that HyperGNN can minimize the PUBO loss. No new physical or mathematical objects are postulated. The main free parameters are the penalty coefficients and annealing schedule, which are hand-tuned.

free parameters (4)
  • Penalty coefficients lambda_k, mu_l = not specified, described as 'sufficiently large'
    Used in Eq 7; too small yields infeasible solutions, too large can distort the objective; no heuristic or tuning rule given.
  • Annealing schedule (gamma start, ramp epochs, final value) = gamma=-2.5 initially, reaches 0 at epoch 500, increases after (Sec 6.4)
    Hand-picked for Cora; no general schedule or sensitivity analysis is provided.
  • Discreteness penalty exponent alpha = even integer, value not stated
    Appears in the penalty term phi(x); controls the shape of the binary-preference penalty; alpha is not specified.
  • Network hyperparameters (layers, hidden dims, learning rate) = two-layer HGNN+ (Sec 6 implementation), other values not reported
    Architecture choice and training hyperparameters are not given, hindering reproduction.
assumptions (5)
  • standard math Any function on {0,1}^m has a unique multilinear polynomial representation; coefficients computed by inclusion-exclusion (Eq 5-6).
    Used in Section 4.1 to replace sin, log, exp terms with polynomials; classical interpolation over finite sets.
  • domain assumption A penalty term that is zero on feasible points and positive on violating points, added with sufficiently large coefficient, preserves the optimal solution of the constrained problem.
    Standard penalty method (Nocedal and Wright [21]), but the paper gives no value or bound for the penalty coefficients.
  • domain assumption Minimal violation subsets V can be enumerated in practical time; real-world constraints have local structure.
    Section 4.2 step (i) requires checking up to 2^Delta subsets for a constraint with Delta variables; the paper argues locality but provides no supporting instances or bounds.
  • domain assumption The continuous relaxation with annealing converges to binary feasible solutions for the problems tested.
    Section 3.2 and 6.4 show this empirically for one dataset; no convergence theorem is given.
  • domain assumption A hypergraph neural network can minimize PUBO objectives through gradient descent well enough to beat classical heuristics.
    The core empirical claim of the paper; supported only by the experiments reported, with no theoretical grounding.

how reviews work

0 comments
Cite this review

Pith. "Pith review of BIPNN: Learning to Solve Binary Integer Programming via Hypergraph Neural Networks." pith.science (2026). https://pith.science/paper/XTFRM6W3

@misc{pith2026250520997,
  author       = {Pith},
  title        = {Pith review of: BIPNN: Learning to Solve Binary Integer Programming via Hypergraph Neural Networks},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/XTFRM6W3}},
  note         = {Machine review of arXiv:2505.20997}
}
read the original abstract

Binary (0-1) integer programming (BIP) is pivotal in scientific domains requiring discrete decision-making. As the advance of AI computing, recent works explore neural network-based solvers for integer linear programming (ILP) problems. Yet, they lack scalability for tackling nonlinear challenges. To handle nonlinearities, state-of-the-art Branch-and-Cut solvers employ linear relaxations, leading to exponential growth in auxiliary variables and severe computation limitations. To overcome these limitations, we propose BIPNN (Binary Integer Programming Neural Network), an unsupervised learning framework to solve nonlinear BIP problems via hypergraph neural networks (HyperGNN). Specifically, BIPNN reformulates BIPs-constrained, discrete, and nonlinear (sin, log, exp) optimization problems-into unconstrained, differentiable, and polynomial loss functions. The reformulation stems from the observation of a precise one-to-one mapping between polynomial BIP objectives and hypergraph structures, enabling the unsupervised training of HyperGNN to optimize BIP problems in an end-to-end manner. On this basis, we propose a GPU-accelerated and continuous-annealing-enhanced training pipeline for BIPNN. The pipeline enables BIPNN to optimize large-scale nonlinear terms in BIPs fully in parallel via straightforward gradient descent, thus significantly reducing the training cost while ensuring the generation of discrete, high-quality solutions. Extensive experiments on synthetic and real-world datasets highlight the superiority of our approach.

Figures

Figures reproduced from arXiv: 2505.20997 by the authors.

Figure 1
Figure 1. The BIPNN framework. (LP) solvers (e.g., the Simplex method1 ). Consequently, large-scale nonlinear BIPs often suffer from prohibitive computational costs. As BIP solvers continue to evolve, linearization remains indispensable for making nonlinearities more tractable for BIP solvers. These limitations motivate us to develop a streamlined and general-purpose BIP solver to advance the state of the art. To profoundly a… view at source ↗
Figure 2
Figure 2. Modeling PUBO-formulated BIPs via hypergraphs. [PITH_FULL_IMAGE:figures/full_fig_p004_2.png] view at source ↗
Figure 3
Figure 3. To solve the hypergraph max-cut problem, BIPNN generates a new hypergraph structure. However, both of [PITH_FULL_IMAGE:figures/full_fig_p006_3.png] view at source ↗
Figures from the paper (4 more)
Figure 4
Figure 4. Figure 4: Comparison of BIPNN and existing BIP solvers. [PITH_FULL_IMAGE:figures/full_fig_p007_4.png]
Figure 5
Figure 5. Figure 5: Comparison of the quality of solutions and time efficiency of BIPNN when it applys its generated hypergraph [PITH_FULL_IMAGE:figures/full_fig_p008_5.png]
Figure 6
Figure 6. Figure 6: Comparison of the training time for BIPNN with or without GPU accelerated algo￾rithm for PUBO losses. 6.4 Ablation Study GPU Acceleration. The superior time efficiency of BIPNN is primarily attributed to the GPU-accelerated algorithm employed in computing large-scale P…
Figure 7
Figure 7. Figure 7: Quality and discrete￾ness of solutions with or without the annealing strategy. This work proposes BIPNN, a novel neural network solver for nonlinear BIP prob￾lems. It reformulates nonlinear BIPs into PUBO cost functions, which correspond to hypergraph structures. On th…

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

39 extracted references · 38 canonical work pages

  1. [1]

    Yan Qiao, Yanjun Lu, Jie Li, Siwei Zhang, Naiqi Wu, and Bin Liu. An efficient binary integer programming model for residency time-constrained cluster tools with chamber cleaning requirements.IEEE Transactions on Automation Science and Engineering, 19(3):1757–1771, 2021

    work page 2021

  2. [2]

    Constrained discrete black-box optimization using mixed-integer programming

    Theodore P Papalexopoulos, Christian Tjandraatmadja, Ross Anderson, Juan Pablo Vielma, and David Belanger. Constrained discrete black-box optimization using mixed-integer programming. InInternational Conference on Machine Learning, pages 17295–17322. PMLR, 2022

    work page 2022

  3. [3]

    Libin Wang, Han Hu, Qisen Shang, Haowei Zeng, and Qing Zhu. Struc- turedmesh: 3-d structured optimization of façade components on photogram- metric mesh models using binary integer programming.IEEE Transactions on Geoscience and Remote Sensing, 62:1–12, 2024

    work page 2024

  4. [4]

    Optimal qubit assignment and routing via integer programming.ACM Transactions on Quantum Computing, 4(1):1–31, 2022

    Giacomo Nannicini, Lev S Bishop, Oktay Günlük, and Petar Jurcevic. Optimal qubit assignment and routing via integer programming.ACM Transactions on Quantum Computing, 4(1):1–31, 2022

    work page 2022

  5. [5]

    Hybrid classical- quantum optimization techniques for solving mixed-integer programming prob- lems in production scheduling.IEEE Transactions on Quantum Engineering, 3:1–16, 2022

    Akshay Ajagekar, Kumail Al Hamoud, and Fengqi You. Hybrid classical- quantum optimization techniques for solving mixed-integer programming prob- lems in production scheduling.IEEE Transactions on Quantum Engineering, 3:1–16, 2022

    work page 2022

  6. [6]

    Hybrid quantum-classical computing for future network optimization.IEEE Network, 36(5):72–76, 2022

    Lei Fan and Zhu Han. Hybrid quantum-classical computing for future network optimization.IEEE Network, 36(5):72–76, 2022

    work page 2022

  7. [7]

    Align- ment of biological networks by integer linear programming: virus-host protein- protein interaction networks.BMC bioinformatics, 21(Suppl 6):434, 2020

    Mercè Llabrés, Gabriel Riera, Francesc Rosselló, and Gabriel Valiente. Align- ment of biological networks by integer linear programming: virus-host protein- protein interaction networks.BMC bioinformatics, 21(Suppl 6):434, 2020

    work page 2020

  8. [8]

    Jianshen Zhu, Naveed Ahmed Azam, Fan Zhang, Aleksandar Shurbevski, Kazuya Haraguchi, Liang Zhao, Hiroshi Nagamochi, and Tatsuya Akutsu. A novel method for inferring chemical compounds with prescribed topological substructures based on integer programming.IEEE/ACM Transactions on Computational Biology and Bioinformatics, 19(6):3233–3245, 2021

    work page 2021

Show all 39 references
  1. [9]

    Optimality guarantees for crystal structure prediction.Nature, 619(7968):68–72, 2023

    Vladimir V Gusev, Duncan Adamson, Argyrios Deligkas, Dmytro Anty- pov, Christopher M Collins, Piotr Krysta, Igor Potapov, George R Darling, Matthew S Dyer, Paul Spirakis, et al. Optimality guarantees for crystal structure prediction.Nature, 619(7968):68–72, 2023

    2023

  2. [10]

    A mixed integer linear programming approach for the design of chemical process families.Computers & Chemical Engineering, 183:108620, 2024

    Georgia Stinchfield, Joshua C Morgan, Sakshi Naik, Lorenz T Biegler, John C Eslick, Clas Jacobson, David C Miller, John D Siirola, Miguel Zamarripa, Chen Zhang, et al. A mixed integer linear programming approach for the design of chemical process families.Computers & Chemical ...

    2024

  3. [11]

    Springer, 2010

    Richard M Karp.Reducibility among combinatorial problems. Springer, 2010

    2010

  4. [12]

    Mip-gnn: A data-driven framework for guiding combinatorial solvers

    Elias B Khalil, Christopher Morris, and Andrea Lodi. Mip-gnn: A data-driven framework for guiding combinatorial solvers. InProceedings of the AAAI Conference on Artificial Intelligence, volume 36, pages 10219–10227, 2022

    2022

  5. [13]

    Gnn&gbdt-guided fast optimizing framework for large-scale integer program- ming

    Huigen Ye, Hua Xu, Hongyan Wang, Chengming Wang, and Yu Jiang. Gnn&gbdt-guided fast optimizing framework for large-scale integer program- ming. InInternational conference on machine learning, pages 39864–39878. PMLR, 2023

    2023

  6. [14]

    PySCIPOpt: Mathematical programming in python with the SCIP optimization suite

    Stephen Maher, Matthias Miltenberger, João Pedro Pedroso, Daniel Rehfeldt, Robert Schwarz, and Felipe Serrano. PySCIPOpt: Mathematical programming in python with the SCIP optimization suite. InMathematical Software – ICMS 2016, pages 301–307. Springer International Publishing, 2016

    2016

  7. [15]

    Scip: solving constraint integer programs.Mathematical Programming Computation, 1:1–41, 2009

    Tobias Achterberg. Scip: solving constraint integer programs.Mathematical Programming Computation, 1:1–41, 2009. 10 APREPRINT- SEPTEMBER18, 2025

    2009

  8. [16]

    A new polynomial-time algorithm for linear program- ming

    Narendra Karmarkar. A new polynomial-time algorithm for linear program- ming. InProceedings of the sixteenth annual ACM symposium on Theory of computing, pages 302–311, 1984

    1984

  9. [17]

    Hgnn+: General hyper- graph neural networks.IEEE Transactions on Pattern Analysis and Machine Intelligence, 45(3):3181–3199, 2022

    Yue Gao, Yifan Feng, Shuyi Ji, and Rongrong Ji. Hgnn+: General hyper- graph neural networks.IEEE Transactions on Pattern Analysis and Machine Intelligence, 45(3):3181–3199, 2022

    2022

  10. [18]

    Hypergcn: A new method for training graph convo- lutional networks on hypergraphs.Advances in neural information processing systems, 32, 2019

    Naganand Yadati, Madhav Nimishakavi, Prateek Yadav, Vikram Nitin, Anand Louis, and Partha Talukdar. Hypergcn: A new method for training graph convo- lutional networks on hypergraphs.Advances in neural information processing systems, 32, 2019

    2019

  11. [19]

    Unignn: a unified framework for graph and hy- pergraph neural networks

    Jing Huang and Jie Yang. Unignn: a unified framework for graph and hy- pergraph neural networks. Inthe Thirtieth International Joint Conference on Artificial Intelligence (IJCAI), 2021

    2021

  12. [20]

    Controlling continuous relaxation for combinatorial opti- mization.Advances in Neural Information Processing Systems (NeurIPS), 37:47189–47216, 2024

    Yuma Ichikawa. Controlling continuous relaxation for combinatorial opti- mization.Advances in Neural Information Processing Systems (NeurIPS), 37:47189–47216, 2024

    2024

  13. [21]

    Springer, 1999

    Jorge Nocedal and Stephen J Wright.Numerical optimization. Springer, 1999

    1999

  14. [22]

    Quantum bridge analytics i: a tutorial on formulating and using qubo models.Annals of Operations Research, 314(1):141–183, 2022

    Fred Glover, Gary Kochenberger, Rick Hennig, and Yu Du. Quantum bridge analytics i: a tutorial on formulating and using qubo models.Annals of Operations Research, 314(1):141–183, 2022

    2022

  15. [23]

    Springer, 1998

    Fred Glover and Manuel Laguna.Tabu search. Springer, 1998. 11 APREPRINT- SEPTEMBER18, 2025 A A toy example of the polynomial reformulation of BIP (Sec. 4). For sin(x1 +x 2 +x 3), where x1, x2, x3 ∈ {0,1}, we can construct a polynomial to precisely fit the function, such that i...

    1998

  16. [24]

    Thus,d= 0

    Whenx 1 = 0, x2 = 0, x3 = 0:P(0,0,0) =d= sin(0) = 0. Thus,d= 0

  17. [25]

    Thus,a 3 = 0.8415

    Whenx 1 = 0, x2 = 0, x3 = 1:P(0,0,1) =a 3 = sin(1)≈0.8415. Thus,a 3 = 0.8415

  18. [26]

    Thus,a 2 = 0.8415

    Whenx 1 = 0, x2 = 1, x3 = 0:P(0,1,0) =a 2 = sin(1)≈0.8415. Thus,a 2 = 0.8415

  19. [27]

    Thus,a 1 = 0.8415

    Whenx 1 = 1, x2 = 0, x3 = 0:P(1,0,0) =a 1 = sin(1)≈0.8415. Thus,a 1 = 0.8415

  20. [28]

    Substitutinga 2 = 0.8415anda 3 = 0.8415:b 23 =−0.7737

    Whenx 1 = 0, x2 = 1, x3 = 1:P(0,1,1) =a 2 +a 3 +b 23 = sin(2)≈0.9093. Substitutinga 2 = 0.8415anda 3 = 0.8415:b 23 =−0.7737

  21. [29]

    Whenx 1 = 1, x2 = 0, x3 = 1:P(1,0,1) =a 1 +a 3 +b 13 = sin(2)≈0.9093 Substitutinga 1 = 0.8415anda 3 = 0.8415:b 13 =−0.7737

  22. [30]

    Whenx 1 = 1, x2 = 1, x3 = 0:P(1,1,0) =a 1 +a 2 +b 12 = sin(2)≈0.9093 Substitutinga 1 = 0.8415anda 2 = 0.8415:b 12 =−0.7737

  23. [31]

    Substituting known values:c=−0.0623

    Whenx 1 = 1, x2 = 1, x3 = 1:P(1,1,1) =a 1 +a 2 +a 3 +b 12 +b 13 +b 23 +c= sin(3)≈0.1411. Substituting known values:c=−0.0623. Based on the above calculations, the polynomial is: P(x 1, x2, x3) = 0.8415(x1 +x 2 +x 3)−0.7737(x 1x2 +x 1x3 +x 2x3)−0.0623x 1x2x3 (12) B A toy exampl...

  24. [32]

    Whenx 1 = 0, x2 = 0, x3 = 0:g(x) = 1≤5, feasible

  25. [33]

    Whenx 1 = 0, x2 = 0, x3 = 1:g(x) = 1≤5, feasible

  26. [34]

    Whenx 1 = 0, x2 = 1, x3 = 0:g(x) =e≤5, feasible

  27. [35]

    Whenx 1 = 1, x2 = 0, x3 = 0:g(x) = 3≤5, feasible

  28. [36]

    Whenx 1 = 0, x2 = 1, x3 = 1:g(x) =e≤5, feasible

  29. [37]

    Whenx 1 = 1, x2 = 0, x3 = 1:g(x) = 6≥5, violation

  30. [38]

    Whenx 1 = 1, x2 = 1, x3 = 0:g(x) =e+ 2≤5, feasible

  31. [39]

    Identified minimal violation subsets:{x 1, x3}

    Whenx 1 = 1, x2 = 1, x3 = 1:g(x) = 5 +e≥5, violation (not minimal). Identified minimal violation subsets:{x 1, x3}. Thus, P(x) =λ(x 1x3)(13) Final BIP objective: OBIP =f(x) +λ(x 1x3)(14) C The hypergraph max-cut problem. The max-cut problem of a hypergraph G= (V, E) involves p...

    2025

Pith tools

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