-

 

 

 




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

Citation:

Download: [PDF]

Entry Submitted: 11/15/2019
Entry Accepted: 11/18/2019
Entry Last Modified: 11/15/2019

Modify/Update this entry


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

 

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