Automatic decomposition of mixed integer programs for Lagrangian relaxation using a multiobjective approach

Jake Weiner, Andreas Ernst, Xiaodong Li, Yuan Sun

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review


This paper presents a new method to automatically decompose general Mixed Integer Programs (MIPs). To do so, we represent the constraint matrix for a general MIP problem as a hypergraph and relax constraints by removing hyperedges from the hypergraph. A Breadth First Search algorithm is used to identify the individual partitions that now exist and the resulting decomposed problem. We propose that good decompositions have both a small number of constraints relaxed and small subproblems in terms of the number of variables they contain. We use the multiobjective Nondominated Sorting Genetic Algorithm II (NSGA-II) to create decompositions which minimize both the size of the subproblems and the number of constraints relaxed. We show through our experiments the types of decompositions our approach generates and test empirically the effectiveness of these decompositions in producing bounds when used in a Lagrangian Relaxation framework. The results demonstrate that the bounds generated by our decompositions are significantly better than those attained by solving the Linear Programming relaxation, as well as the bounds found via random and greedy constraint relaxation and decomposition generation.

Original languageEnglish
Title of host publicationProceedings of the 2020 Genetic and Evolutionary Computation Conference
EditorsCarlos A Coello
Place of PublicationNew York NY USA
PublisherAssociation for Computing Machinery (ACM)
Number of pages8
ISBN (Electronic)9781450371285
Publication statusPublished - 25 Jun 2020
EventGenetic and Evolutionary Computation Conference, 2020 - Cancun, Mexico
Duration: 8 Jul 202012 Jul 2020


ConferenceGenetic and Evolutionary Computation Conference, 2020
Abbreviated titleGECCO 2020
OtherThe Genetic and Evolutionary Computation Conference (GECCO) presents the latest high-quality results in genetic and evolutionary computation since 1999. Topics include: genetic algorithms, genetic programming, ant colony optimization and swarm intelligence, complex systems (artificial life/robotics/evolvable hardware/generative and developmental systems/artificial immune systems), digital entertainment technologies and arts, evolutionary combinatorial optimization and metaheuristics, evolutionary machine learning, evolutionary multiobjective optimization, evolutionary numerical optimization, real world applications, search-based software engineering, theory and more.
Internet address


  • Combinatorial optimization
  • Heuristics
  • Multi-objective optimization

Cite this