https://www.mdu.se/

mdu.sePublications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
A symbiosis between population based incremental learning and LP-relaxation based parallel genetic algorithm for solving integer linear programming models
GC Shahid Beheshti Univ, Fac Math Sci, Dept Data & Comp Sci, Tehran, Iran.
GC Shahid Beheshti Univ, Fac Math Sci, Dept Data & Comp Sci, Tehran, Iran.
Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems.
(English)In: Computing, ISSN 0010-485X, E-ISSN 1436-5057Article in journal (Refereed) Epub ahead of print
Abstract [en]

Solving Integer Linear Programming (ILP) models generally lies in the category of NP-hard problems and finding the optimal answer for large models is a computational challenge. Genetic algorithms are a family of metaheuristic algorithms capable of adjusting and redesigning parameters and operations according to the characteristics of ILP models. On the other hand, still the genetic algorithm performs a lot of operations to solve large models, and parallel processing is a suitable technique to tackle this problem. This paper introduces an LP-Relaxation based parallel genetic algorithm that uses a population-based incremental learning technique to presents an expandable solver for large ILP models derived from a behavioral synthesis of digital circuits. In the proposed algorithm, each chromosome provides a state subspace of possible solutions, and each generation is produced based on a probability vector as well as elitism. Our experiments verify the efficiency of the proposed algorithm on multicore platforms, as it outperformed four previous genetic algorithms for solving mixed integer programming problems. The proposed genetic algorithm solved 20 ILP models include up to 5183 int / binary decision variables in less than 20 min using four 16-core AMD Opteron 6386 SE processors. Also, the results indicate that for models with more than 4000 variables, the speedup and the efficiency of the proposed parallel genetic algorithm on 60 CPU cores is more than 18X and 30%, respectively.

National Category
Computer Sciences
Identifiers
URN: urn:nbn:se:mdh:diva-55892DOI: 10.1007/s00607-021-01004-xISI: 000692679100001Scopus ID: 2-s2.0-85114143471OAI: oai:DiVA.org:mdh-55892DiVA, id: diva2:1594887
Available from: 2021-09-16 Created: 2021-09-16 Last updated: 2023-05-24Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full textScopus

Authority records

Daneshtalab, Masoud

Search in DiVA

By author/editor
Daneshtalab, Masoud
By organisation
Embedded Systems
In the same journal
Computing
Computer Sciences

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 38 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf