混合2値2次計画（MBQP）向けのML誘導プライマル・ヒューリスティクス

要旨: 混合バイナリ二次計画（Mixed Binary Quadratic Programs: MBQPs）は、組合せ最適化における重要で複雑な一群の問題である。大規模な組合せ最適化問題を解くことは困難であるため、短時間で高品質な解を迅速に特定するための原始（primal）ヒューリスティックが開発されてきた。近年では、解法を加速するために機械学習を用いる研究も増えている。これらMLに導かれた手法の人気が高まっている一方で、これまでの研究の大部分は混合整数線形計画（Mixed-Integer Linear Programs: MILPs）に焦点を当ててきた。MBQPsは、組合せ的な複雑性に加えて非線形性が結びついているため、解くことが難しい。本研究は、MLに導かれたMILP解法の予測に関する既存研究をMBQPsに適応し、さらに拡張することで、混合バイナリ二次計画（MBQPs）向けのMLガイド付き原始ヒューリスティックを提案する。MBQP解法予測のための新しいニューラルネットワークのアーキテクチャと、新しい学習データ収集手順を導入する。さらに、解法予測における既存の損失関数を拡張し、コントラスト損失と重み付き交差エントロピー損失を組み合わせることを提案する。標準的および実世界のMBQPベンチマークで手法を評価し、その開発したMLガイド付き手法が、既存の原始ヒューリスティックおよび最先端のソルバを大幅に上回ることを示す。加えて、提案する拡張（結合損失）で学習したモデルは、MILPから適応した他のMLベース手法よりも優れており、実世界の風力発電所レイアウト最適化問題における領域をまたいだ推論（クロスリージョナル推論）での汎化性能が向上することを示す。