Analysis and Solving SAT and MAX-SAT Problems Using an L-partition Approach

In this paper, we study SAT and MAX-SAT using the integer linear programming models and L-partition approach. This approach can be applied to analyze and solve many discrete optimization problems including location, covering, scheduling problems. We describe examples of SAT and MAX-SAT families for which the cardinality of L-covering of the relaxation polytope grows exponentially with the number of variables. These properties are useful in analysis and development of algorithms based on the linear relaxation of the problems. Besides we present the L-class enumeration algorithm for SAT using the L-partition approach. In addition we consider an application of this algorithm to construct exact algorithm and local search algorithms for the MAX-SAT problem.     

Bus driver duty optimization using an integer programming and evolutionary hybrid algorithm

This paper describes the details of a successful application where an integer programming and evolutionary hybrid algorithm was used to solve a bus driver duty optimization problem. The task is NP-hard, therefore theoretically optimal solutions can only be calculated for very small problem instances. Our aim is to obtain solutions of good quality within reasonable time limits. We first applied an integer programming approach to a set partitioning problem. The model was solved with a column generation algorithm in a branch and bound scheme. In order to solve larger real-life problems, we have combined the integer programming method with a greedy 1+1 steady state evolutionary algorithm. The resulting hybrid algorithm was capable of providing near-optimal solutions within reasonable timescales to larger instances of the bus driver scheduling problem. We present the results and running times of our algorithm in detail, as well as possible directions of future improvements.     

Scatter Search and Genetic Algorithms for MAX-SAT Problems

In this paper, both scatter search (SS) and genetic algorithms (GAs) are studied for the NP-Hard optimization variant of the satisfiability problem, namely MAX-SAT. First, we investigate a new selection strategy based on both fitness and diversity to choose individuals to participate in the reproduction phase of a genetic algorithm. The resulting algorithm is enhanced in two ways leading to two genetic algorithm variants: the first one uses a uniform crossover. The second one uses a specific crossover operator (to MAX-SAT). The crossover operator is combined with an improved stochastic local search (SLS). The crossover operator is used to identify promising regions while the stochastic local search performs an intensified search of solutions around these regions. Secondly, we propose a scatter search variant for MAX-SAT. Both the SS and the GAs implementations share the solution selection strategy, the improved SLS method and the combination operator. Experiments on several instances from MAX-SAT libraries are performed to show and compare the effectiveness of our approaches. The computational experiments show that both (SS) and (GAs) with a stochastic local search (SLS) improvement technique outperform a classical genetic algorithm (without SLS). The two metaheuristics are able of balancing search diversification and intensification which leads to good results. In general, the specific genetic algorithm with a (SLS) improvement technique and a specific combination method provides competitive results and finds solutions of a higher quality than a scatter search.     

The complete parsimony haplotype inference problem and algorithms based on integer programming,branch-and-bound and Boolean satisfiability

Haplotype inference by pure parsimony (Hipp) is a well-known paradigm for haplotype inference. In order to assess the biological significance of this paradigm, we generalize the problem of Hipp to the problem of finding all optimal solutions, which we call Chipp. We study intrinsic haplotype features, such as backbone haplotypes and fat genotypes as well as equal columns and decomposability. We explicitly exploit these features in three computational approaches that are based on integer linear programming, depth-first branch-and-bound, and Boolean satisfiability. Further we introduce two hybrid algorithms that draw upon the diverse strengths of the approaches. Our experimental analysis shows that our optimized algorithms are significantly superior to the baseline algorithms, often with orders of magnitude faster running time. Finally, our experiments provide some useful insights into the intrinsic features of this important problem.     

Computational experience with an interior point algorithm on the satisfiability problem

We apply the zero-one integer programming algorithm described in Karmarkar [12] and Karmarkar, Resende and Ramakrishnan [13] to solve randomly generated instances of the satisfiability problem (SAT). The interior point algorithm is briefly reviewed and shown to be easily adapted to solve large instances of SAT. Hundreds of instances of SAT (having from 100 to 1000 variables and 100 to 32,000 clauses) are randomly generated and solved. For comparison, we attempt to solve the problems via linear programming relaxation with MINOS.     

