An Algorithm for Solving a Class of Pseudo-Boolean Equations
Abstract
A new algorithm named the Overall Algorithm applicable to a 0-1 variable (Pseudo-Boolean) system of equations with an objective function and a set of inequality constraints. The objective equation can be linear or non-linear. The set of constraints must be either all linear or all non-linear independent of the objective function. The Overall Algorithm first solves the objective function and checks the set of constraints for feasibility. If the solution is feasible then the algorithm stops. If the solution is not feasible then the Overall Algorithm moves to the set of constraints and solves the set of constraints for a feasible solution. If there is a solution to the constraints then the Overall Algorithm creates bounds for the optimal solution. This is conjectured through application to 48 previously published problems that are listed in the thesis. The Overall Algorithm is significant because it is an alternative method for the solution of Pseudo-Boolean systems of equations or models. It is a simple algorithm that, based on computational experience, has been shown to be surprisingly accurate. Finally, the most iterations required for this algorithm is n, where n is the number of variables.
Document Details
- Document Type
- Technical Report
- Publication Date
- Feb 25, 1991
- Accession Number
- ADA236023
Entities
People
- Kevin J. Loy