Optimization Online


Multi-objective Optimization Based Algorithms for Solving Mixed Integer Linear Minimum Multiplicative Programs

Vahid Mahmoodian (Mahmoodian***at***mail.usf.edu)
Hadi Charkhgard (hcharkhgard***at***usf.edu)
Yu Zhang (yuzhang***at***usf.edu)

Abstract: We present two new algorithms for a class of single-objective non-linear optimization problems, the so-called Mixed Integer Linear minimum Multiplicative Programs (MIL-mMPs). This class of optimization problems has a desirable characteristic: a MIL-mMP can be viewed as a special case of the problem of optimization over the efficient set in multi-objective optimization. The proposed algorithms exploit this characteristic and solve any MIL-mMP from the viewpoint of multi-objective optimization. A computational study on 960 instances demonstrates that the proposed algorithms outperform a generic-purpose solver, SCIP, by a factor of more than 10 on many instances. We numerically show that selecting the best algorithm among our proposed algorithms highly depends on the class of instances used. Specifically, since one of the proposed algorithms is a decision space search algorithm and the other one is a criterion space search algorithm, one can significantly outperform the other depending on the dimension of decision space and criterion space. Although it is possible to linearize some instances of MIL-mMPs, we show that a commercial solver, CPLEX, struggles to directly solve such linearized instances because linearization introduces additional constraints and binary decision variables.

Keywords: multi-objective optimization; minimum multiplicative programming; optimization over the efficient set; decision space search algorithm; criterion space search algorithm

Category 1: Combinatorial Optimization (Branch and Cut Algorithms )

Category 2: Integer Programming ((Mixed) Integer Nonlinear Programming )

Category 3: Global Optimization



Entry Submitted: 11/15/2019
Entry Accepted: 11/18/2019
Entry Last Modified: 12/10/2020

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society