タグ

整数計画法に関するnyamappのブックマーク (2)

  • 最長片道きっぷの経路を求める

    最長片道きっぷの経路を求める Index & Overview あらまし この文書は、JRの最長片道きっぷの経路を、 整数計画法と全探索の2つの方法で求めた過程をまとめたものです。 前者では厳密に、後者ではややイイカゲンに、その経路を求めることに成功し、 2つの方法で求めた経路は一致しました。 トピックス NHK の紀行番組「列島縦断 鉄道12000kmの旅」をきっかけにこの Web ページを探し当てた方は、まず「付録2(2004年3月版)」をご覧ください。 現状の最長片道きっぷの経路や、ありそうな質問をまとめてあります。 ふと思い立って、2006年5月版の最長片道きっぷ経路図(PDF 形式、35,414 bytes)を作りました。 2004年3月版の地図との相違点はただ1点、 「富山港線を削除した」ことです(2006年2月28日廃止)。 もともと最長経路に含まれていなかった路線が廃止にな

  • 分数切除平面法(ゴモリーカット)の頂点彩色問題への適用

    明治大学理工学部情報科学科 計算理論研究室 中田 寛基 概要 巡回セールスマン問題(TSP)などの難しい問題を解く手法の一つに、数理計画法というものがある。その手法を、定式化した彩色問題に応用できないかを考える。 研究背景、目的 CPLEX(Ilog社)などの数理計画問題ソルバーが強力になってきている。 巡回セールスマン問題(TSP)などにおいて、数理計画法(と分枝限定などの組み合わせ)が良い成績を残している。 その数理計画法を学び他の問題に応用できないかを考える。 彩色問題が整数計画法に定式化できるので、より高速に解を求めたい。 彩色問題以外にも、整数計画法に定式化できる問題に対するアプローチの開発にもつながるはずである。 内容 数理計画法について 分数切除平面法(ゴモリーカット)について 頂点彩色問題の定式化 実験結果 参考資料 「オペレーションズ・リサーチ」 森雅夫、松井知己 経営シ

  • 1