Sums of squares based approximation algorithms for MAX-SAT

We investigate the Semidefinite Programming based sums of squares (SOS) decomposition method, designed for global optimization of polynomials, in the context of the (Maximum) Satisfiability problem. To be specific, we examine the potential of this theory for providing tests for unsatisfiability and providing MAX-SAT upper bounds. We compare the SOS approach with existing upper bound and rounding techniques for the MAX-2-SAT case of Goemans and Williamson [Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming, J. Assoc. Comput. Mach. 42(6) (1995) 1115-1145] and Feige and Goemans [Approximating the value of two prover proof systems, with applications to MAX2SAT and MAXDICUT, in: Proceedings of the Third Israel Symposium on Theory of Computing and Systems, 1995, pp. 182-189] and the MAX-3-SAT case of Karloff and Zwick [A 7/8-approximation algorithm for MAX 3SAT? in: Proceedings of the 38th Annual IEEE Symposium on Foundations of Computer Science, Miami Beach, FL, USA, IEEE Press, New York, 1997], which are based on Semidefinite Programming as well. We prove that for each of these algorithms there is an SOS-based counterpart which provides upper bounds at least as tight, but observably tighter in particular cases. Also, we propose a new randomized rounding technique based on the optimal solution of the SOS Semidefinite Program (SDP) which we experimentally compare with the appropriate existing rounding techniques. Further we investigate the implications to the decision variant SAT and compare experimental results with those yielded from the higher lifting approach of Anjos [On semidefinite programming relaxations for the satisfiability problem, Math. Methods Oper. Res. 60(3) (2004) 349-367; An improved semidefinite programming relaxation for the satisfiability problem, Math. Programming 102(3) (2005) 589-608; Semidefinite optimization approaches for satisfiability and maximum-satisfiability problems, J. Satisfiability Boolean Modeling Comput. 1 (2005) 1-47].We give some impression of the fraction of the so-called unit constraints in the various SDP relaxations. From a mathematical viewpoint these constraints should be easily dealt within an algorithmic setting, but seem hard to be avoided as extra constraints in an SDP setting. Finally, we briefly indicate whether this work could have implications in finding counterexamples to uncovered cases in Hilbert's Positivstellensatz.     

Progressive Basic Decision CPM

PERT and CPM are two valuable tools for the planning, scheduling and controllingof projects, but they do not on their own deal with the interdependence between planning resource utilization or direct cost expenditure and sclheduling with its overhead cost (penalty cost and/or reward bonus) implications. Several approaches to overcome this deficiency are possible, this paper dealing with one known as Decision CPM. The most recent approach to the Decision CPM problem known to the authors leads to relatively large integer programming problems which are solved as such. This paper considers a restricted formulation of the Decision CPM problem in an integer programming framework, and shows how it may be solved relatively easily witlhout resort to integer programming methods. Extensions of the restricted model are also considered briefly, some of which pose no difficulties, while others suggest the need for a hybrid of other approaches and that described here.     

Constraint Programming and Hybrid Formulations for Three Life Designs

Conway's game of Life provides an interesting testbed for exploring issues in formulation, symmetry, and optimization with constraint programming and hybrid constraint programming/integer programming methods. We consider three Life pattern-creation problems: finding maximum density still-Lifes, finding smallest immediate predecessor patterns, and finding period-2 oscillators. For the first two problems, integrating integer programming and constraint programming approaches provides a much better solution procedure than either individually. For the final problem, the constraint programming formulation provides the better approach.     

New convergent heuristics for 0–1 mixed integer programming

Several hybrid methods have recently been proposed for solving 0–1 mixed integer programming problems. Some of these methods are based on the complete exploration of small neighborhoods. In this paper, we present several convergent algorithms that solve a series of small sub-problems generated by exploiting information obtained from a series of relaxations. These algorithms generate a sequence of upper bounds and a sequence of lower bounds around the optimal value. First, the principle of a linear programming-based algorithm is summarized, and several enhancements of this algorithm are presented. Next, new hybrid heuristics that use linear programming and/or mixed integer programming relaxations are proposed. The mixed integer programming (MIP) relaxation diversifies the search process and introduces new constraints in the problem. This MIP relaxation also helps to reduce the gap between the final upper bound and lower bound. Our algorithms improved 14 best-known solutions from a set of 108 available and correlated instances of the 0–1 multidimensional Knapsack problem. Other encouraging results obtained for 0–1 MIP problems are also presented.     

