Lagrange Relaxation Method To Determine Program Solutions Number Of Chooses

Abstract

When the Integer Programming (IP) has several constraints, we need to reduce the constraints for getting feasible solution in a relative short time. One of the available methods is the Lagrange relaxation method, that reduces constraints by including complicated constraints set into the objective function as penalty with respect to the set of nice constraints. If the constraints and λ values are chosen well, it tends to be a reasonably tightest bound in finding optimal solution and solving IP quickly. The purpose of this paper is to discuss how to solve IP by using Lagrange relaxation approach, find out relation among optimal solution of Linear programming, IP and relaxation Lagrange (dual Lagrange), and understanding this method via an example.