A linear programming based algorithm to solve a class of optimization problems with a multi-linear objective function and affine constraints

Hadi Charkhgard

doi:10.1016/j.cor.2017.07.015

2018-01-01

PRE

Hadi Charkhgard *

Martin Savelsbergh

Masoud Talebian

DOI：10.1016/j.cor.2017.07.015

原文链接

原文求助

摘要

En 中文

We present a linear programming based algorithm for a class of optimization problems with a multi-linear objective function and affine constraints. This class of optimization problems has only one objective function, but it can also be viewed as a class of multi-objective optimization problems by decomposing its objective function. The proposed algorithm exploits this idea and solves this class of optimization problems from the viewpoint of multi-objective optimization. The algorithm computes an optimal solution when the number of variables in the multi-linear objective function is two, and an approximate solution when the number of variables is greater than two. A computational study demonstrates that when available computing time is limited the algorithm significantly outperforms well-known convex programming solvers IPOPT and CVXOPT, in terms of both efficiency and solution quality. The optimization problems in this class can be reformulated as second-order cone programs, and, therefore, also be solved by second-order cone programming solvers. This is highly effective for small and medium size instances, but we demonstrate that for large size instances with two variables in the multi-linear objective function the proposed algorithm outperforms a (commercial) second-order cone programming solver. (C) 2017 Elsevier Ltd. All rights reserved.

Keyword:

Pareto optimal solutions

Convex programming

Multi-linear objective function

Linear programming

Polynomial-time algorithm

AI总结

对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。

期刊

Computers and Operations Research

IF:

4.3

论文数:

6.5K

被引数:

1.8W

机构

State University System of Florida

学者数:

12.7W

论文数: 10.9W

被引数: 130

university system of georgia

学者数:

7.3W

论文数: 6.5W

被引数: 101

university of south florida

学者数:

1.5W

论文数: 1.2W

被引数: 9

查看更多机构

引用论文

Risk of Early-Onset Depression Associated With Polygenic Liability, Parental Psychiatric History, and Socioeconomic Status

JAMA Psychiatry

IF0

2021-04-01

OAAI

Esben Agerbo; Betina B. Trabjerg; Anders D. Børglum; Andrew J. Schork; Bjarni J. Vilhjálmsson; Carsten B. Pedersen; Christian Hakulinen; Clara Albiñana; David M. Hougaard; Jakob Grove; John J. McGrath; Jonas Bybjerg-Grauholm; Ole Mors; Oleguer Plana-Ripoll; Thomas Werge; Naomi R. Wray; Preben Bo Mortensen; Katherine L. Musliner

On finding representative non-dominated points for bi-objective integer network flow problems 关于寻找双目标整数网络流问题的代表性非支配点

COMPUTERS & OPERATIONS RESEARCH

IF4.3

2014-08-01

PREAI

Eusebio, A.; Figueira, J. R.; Ehrgott, M.

Redox behaviours and electrocatalytic properties of copper within Dawson structure-derived sandwich heteropolyanions [Cu4(H2O)2(X2W15O56)2]16− (X=P or As)

Electrochemistry Communications

IF0

2003-09-01

PREAI

Bineta Keita; Israel-Martyr Mbomekalle; Louis Nadjo