NONLINEAR INTEGER PROGRAMMING AND GLOBALOPTIMIZATION

1.IntroductionAlthoughthegenerallinearintegerprogrammingproblemisNP-hard,muchworkhasbeendevotedtoit(SeeNumhauserandWolsey[1988],Schrijver[1986]).Thesolutionmethodsincludethecuttingplane,theBranch-and-Bound,thedynamicprogrammingmethodsetc..However,thegeneralnonlinearintegerprogrammingproblemisdifficulttosolve.GareyandJohnson[1979]pointedoutthattheintegerprogrammingoverRewithalinearobjectivefunctionandquadraticconstraintsisundecidable.Soifanonlinearintegerprogrammingproblemishandled,itisalw…     

A partitioning algorithm for the network loading problem

This paper proposes a Benders-like partitioning algorithm to solve the network loading problem. The approach is an iterative method in which the integer programming solver is not used to produce the best integer point in the polyhedral relaxation of the set of feasible capacities. Rather, it selects an integer solution that is closest to the best known integer solution. Contrary to previous approaches, the method does not exploit the original mixed integer programming formulation of the problem. The effort of computing integer solutions is entirely left to a pure integer programming solver while valid inequalities are generated by solving standard nonlinear multicommodity flow problems. The method is compared to alternative approaches proposed in the literature and appears to be efficient for computing good upper bounds.     

Formulation of linear problems and solution by a universal machine

Using the predicate language for ordered fields a class of problems referred to aslinear problems is defined. This class contains, for example, all systems of linear equations and inequalities, all linear programming problems, all integer programming problems with bounded variables, all linear complementarity problems, the testing of whether sets that are defined by linear inequalities are semilattices, all satisfiability problems in sentenial logic, the rank-computation of matrices, the computation of row-reduced echelon forms of matrices, and all quadratic programming problems with bounded variables. A single, one, algorithm, to which we refer as theUniversal Linear Machine, is described. It solves any instance of any linear problem. The Universal Linear Machine runs in two phases. Given a linear problem, in the first phase a Compiler running on a Turing Machine generates alinear algorithm for the problem. Then, given an instance of the linear problem, in the second phase the linear algorithm solves the particular instance of the linear problem. The linear algorithm is finite, deterministic, loopless and executes only the five ordered field operations — additions, multiplications, subtractions, divisions and comparisons. Conversely, we show that for each linear algorithm there is a linear problem which the linear algorithm solves uniquely. Finally, it is shown that with a linear algorithm for a linear problem, one can solve certain parametric instances of the linear problem.Research was supported in part by the National Science Foundation Grant DMS 92-07409, by the Department of Energy Grant DE-FG03-87-ER-25028, by the United States—Israel Binational Science Foundation Grant 90-00434 and by ONR Grant N00014-92-J1142.Corresponding author.     

A simplex social spider algorithm for solving integer programming and minimax problems

In this paper, we propose a new hybrid social spider algorithm with simplex Nelder-Mead method in order to solve integer programming and minimax problems. We call the proposed algorithm a Simplex Social Spider optimization (SSSO) algorithm. In the the proposed SSSO algorithm, we combine the social spider algorithm with its powerful capability of performing exploration, exploitation, and the Nelder-Mead method in order to refine the best obtained solution from the standard social spider algorithm. In order to investigate the general performance of the proposed SSSO algorithm, we test it on 7 integer programming problems and 10 minimax problems and compare against 10 algorithms for solving integer programming problems and 9 algorithms for solving minimax problems. The experiments results show the efficiency of the proposed algorithm and its ability to solve integer and minimax optimization problems in reasonable time.     

