Optimization Online


A Hyper-Matheuristic Methodology for Mixed Integer Linear Optimization Problems

Martín González Espinosa(martin.gonzaleze***at***umh.es)
Jose Juan López-Espín(jlopez***at***umh.es)
Juan Aparicio(j.aparicio***at***umh.es)
El-Ghazali Talbi(el-ghazali.talbi***at***univ-lille1.fr)

Abstract: Metaheuristics and exact methods are the most common tools used to solve Mixed Integer Linear Optimization Problems (MILPs). These problems are usually NP-hard problems, being intractable to obtain optimal solutions in reasonable time for large scale instances of the problem. In this work, we propose a MILP-based decomposition in which the main problem is divided in two hierarchical subproblems according to the complexity of the latter. In this paper, we investigate a decomposition separating the discrete and continuous variables, treating each subproblem with different optimization methods. A metaheuristic focuses on the discrete variable search space while the exact method takes into account the continuous variables. Hence, the metaheuristic uses an indirect representation which encode an incomplete solution for the problem, while the exact method is applied to decode the solution and generate a complete solution. The experimental results show that the solutions obtained applying the proposed MILP-based decomposition are better than those obtained solving the problem globally using a metaheuristic method. Moreover, a novel Hyper-Matheuristic scheme is introduced in which the best algorithm selection is found for a set of cooperative metaheuristics and exact optimization algorithms.

Keywords: Hyper-Matheuristic, Metaheuristics, Exact Methods, Mixed Integer Problems, MILP Decomposition.

Category 1: Integer Programming ((Mixed) Integer Linear Programming )

Category 2: Combinatorial Optimization (Meta Heuristics )

Category 3: Robust Optimization


Download: [PDF]

Entry Submitted: 08/27/2019
Entry Accepted: 08/27/2019
Entry Last Modified: 08/27/2019

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