A Feasibility-Ensured Lagrangian Heuristic for General Decomposable Problems

Kouhei Harada ()
Additional contact information
Kouhei Harada: NTTDATA Mathematical Systems Inc.

SN Operations Research Forum, 2021, vol. 2, issue 4, 1-26

Abstract: Abstract The Lagrangian relaxation method is a popular and useful tool to solve large-scale optimization problems with decomposable structures. A drawback of this approach is that a primal solution obtained by solving the Lagrangian relaxation problem is often primal infeasible even if an optimal dual solution is given. To recover primal feasibility, we rely on specialized heuristic-based approaches, each of which is tailored for a particular optimization problem. To overcome the difficulty, a general heuristic method has been proposed recently. The method ensures primal feasibility, but it is not tailored for some particular optimization problems. Furthermore, the method can estimate the gap of the objective between an optimal solution and the feasible solution obtained using the heuristic. Although the method provides important results, it relies on the assumption that both objective and constraint functions are concave. We generalize the results: the method ensures primal feasibility for a rather general class of problems. We have demonstrated that the fundamentally important requirement here is the extremity of the solution set of the Lagrangian relaxation problem. Our numerical experiments support the efficiency and validity of our generalized results.

Keywords: Convexification; Decomposable problem; Extreme point; Lagrangian heuristic; Lagrangian relaxation; Primal feasibility; 90C22; 90C25 (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s43069-021-00094-9 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:snopef:v:2:y:2021:i:4:d:10.1007_s43069-021-00094-9

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/43069

DOI: 10.1007/s43069-021-00094-9

Access Statistics for this article

SN Operations Research Forum is currently edited by Marco Lübbecke

More articles in SN Operations Research Forum from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().