An approach to the modeling and analysis of multiobjective generalized networks

Generalized networks can often provide substantial advantages in both the modeling and solution of integer programming problems. In this paper we present a straightforward approach which combines generalized networks with goal programming so as to achieve a modeling and solution methodology for multiobjective generalized networks. Such an approach also encompasses the solution to weighted integer foal programming as well as lexicographic integer goal programming problems. In ongoing research, the resulting hybrid algorithms have indicated superior performance, for a number of problems, over that obtained by more conventional approaches. A particularly attractive feature of the methodology is its relative simplicity and robustness.     

A genetic algorithm solution for one-dimensional bundled stock cutting

This paper discusses a one-dimensional cutting stock problem in which lumber is cut in bundles. The nature of this problem is such that the traditional approaches of linear programming with an integer round-up procedure or sequential heuristics are not effective. A good solution to this problem must consider trim loss, stock usage and ending inventory levels. A genetic search algorithm is proposed and results compared to optimal solutions for an integer programming formulation of the problem.     

Branch-and-Price Algorithms for the One-Dimensional Cutting Stock Problem

We compare two branch-and-price approaches for the cutting stock problem. Each algorithm is based on a different integer programming formulation of the column generation master problem. One formulation results in a master problem with 0–1 integer variables while the other has general integer variables. Both algorithms employ column generation for solving LP relaxations at each node of a branch-and-bound tree to obtain optimal integer solutions. These different formulations yield the same column generation subproblem, but require different branch-and-bound approaches. Computational results for both real and randomly generated test problems are presented.     

Solving the weighted MAX-SAT problem using the dynamic convexized method

Satisfiability (SAT) and maximum satisfiability (MAX-SAT) are difficult combinatorial problems that have many important real-world applications. In this paper we investigate the performance of the dynamic convexized method based heuristics on the weighted MAX-SAT problem. We first present an auxiliary function which is constructed based on a penalty function, and minimize the function by a local search method which can escape successfully from previously converged local minimizers by increasing the value of a parameter. Two algorithms of the approach are implemented and compared with the Greedy Randomized Adaptive Search Procedure (GRASP) and the GRASP with Path Relinking (GRASP + PR). Experimental results illustrate efficient and faster convergence of our two algorithms.     

Column enumeration based decomposition techniques for a class of non-convex MINLP problems

We propose a decomposition algorithm for a special class of nonconvex mixed integer nonlinear programming problems which have an assignment constraint. If the assignment decisions are decoupled from the remaining constraints of the optimization problem, we propose to use a column enumeration approach. The master problem is a partitioning problem whose objective function coefficients are computed via subproblems. These problems can be linear, mixed integer linear, (non-)convex nonlinear, or mixed integer nonlinear. However, the important property of the subproblems is that we can compute their exact global optimum quickly. The proposed technique will be illustrated solving a cutting problem with optimum nonlinear programming subproblems.     

Solving Fixed-Charge Network Flow Problems with a Hybrid Optimization and Constraint Programming Approach

We apply to fixed charge network flow (FCNF) problems a general hybrid solution method that combines constraint programming and linear programming. FCNF problems test the hybrid approach on problems that are already rather well suited for a classical 0–1 model. They are solved by means of a global constraint that generates specialized constraint propagation algorithms and a projected relaxation that can be rapidly solved as a minimum cost network flow problem. The hybrid approach ran about twice as fast as a commercial mixed integer programming code on fixed charge transportation problems with its advantage increasing with problem size. For general fixed charge transshipment problems, however, it has no effect because the implemented propagation methods are weak.     

Discrete and geometric Branch and Bound algorithms for?medical image registration

Aiming at the development of an exact solution method for registration problems, we present two different Branch & Bound algorithms for a mixed integer programming formulation of the problem. The first B&B algorithm branches on binary assignment variables and makes use of an optimality condition that is derived from a graph matching formulation. The second, geometric B&B algorithm applies a geometric branching strategy on continuous transformation variables. The two approaches are compared for synthetic test examples as well as for 2-dimensional medical data. The results show that medium sized problem instances can be solved to global optimality in a reasonable amount of time.