Continuous-Time Systems for Solving 0-1 Integer Linear Programming Feasibility Problems

Chengrui Li, Bruce J. MacLennanarXiv 2019 · arXiv

Abstract

The 0-1 Integer Linear Programming (ILP) feasibility problem is a foundational NP-complete challenge typically addressed through discrete search methods. This paper explores a continuous-time dynamical system approach that transforms the discrete search space into a continuous energy landscape. By employing a novel "impulse algorithm" to detect and escape local minima, the system demonstrates an efficient path to finding valid binary solutions, often outperforming traditional random-restart strategies.

Introduction

The 0-1 Integer Linear Programming (ILP) feasibility problem asks whether a set of linear constraints can be satisfied by a vector of binary variables. Given its NP-complete nature, traditional solvers like branch-and-bound face exponential worst-case complexity. Continuous-time methods, such as Hopfield networks, offer a different paradigm by treating the problem as a gradient descent toward an energy minimum. However, these systems frequently stall in "local traps"—non-solution points where the gradient vanishes. This research proposes a robust continuous-time system designed to reliably detect and navigate out of these traps.

Methodology

The proposed system relies on three pillars: problem transformation, energy function design, and a specialized impulse algorithm.

Problem Transformation and Energy Function

ILP constraints are first standardized into a non-negative coefficient form to simplify system dynamics. The authors then define a 4th-order polynomial energy function, $K(x)$, designed such that its global minimum is exactly zero. This minimum is achieved if and only if all variables are binary (0 or 1) and all linear constraints are satisfied.

The Impulse Algorithm

To prevent the system from becoming trapped in local minima, the authors introduced a "detection function" based on the ratio $\frac{dK}{K \cdot dt}$. Utilizing a "L'Hospital" trick, this ratio approaches infinity as the system nears a global solution but remains low in local traps. When a trap is detected, the system triggers an "impulse"—a calculated directional push that moves the variables back toward the interior of the 0-1 hypercube, allowing the system to resume its search from a more favorable position.

Dynamics of the continuous-time system. (a-b) Convergence to binary solutions for different problem sizes. (c-d) The impulse algorithm in action, showing variable shifts and energy spikes to escape local minima.

Experimental Results

The system was evaluated using thousands of synthetic ILP instances with variables ($N$) and constraints ($M$) ranging from 3 to 15.

Basin of Attraction and Efficiency

A key finding is that the "basin of attraction"—the set of initial conditions leading directly to a solution—is significantly larger than expected. In some instances, it was over 200 times larger than the probability of finding a solution through random discrete guessing. Furthermore, the distribution of time-to-solution was found to be heavily left-skewed, indicating that the system typically finds solutions much faster than its average performance might suggest.

Impulse vs. Random Restart

The impulse algorithm demonstrated clear superiority over standard random-restart methods. As the number of variables $N$ increased, the intelligent directional push of the impulse proved far more effective at navigating the complex energy landscape than simply resetting the system to a random state. The study also noted that higher constraint density ($M/N$) improved performance by more effectively shaping the energy landscape.

Discussion and Conclusion

While the continuous-time approach offers significant average-case speedups and a robust mechanism for escaping local traps, the authors note that the worst-case complexity remains exponential, consistent with the problem's NP-complete status. Additionally, while the basins of attraction are large, predicting their exact location based on input parameters remains an open challenge. Future work will focus on scaling these dynamics to industrial-sized problems involving thousands of variables.

Summary updated

Abstract

The 0-1 integer linear programming feasibility problem is an important NP-complete problem. This paper proposes a continuous-time dynamical system for solving that problem without getting trapped in non-solution local minima. First, the problem is transformed to an easier form in linear time. Then, we propose an "impulse algorithm" to escape from local traps and show its performance is better than randomization for escaping traps. Second, we present the time-to-solution distribution of the impulse algorithm and compare it with exhaustive search to see its advantages. Third, we show that the fractional size of the basin of attraction of the global minimum is significantly larger than $2^{-N}$, the corresponding discrete probability for exhaustive search. Finally, we conduct a case study to show that the location of the basin is independent of different dimensions. These findings reveal a better way to solve the 0-1 integer linear programming feasibility problem continuously and show that its cost could be less than discrete methods in average cases.
BibTeX
@misc{li2019continuous,
  author = {Chengrui Li and Bruce J. MacLennan},
  title = {{Continuous-Time Systems for Solving 0-1 Integer Linear Programming Feasibility Problems}},
  year = {2019},
  eprint = {1905.04612},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1905.04612},
}
Figure