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/
• 关键词: 組合せ最適化; 非線形関数; 整数計画; 離散凸関数; 近似解法; アルゴリズム; マトロイド; 劣モジュラ関数; 非線形計画; 凸解析; 凸関数; 離散凸解析

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

The whole number of problems is calculated, and the whole number of problems is minimized (or maximized). In general, integer drawing problems can be solved in a short time, and the knowledge and knowledge of the theory of mathematical theory will be solved in a short time. In order to solve the most difficult problem of integer planning, the condition of non-shape number and non-shape integer drawing problem. The purpose of this study is to solve the problem of non-linear integer drawing, and to solve the problem in a short time.

项目成果

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

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

跳跃系统优化问题的算法

• 发表时间: 2007
• 作者: 石渡 哲哉;矢崎成俊;久保雅義;Masayoshi Kubo;T.Ishiwata and 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;笠井博則;塩浦昭義
• 通讯作者: 塩浦昭義

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

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

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