論文の概要: Cable Tree Wiring -- Benchmarking Solvers on a Real-World Scheduling
Problem with a Variety of Precedence Constraints
- arxiv url: http://arxiv.org/abs/2011.12862v1
- Date: Wed, 25 Nov 2020 16:34:04 GMT
- ステータス: 処理完了
- システム内更新日: 2022-09-21 02:47:04.945969
- Title: Cable Tree Wiring -- Benchmarking Solvers on a Real-World Scheduling
Problem with a Variety of Precedence Constraints
- Title（参考訳）: ケーブルツリー配線 --様々な事前制約を伴う実世界のスケジューリング問題に対するベンチマーク解法
- Authors: Jana Koehler, Joseph B\"urgler, Urs Fontana, Etienne Fux, Florian
Herzog, Marc Pouly, Sophia Saller, Anastasia Salyaeva, Peter Scheiblechner,
Kai Waelti
- Abstract要約: ケーブルツリーの所定のレイアウトに対して最適な配線順序を導出する問題を研究・定式化する。
我々は,このケーブルツリー配線問題 (CTW) を,原子,軟質原子,および解離性優先制約を伴う旅行セールスマン問題としてモデル化する研究を要約する。
問題に対する様々なモデリングのバリエーションについて議論し、NP-hardnessを証明し、278インスタンスのベンチマークセット上でCP, OMT, MIPソルバを実証的に比較する。
- 参考スコア（独自算出の注目度）: 1.7877820096199728
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Cable trees are used in industrial products to transmit energy and
information between different product parts. To this date, they are mostly
assembled by humans and only few automated manufacturing solutions exist using
complex robotic machines. For these machines, the wiring plan has to be
translated into a wiring sequence of cable plugging operations to be followed
by the machine. In this paper, we study and formalize the problem of deriving
the optimal wiring sequence for a given layout of a cable tree. We summarize
our investigations to model this cable tree wiring Problem (CTW) as a traveling
salesman problem with atomic, soft atomic, and disjunctive precedence
constraints as well as tour-dependent edge costs such that it can be solved by
state-of-the-art constraint programming (CP), Optimization Modulo Theories
(OMT), and mixed-integer programming (MIP) solvers. It is further shown, how
the CTW problem can be viewed as a soft version of the coupled tasks scheduling
problem. We discuss various modeling variants for the problem, prove its
NP-hardness, and empirically compare CP, OMT, and MIP solvers on a benchmark
set of 278 instances. The complete benchmark set with all models and instance
data is available on github and is accepted for inclusion in the MiniZinc
challenge 2020.
- Abstract（参考訳）: ケーブルツリーは、異なる製品部品間でエネルギーと情報を伝達するために工業製品に使用される。
今日まで、それらはほとんど人間によって組み立てられ、複雑なロボットマシンを使用して自動化された製造ソリューションはごくわずかである。
これらの機械の場合、配線計画は、その機械に追従するケーブルプラグ操作の配線シーケンスに変換されなければならない。
本稿では,ケーブルツリーの所定のレイアウトに対して最適な配線シーケンスを導出する問題を考察し,定式化する。
我々は,このケーブルツリー配線問題 (CTW) を,最先端制約プログラミング (CP) や最適化モジュロ理論 (OMT) ,混合整数プログラミング (MIP) の解法によって解決可能なツアー依存エッジコストとともに,原子,軟質原子,および偏在性優先制約を用いた旅行セールスマン問題としてモデル化する研究を要約する。
さらに,ctw問題を結合タスクスケジューリング問題のソフトバージョンと見なすことができることを示した。
問題に対する様々なモデリングのバリエーションについて議論し、NP硬度を証明し、278インスタンスのベンチマークセット上でCP, OMT, MIPソルバを実証的に比較する。
すべてのモデルとインスタンスデータの完全なベンチマークセットはgithubで利用可能であり、MiniZinc Challenge 2020に含められている。
関連論文リスト
- Automated Placement of Analog Integrated Circuits using Priority-based Constructive Heuristic [0.0]
われわれは,いわゆるポケット,合併の可能性,デバイス間のパラメトリジブルな最小距離を必要とする,特定の種類のアナログ配置に注目した。
我々の解は回路の境界ボックスの周長と近似ワイヤ長を最小化する。
本手法は,手作業による設計を伴い,合成された産業事例と実物実物実物実物実物実物実物実物実物実物実物実物実物実物実物実物実物実物実物実物実物実物実物実物実物実物実物実物実物実物実物実物実物実物実物実物実物実物実物実物実物実物実物実物実物実物実物実物実
論文 参考訳（メタデータ） (2024-10-18T07:16:59Z) - An Unsupervised Learning Framework Combined with Heuristics for the Maximum Minimal Cut Problem [5.092968949752308]
本研究は,MMCPの最大値と非教師なし学習フレームワークを提案する。
重要な観察は、それぞれの溶液が少なくとも1本の枝木に対応することである。
フレームワークを評価し、特定のアプリケーションを提供するために、広範な実験を行います。
論文 参考訳（メタデータ） (2024-08-16T02:07:34Z) - How Realistic Is Your Synthetic Data? Constraining Deep Generative
Models for Tabular Data [57.97035325253996]
本稿では,制約付き深部生成モデル(C-DGM)をリアルな合成データモデルに変換する方法について述べる。
C-DGMは、制約によって表現される背景知識を活用して、標準知識より優れている。
論文 参考訳（メタデータ） (2024-02-07T13:22:05Z) - Qubit efficient quantum algorithms for the vehicle routing problem on
NISQ processors [48.68474702382697]
時間窓付き車両ルーティング問題(VRPTW)は、ロジスティクス業界で直面する一般的な最適化問題である。
そこで本研究では,以前に導入した量子ビット符号化方式を用いて,バイナリ変数の数を削減した。
論文 参考訳（メタデータ） (2023-06-14T13:44:35Z) - Symmetric Tensor Networks for Generative Modeling and Constrained
Combinatorial Optimization [72.41480594026815]
ポートフォリオ最適化からロジスティクスに至るまで、制約付き最適化問題は業界に多い。
これらの問題の解決における主要な障害の1つは、有効な検索空間を制限する非自明なハード制約の存在である。
本研究では、Ax=bという形の任意の整数値等式制約をU(1)対称ネットワーク(TN)に直接エンコードし、それらの適用性を量子に着想を得た生成モデルとして活用する。
論文 参考訳（メタデータ） (2022-11-16T18:59:54Z) - On a Uniform Causality Model for Industrial Automation [61.303828551910634]
産業自動化の様々な応用分野に対する一様因果モデルを提案する。
得られたモデルは、サイバー物理システムの振る舞いを数学的に記述する。
このモデルは、機械学習に焦点を当てた産業自動化における新しいアプローチの応用の基盤として機能することが示されている。
論文 参考訳（メタデータ） (2022-09-20T11:23:51Z) - Exact methods and lower bounds for the Oven Scheduling Problem [5.7485371212305685]
Oven Scheduling Problem (OSP) は、電子部品製造の領域で発生する新しい並列バッチスケジューリング問題である。
オーブンの実行はエネルギー集約性の高いため、時間内にジョブを終了する以外に、すべてのオーブンの累積バッチ処理時間を最小化することが主な目的である。
本稿では、制約計画法(CP)と整数線形計画法(ILP)とそれに対応するモデルを用いて、このNPハードスケジューリング問題を解決することを提案する。
論文 参考訳（メタデータ） (2022-03-23T16:28:05Z) - An Information Theory-inspired Strategy for Automatic Network Pruning [88.51235160841377]
深層畳み込みニューラルネットワークは、リソース制約のあるデバイスで圧縮されることがよく知られている。
既存のネットワークプルーニング手法の多くは、人的努力と禁忌な計算資源を必要とする。
本稿では,自動モデル圧縮のための情報理論に基づく戦略を提案する。
論文 参考訳（メタデータ） (2021-08-19T07:03:22Z) - An SMT Based Compositional Model to Solve a Conflict-Free Electric
Vehicle Routing Problem [2.64699517152535]
CF-EVRP(Electric Conflict-Free Vehicle Routing Problem)は、車両の運転範囲の制限、顧客への配送時間帯の制限、道路セグメントが許容できる車両数に対する制限といった制約を含む。
我々は、問題をより小さく、より単純なサブプロブレムに分解し、準最適で実現可能なソリューションを提供する構成モデルを開発する。
論文 参考訳（メタデータ） (2021-06-10T20:37:46Z) - Quantum computing approach to railway dispatching and conflict
management optimization on single-track railway lines [0.4724825031148411]
単線鉄道における遅延と競合管理という,実用的な鉄道派遣問題について考察する。
本稿では,量子アニール技術と互換性のある2次非拘束二元最適化(QUBO)モデルを提案する。
概念実証として、D-Wave量子アニールを用いてポーランドの鉄道網から選択した実生活問題を解く。
論文 参考訳（メタデータ） (2020-10-16T08:17:57Z) - An Integer Linear Programming Framework for Mining Constraints from Data [81.60135973848125]
データから制約をマイニングするための一般的なフレームワークを提案する。
特に、構造化された出力予測の推論を整数線形プログラミング(ILP)問題とみなす。
提案手法は,9×9のスドクパズルの解法を学習し,基礎となるルールを提供することなく,例からツリー問題を最小限に分散させることが可能であることを示す。
論文 参考訳（メタデータ） (2020-06-18T20:09:53Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。