Exact and Approximation Methods for Mixed-Integer Nonlinear Programming Problem

Amit Kumar Vatsa () and Saurabh Chandra ()
Additional contact information
Amit Kumar Vatsa: Indian Institute of Management
Saurabh Chandra: Indian Institute of Management

Chapter Chapter 13 in Optimization Essentials, 2024, pp 393-415 from Springer

Abstract: Abstract Mixed-integer nonlinear programming problems (MINLPs) are frequently observed in the real world. These problems generally require more computational effort than their counterpart mixed-integer linear programming problems (MILPs). The solvers and solution technique improvements in the last few decades have enabled us to solve MINLPs of practical sizes. This chapter presents various techniques that can be used to solve MINLPs. We divide this chapter into approximation algorithms and exact algorithms. We discuss two approximation algorithms in detail: piece-wise linearization and linearization based on the McCormick envelope. These methods can be used to obtain feasible solutions with a guarantee on bound on a wide variety of problems, including non-convex problems, which are notoriously difficult to solve with an exact method. Next, we present the exact solution methods, which are guaranteed to give an optimal solution if the algorithms are allowed to run indefinitely. These methods, such as outer approximation and generalized Benders decomposition can be applied to problems where relaxation of integrality constraint makes the problem a convex optimization problem. Some non-convex problems can be convexified using the transformation of non-convex functions. These transformations might be computationally expensive but ensure an exact solution as a trade-off. With toy examples, we demonstrate the use of exact and approximation methods on MINLPs. We also provide a real-world case study for the location-allocation of shared wastewater treatment plants and show how different methods can be used to solve that problem.

Date: 2024
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

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:isochp:978-981-99-5491-9_13

Ordering information: This item can be ordered from
http://www.springer.com/9789819954919

DOI: 10.1007/978-981-99-5491-9_13

Access Statistics for this chapter

More chapters in International Series in Operations Research & Management Science from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().