半整数制約付き種別構成問題に対する高性能錐最適化手法の構築
【研究キーワード】
応用数学 / 数理最適化 / 錐最適化 / 混合整数計画問題 / 半整数制約 / 育種学 / 種別構成問題
【研究成果の概要】
本研究課題では、種別構成問題において各変数が半整数となるような制約を付加した最適化問題に対する効率的な計算手法の開発を行った。錐分割手法では、切除平面の計算が解析的に行えるようにし、半整数制約と合わせて混合整数計画問題を解く反復解法を構築した。また、別の手法として、半整数制約と錐制約をそれぞれの子問題に分解する方法を改良し、一部の制約を含ませることで良好な解を生成可能とした。
【研究の社会的意義】
半整数制約は、変数が 0 あるいは一定の範囲の整数となっているような制約である。例えばポートフォリオ構築などであれば、資産をポートフォリオに組み込む場合に手数料などから最低限組み込むべき量が決まっている場合などが想定される。本研究で構築した計算手法は半整数制約を伴うような錐最適化問題に特に効果が高いと考えられる。また、数理最適化問題が複雑になったときに子問題への分解は良く行われる手法であり、特定の制約を含ませる本研究の方法は多くの手法の改善に利用できる可能性がある。
【研究代表者】
【研究種目】基盤研究(C)
【研究期間】2018-04-01 - 2022-03-31
【配分額】4,030千円 (直接経費: 3,100千円、間接経費: 930千円)