Constraint violation reduction search for 0–1 mixed integer linear programming problems. Issue 4 (3rd April 2021) - Bansal, Ankit; Uzsoy, Reha
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.