Continuous relaxation for discrete DC programming

• 成果类型: Article
• 署名作者: Maehara, Takanori; Marumo, Naoki; Murota, Kazuo
• 署名单位: Shizuoka University; RIKEN; University of Tokyo; Tokyo Metropolitan University
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-017-1139-2
• 发表日期: 2018
• 页码: 199-219
• 关键词: convex function minimization

摘要

Discrete DC programming with convex extensible functions is studied. A natural approach for this problem is a continuous relaxation that extends the problem to a continuous domain and applies the algorithm in continuous DC programming. By employing a special form of continuous relaxation, which is named lin-vex extension, the produced optimal solution of the extended continuous relaxation coincides with the solution of the original discrete problem. The proposed method is demonstrated for the degree-concentrated spanning tree problem, the unfair flow problem, and the correlated knapsack problem.