A Branch-and-Bound Algorithm for a Class of Mixed Integer Linear Maximum Multiplicative Programs: A Bi-objective Optimization Approach. (January 2019)

• Record Type: Journal Article
• Authors: Ghasemi Saghand, Payman; Charkhgard, Hadi; Kwon, Changhyun
• Is Part Of: Computers & operations research. Volume 101(2019)
• Page Start: 263
• Page End: 274
• Publication Date: 2019-01
• Subjects: Multiplicative programming -- Multi-objective optimization -- Optimization over the efficient set -- Linear programming -- Branch-and-bound algorithm; Operations research -- Periodicals; Electronic digital computers -- Periodicals; 004.05
• DOI: 10.1016/j.cor.2018.08.004
• Languages: English
• ISSNs: 0305-0548

Abstract

Highlights: We study a class of mixed integer non-linear optimization problems. We develop a novel branch-and-bound algorithm. We show that the proposed algorithm outperforms a standard solver. Abstract: We present a linear programming based branch-and-bound algorithm for a class of mixed integer optimization problems with a bi-linear objective function and linear constraints. This class of optimization problems can be viewed as a special case of the problem of optimization over the set of efficient solutions in bi-objective optimization. It is known that when there exists no integer decision variable, such a problem can be solved in polynomial time. In fact, in such a case, the problem can be transformed into a Second-Order Cone Program (SOCP) and so it can be solved efficiently by a commercial solver such as CPLEX SOCP solver. However, in a recent study, it is shown that such a problem can be solved even faster in practice by using a bi-objective linear programming based algorithm. So, in this study, we embed that algorithm in an effective branch-and-bound framework to solve mixed integer instances. We also develop several enhancement techniques including preprocessing and cuts. A computational study demonstrates that the proposed branch-and-bound algorithm outperforms a commercial mixed integer SOCP solver. Moreover, the effect of different branching and node selecting strategies is explored.