Study on Practical Algorithms for Nonlinear Integer Programs Based on Discrete Convex Analysis Approach

基于离散凸分析法的非线性整数规划实用算法研究

• 批准号: 18740042
• 负责人: SHIOURA Akiyoshi
• 金额: $ 2.41万
• 依托单位: Tohoku University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Young Scientists (B)
• 财政年份: 2006
• 资助国家: 日本
• 起止时间: 2006 至 2008
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-18740042/
• 关键词: 組合せ最適化; 非線形関数; 整数計画; 離散凸関数; 近似解法; アルゴリズム; マトロイド; 劣モジュラ関数; 非線形計画; 凸解析; 凸関数; 離散凸解析

整数計画問題とは,与えられた制約条件を満たす整数ベクトルの中から,与えられた目的関数を最小化(または最大化)する解を求める問題である.一般に整数計画問題は短時間で解くことが困難である,ということが理論的にも現実的にも知られている.とくに,目的関数と条件が非線形関数で与えられる非線形整数計画問題は,解くことが最も困難な整数計画のクラスである.本研究では,様々な非線形整数計画問題に対して,その良質な近似解を短時間で求めるアルゴリズムを提案した.

整数规划问题是从满足给定约束的整数向量中找到最小化（或最大化）给定目标函数的解决方案的问题。整数规划问题通常在短时间内得到解决。特别是，目标函数和条件由非线性函数给出的非线性整数规划问题是整数规划中最难解决的一类，我们提出了一种可以在短时间内找到近似解的算法。

项目成果

ジャンプシステム上の最適化問題に対するアルゴリズム

跳跃系统优化问题的算法

• 发表时间: 2007
• 作者: 石渡 哲哉;矢崎成俊;久保雅義;Masayoshi Kubo;T.Ishiwata and S.Yazaki;久保雅義;塩浦昭義
• 通讯作者: 塩浦昭義

Polynomial-Time Algorithms for Linear and Convex Optimization on Jump Systems

跳跃系统线性和凸优化的多项式时间算法

• 期刊: SIAM Journal on Discrete Mathematics (to appear)
• 作者: Akiyoshi Shioura;Ken'ichiro Tanaka
• 通讯作者: Ken'ichiro Tanaka

劣モジュラ関数最大化に対する近似アルゴリズムと離散凹性

子模函数最大化的逼近算法和离散凹性

• 发表时间: 2008
• 作者: T. Ishiwata;S. Yazaki;塩浦昭義
• 通讯作者: 塩浦昭義

A Fast Divide-and-Conquer Algorithm for Polymatroid Optimization and Its Application to Preemptive Scheduling Problems with Controllable Processing Times

多拟阵优化的快速分治算法及其在处理时间可控的抢占式调度问题中的应用

• 发表时间: 2009
• 作者: S. Albeverio;S. Liang and B. Zegarlinski;Hironori Kasai;T. Ishiwata;笠井博則;塩浦昭義
• 通讯作者: 塩浦昭義