Constraint violation reduction search for 0–1 mixed integer linear programming problems. Issue 4 (3rd April 2021)

• Record Type: Journal Article
• Authors: Bansal, Ankit; Uzsoy, Reha
• Is Part Of: Engineering optimization. Volume 53:Issue 4(2021)
• Page Start: 609
• Page End: 626
• Publication Date: 2021-04-03
• Subjects: Primal heuristic -- MILP -- resource constrained project scheduling -- MIPLIB -- capacitated warehouse location; Engineering design -- Periodicals; Mathematical optimization -- Periodicals; 620.0042
• DOI: 10.1080/0305215X.2020.1742710
• Languages: English
• ISSNs: 0305-215X

Abstract

Abstract : This article presents Constraint Violation Reduction Search (CVRS), a primal heuristic for 0–1 Mixed Integer Linear Programming (MILP) problems. CVRS constructs a series of MILP subproblems by adding artificial variables representing the amount by which each constraint is violated and minimizing their sum in the objective function. A cutoff constraint added to each subproblem ensures that the objective function value of the original MILP problem improves at each iteration. If no integer feasible solution to the MILP subproblem can be found, a neighbourhood search is used to repair the infeasibility. CVRS is tested on 99 hard instances of resource constrained project scheduling, Mixed Integer Programming Library (MIPLIB) and capacitated warehouse location, and its performance is compared to a recent neighbourhood search based primal heuristic for MILP and the CPLEX ® MILP solver with promising results.