論文の概要: On Representing Mixed-Integer Linear Programs by Graph Neural Networks
- arxiv url: http://arxiv.org/abs/2210.10759v1
- Date: Wed, 19 Oct 2022 17:56:07 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-20 15:49:43.510618
- Title: On Representing Mixed-Integer Linear Programs by Graph Neural Networks
- Title(参考訳): グラフニューラルネットワークによる混合整数線形プログラムの表現について
- Authors: Ziang Chen, Jialin Liu, Xinshang Wang, Jianfeng Lu, Wotao Yin
- Abstract要約: 混合整数線形プログラミング(MILP)は一般にNPハードであるが, 実用的MILPは過去20年間で約100倍の高速化を実現している。
しかし、全てのGNNが平等に扱うような、実現不可能で実現不可能なMILPが存在する。
我々は、MILPを展開可能なものに制限したり、ランダムな特徴を加えることで、MILPの実現可能性、最適目標値、最適解を所定の精度で確実に予測できるGNNが存在することを示す。
- 参考スコア(独自算出の注目度): 30.998508318941017
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: While Mixed-integer linear programming (MILP) is NP-hard in general,
practical MILP has received roughly 100--fold speedup in the past twenty years.
Still, many classes of MILPs quickly become unsolvable as their sizes increase,
motivating researchers to seek new acceleration techniques for MILPs. With deep
learning, they have obtained strong empirical results, and many results were
obtained by applying graph neural networks (GNNs) to making decisions in
various stages of MILP solution processes. This work discovers a fundamental
limitation: there exist feasible and infeasible MILPs that all GNNs will,
however, treat equally, indicating GNN's lacking power to express general
MILPs. Then, we show that, by restricting the MILPs to unfoldable ones or by
adding random features, there exist GNNs that can reliably predict MILP
feasibility, optimal objective values, and optimal solutions up to prescribed
precision. We conducted small-scale numerical experiments to validate our
theoretical findings.
- Abstract(参考訳): Mixed-integer linear programming (MILP) は一般にNP-hardであるのに対し、実践的なMILPは過去20年間で約100倍のスピードアップを受けている。
それでも多くのミルプのクラスは、そのサイズが大きくなるとすぐに解決不能になり、研究者がミルプの新しい加速技術を探す動機となった。
深層学習では実験結果が強く,MILPソリューションプロセスの様々な段階における決定にグラフニューラルネットワーク(GNN)を適用することにより,多くの結果が得られた。
しかしながら、全てのGNNが同等に扱い、一般的なMILPを表現する能力が欠如していることを示す、実現不可能なMILPが存在する。
次に,ミルプを展開可能なものに制限したり,ランダムな特徴を加えたりすることで,ミルプ実現可能性,最適目的値,最適解を所定の精度で確実に予測できるgnnが存在することを示す。
理論的結果を検証するため, 小規模数値実験を行った。
関連論文リスト
- Rethinking the Capacity of Graph Neural Networks for Branching Strategy [43.97990814066709]
グラフニューラルネットワーク(GNN)は、混合整数線形プログラム(MILP)の特性や性質を予測するために広く用いられている。
本稿では,GNNの高次分岐(SB)スコアの表現能力について検討し,分岐とバウンドのアルゴリズムにおける効率的な戦略を提案する。
論文 参考訳(メタデータ) (2024-02-11T04:09:50Z) - MAG-GNN: Reinforcement Learning Boosted Graph Neural Network [68.60884768323739]
特定の研究の行は、GNNの表現性を向上させるためにサブグラフ情報を使用するサブグラフGNNを提案し、大きな成功を収めた。
このような効果は、すべての可能な部分グラフを列挙することによって、GNNの効率を犠牲にする。
本稿では,強化学習(RL)により強化されたGNNである磁気グラフニューラルネットワーク(MAG-GNN)を提案する。
論文 参考訳(メタデータ) (2023-10-29T20:32:21Z) - Graph Neural Networks are Inherently Good Generalizers: Insights by
Bridging GNNs and MLPs [71.93227401463199]
本稿では、P(ropagational)MLPと呼ばれる中間モデルクラスを導入することにより、GNNの性能向上を本質的な能力に向ける。
PMLPは、トレーニングにおいてはるかに効率的でありながら、GNNと同等(あるいはそれ以上)に動作することを観察する。
論文 参考訳(メタデータ) (2022-12-18T08:17:32Z) - QVIP: An ILP-based Formal Verification Approach for Quantized Neural
Networks [14.766917269393865]
量子化は、浮動小数点数に匹敵する精度でニューラルネットワークのサイズを減らすための有望な技術として登場した。
そこで本研究では,QNNに対する新しい,効率的な形式検証手法を提案する。
特に、QNNの検証問題を整数線形制約の解法に還元する符号化を初めて提案する。
論文 参考訳(メタデータ) (2022-12-10T03:00:29Z) - On Representing Linear Programs by Graph Neural Networks [30.998508318941017]
グラフニューラルネットワーク(GNN)は最適化問題に適した機械学習モデルであると考えられている。
本稿では,線形プログラム(LP)問題にGNNを適用する理論的基礎を確立する。
適切に構築されたGNNは、幅広いクラスにおける各LPに対して、実現可能性、有界性、最適解を確実に予測できることを示す。
論文 参考訳(メタデータ) (2022-09-25T18:27:33Z) - Smart Feasibility Pump: Reinforcement Learning for (Mixed) Integer
Programming [0.0]
本稿では,(混合)整数プログラミング(MIP)問題に対する実現可能な解を見つけるための深層強化学習(DRL)モデルを提案する。
多くの成功者は既知の初期の実現可能なソリューションに依存しているため、MIP問題に対する実現可能なソリューションを見つけることは重要です。
マルチレイヤ認識(MLP)に加えて,制約行列の隠れ情報を取得するために,ポリシーネットワークのための新しい畳み込みネットワーク(CNN)構造を提案する。
論文 参考訳(メタデータ) (2021-02-18T23:18:17Z) - How Neural Networks Extrapolate: From Feedforward to Graph Neural
Networks [80.55378250013496]
勾配勾配降下法によりトレーニングされたニューラルネットワークが、トレーニング分布の支持の外で学んだことを外挿する方法について検討する。
グラフニューラルネットワーク(GNN)は、より複雑なタスクでいくつかの成功を収めている。
論文 参考訳(メタデータ) (2020-09-24T17:48:59Z) - Fast Learning of Graph Neural Networks with Guaranteed Generalizability:
One-hidden-layer Case [93.37576644429578]
グラフニューラルネットワーク(GNN)は、グラフ構造化データから実際に学習する上で、近年大きな進歩を遂げている。
回帰問題と二項分類問題の両方に隠れ層を持つGNNの理論的に基底的な一般化可能性解析を行う。
論文 参考訳(メタデータ) (2020-06-25T00:45:52Z) - Optimization and Generalization Analysis of Transduction through
Gradient Boosting and Application to Multi-scale Graph Neural Networks [60.22494363676747]
現在のグラフニューラルネットワーク(GNN)は、オーバースムーシング(over-smoothing)と呼ばれる問題のため、自分自身を深くするのは難しいことが知られている。
マルチスケールGNNは、オーバースムーシング問題を緩和するための有望なアプローチである。
マルチスケールGNNを含むトランスダクティブ学習アルゴリズムの最適化と一般化を保証する。
論文 参考訳(メタデータ) (2020-06-15T17:06:17Z) - Efficient Probabilistic Logic Reasoning with Graph Neural Networks [63.099999467118245]
マルコフ論理ネットワーク(MLN)は、多くの知識グラフ問題に対処するために用いられる。
MLNの推論は計算集約的であり、MLNの産業規模での応用は非常に困難である。
本稿では,表現力とモデルの単純さとのバランスのよいグラフニューラルネット(GNN)モデルであるExpressGNNを提案する。
論文 参考訳(メタデータ) (2020-01-29T23:34:36Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。