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 @math , 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.
The paper presents a survey of methods and approaches solving linear integer problems, developed during the last 50 years. These problems belong to the class of NP-hard optimization problems. To find out exact optimal solutions for this class of problems requires use of considerable computational resources. The development of efficient hybrid methods, combining in a suitable way the best features of different approaches (exact or approximate) is the actual direction, in which many researchers devote their efforts to solve successfully varioushard practical problems. Author(s): Impagliazzo, R; Lovett, S; Paturi, R; Schneider, S | Abstract: We give an exact algorithm for the 0-1 Integer Linear Programming problem with a linear number of constraints that improves over exhaustive search by an exponential factor. Specifically, our algorithm runs in time @math where n is the number of variables and cn is the number of constraints. The key idea for the algorithm is a reduction to the Vector Domination problem and a new algorithm for that subproblem.  In this work, we study continuous reformulations of zero–one programming problems. We prove that, under suitable conditions, the optimal solutions of a zero–one programming problem can be obtained by solving a specific continuous problem.  This paper reviews the advances of mixed-integer linear programming (MILP) based approaches for the scheduling of chemical processing systems. We focus on the short-term scheduling of general network represented processes. First, the various mathematical models that have been proposed in the literature are classified mainly based on the time representation. Discrete-time and continuous-time models are presented along with their strengths and limitations. Several classes of approaches for improving the computational efficiency in the solution of MILP problems are discussed. Furthermore, a summary of computational experiences and applications is provided. The paper concludes with perspectives on future research directions for MILP based process scheduling technologies. The design of feedback (or recurrent) neural networks to produce good solutions to complex optimization problems is discussed. The theoretical basis for applying neural networks to optimization problems is reviewed, and a design rule that serves as a primitive for constructing a wide class of constraints is introduced. The use of the design rule is illustrated by developing a neural network for producing high-quality solutions to a probabilistic resource allocation task. The resulting neural network has been simulated on a high-performance parallel processor that has been optimized for neural network simulation. >