A parallel difference-of-convex cutting plane algorithm for mixed-binary linear programs

Yi-Shuai Niu

doi:10.1080/02331934.2025.2588422

Return

A parallel difference-of-convex cutting plane algorithm for mixed-binary linear programs

2025-11-01

PRE

DOI：10.1080/02331934.2025.2588422

Original

Original request for help

Save

Abstract

En 中文

In this paper, we introduce a parallel difference-of-convex cutting plane (P-DCCUT) algorithm for solving Mixed-Binary Linear Programs (MBLP). We begin by presenting various difference-of-convex (DC) formulations for MBLP, derived from continuous formulations of integer sets and the exact penalty theorem, which can be addressed using the well-known difference-of-convex algorithm (DCA). We then explore two types of DC cuts (type-I and type-II) constructed at feasible and infeasible DC critical points generated by DCA. When these DC cuts are inapplicable, we incorporate traditional cutting plane techniques such as the Lift-and-Project (LAP) cut, Gomory's Mixed-Integer (GMI) cut, and Mixed-Integer Rounding (MIR) cut. By integrating DCA, DC cuts, and classical cutting planes within a cutting plane framework, we develop a hybrid algorithm - DCCUT - where DCA plays a pivotal role in enhancing upper bounds and generating DC cuts. A parallel version of DCCUT, called P-DCCUT, is proposed by introducing various cutting planes in parallel and multi-starting DCA with random initializations. Numerical results on several illustrative examples, as well as on the MIPLIB 2017 benchmark dataset, demonstrate the efficacy of our methods, emphasizing the important contributions of DCA and DC cuts in improving the solution bounds.

Keywords:

Mixed-binary linear program

difference-of-convex cutting plane

parallel DCCUT algorithm