Optimality results of submodular programming problems
Optimization Eruditorum, Volume 4, Issue 1, April 2027, Pages 53–61
J. Dasmahapatra
Department of Mathematics, Veer Surendra Sai University of Technology Burla, Sambalpur 768018, India
A. Pattnaik
Department of Mathematics, Veer Surendra Sai University of Technology Burla, Sambalpur 768018, India
S. K. Padhan
Department of Mathematics, Veer Surendra Sai University of Technology Burla, Sambalpur 768018, India
C. Nahak
Department of Mathematics, Indian Institute of Technology Kharagpur, Kharagpur 721302, India
Abstract
Submodular functions have emerged as a class of set functions that model the law of diminishing returns in discrete functions. These functions have primarily been applied in discrete optimization problems because they can be minimized exactly and maximized approximately. The present investigation has considered both unconstrained and constrained minimization programming problems involving submodular set functions. It has been observed that the submodular minimization problems has an optimal solution if and only if its Lagrangian has a saddle point. Furthermore, the necessary and sufficient optimality conditions for submodular minimization programs with inequality constraints have been derived, which constitute the discrete analogue of the Karush–Kuhn–Tucker (KKT) conditions for convex programming problems.
Cite this Article as
J. Dasmahapatra, A. Pattnaik, S. K. Padhan, and C. Nahak, Optimality results of submodular programming problems, Optimization Eruditorum, 4(1), 53–61, 2027