A General Purpose Exact Solution Method for Mixed Integer Concave Minimization Problems (revised as on 12/08/2021)

Ankur Sinha, Arka Das, Guneshwar Anand and Sachin Jayaswal

IIMA Working Papers from Indian Institute of Management Ahmedabad, Research and Publication Department

Abstract: In this article, we discuss an exact algorithm for mixed integer concave minimization problems. A piece wise inner-approximation of the concave function is achieved using an auxiliary linear program that leads to a bilevel program, which provides a lower bound to the original problem. The bilevel program is reduced to a single-level formulation with the help of Karush-Kuhn-Tucker(KKT) conditions. Incorporating the KKT conditions lead to complementary slackness conditions that are linearized using BigM. Multiple bilevel programs, When solved over iterations, guarantee convergence to the exact optimum of the original problem. Though the algorithm is general and can be applied to any optimization problem with concave function(s), in this paper, we solve two common classes of operations and supply chain problems; namely, the concave knapsack problem, and the concave production transportation problem. The computational experiments indicate that our proposed approach out performs the customized methods that have been used in the literature to solve the two classes of problems by an order of magnitude in most of the test cases.

Date: 2021-03-01
New Economics Papers: this item is included in nep-isf
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.iima.ac.in/sites/default/files/rnpfiles/3946511502021-03-01.pdf English Version (application/pdf)

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:iim:iimawp:14658

Access Statistics for this paper

More papers in IIMA Working Papers from Indian Institute of Management Ahmedabad, Research and Publication Department Contact information at EDIRC.
Bibliographic data for series maintained by ().