Zero-one integer programs with few constraints —Lower bounding theory

The zero-one integer programming problem and its special case, the multiconstraint knapsack problem frequently appear as subproblems in many combinatorial optimization problems. We present several methods for computing lower bounds on the optimal solution of the zero-one integer programming problem. They include Lagrangean, surrogate and composite relaxations. New heuristic procedures are suggested for determining good surrogate multipliers. Based on theoretical results and extensive computational testing, it is shown that for zero-one integer problems with few constraints surrogate relaxation is a viable alternative to the commonly used Lagrangean and linear programming relaxations. These results are used in a follow up paper to develop an efficient branch and bound algorithm for solving zero-one integer programming problems.     

A simple Tabu Search method to solve the mixed-integer linear bilevel programming problem

Multilevel programming is characterized as mathematical programming to solve decentralized planning problems. The models partition control over decision variables among ordered levels within a hierarchical planning structure of which the linear bilevel form is a special case of a multilevel programming problem. In a system with such a hierarchical structure, the high-level decision making situations generally require inclusion of zero-one variables representing ‘yes-no’ decisions. We provide a mixed-integer linear bilevel programming formulation in which zero-one decision variables are controlled by a high-level decision maker and real-value decision variables are controlled by a low-level decision maker. An algorithm based on the short term memory component of Tabu Search, called Simple Tabu Search, is developed to solve the problem, and two supplementary procedures are proposed that provide variations of the algorithm. Computational results disclose that our approach is effective in terms of both solution quality and efficiency.     

A branch and bound algorithm for mixed zero-one multiple objective linear programming

In this paper, a branch and bound algorithm for the generation of the efficient set in mixed zero-one multiple objective linear programming problems is presented. The algorithm is developed as to take account of the multiple objectives in the node fathoming procedure. In order to extend the algorithm's applicability to large sized problems from real life, an interactive procedure is introduced which systematically reduces the number of efficient points and thus saves considerable computational effort without losing essential information. The algorithm is tested in randomly generated problems along with a case study conceming the power generation sector     

A branch and bound algorithm for extreme point mathematical programming problems

This paper deals with a class of nonconvex mathematical programs called Extreme Point Mathematical Programs. This class is a generalization of zero-one integer programs and is a special case of the Generalized Lattice Point Problem, and finds applications in various areas such as production scheduling, load balancing, and concave programming. The current work existing on this class of problems is limited to certain dual types of extreme point ranking methods (which do not find a feasible solution until optimality) and some non-convergent cutting plane algorithms. No computational experience exists. This paper develops a finitely convergent branch and bound algorithm for solving the problem. The principles involved in the design of this algorithm are quite general and apply to a wider class of mathematical programs including the Generalized Lattice Point Problem. A random problem generator is described which is capable of generating problems of varying levels of difficulty. Computational experience on such problems is provided.     

A note of the knapsack problem with special ordered sets

The knapsack problem with special ordered sets and arbitrarily signed coefficients is shown to be equivalent to a standard problem of the same type but having all coefficients positive. Two propositions are proven which define an algorithm for the linear programming relaxation of the standard problem that is a natural generalization of the Dantzig solution to the problem without special ordered sets/ Several properties of the corvex hull of the associated zero-one polytope are derived.     

Convergence of a continuous approach for zero-one programming problems

In this paper a new continuous formulation for the zero-one programming problem is presented, followed by an investigation of the algorithm for it. This paper first reformulates the zero-one programming problem as an equivalent mathematical programs with complementarity constraints, then as a smooth ordinary nonlinear programming problem with the help of the Fischer-Burmeister function. After that the augmented Lagrangian method is introduced to solve the resulting continuous problem, with optimality conditions for the non-smooth augmented Lagrangian problem derived on the basis of approximate smooth variational principle, and with convergence properties established. To our benefit, the sequence of solutions generated converges to feasible solutions of the original problem, which provides a necessary basis for the convergence results.     

The zero-one knapsack problem with equality constraint

The zero-one knapsack problem is a linear zero-one programming problem with a single inequality constraint. This problem has been extensively studied and many applications and efficient algorithms have been published. In this paper we consider a similar problem, one with an equality instead of the inequality constraint. By replacing the equality by two inequalities one of which is placed in the economic function, a Lagrangean relaxation of the problem is obtained. The relation between the relaxed problem and the original problem is examined and it is shown how the optimal value of the relaxed problem varies with increasing values of the Lagrangean multiplier. Using these results an algorithm for solving the problem is proposed.The paper concludes with a discussion of computational experience.     

Special ordered sets and an application to gas supply operations planning

Special Ordered Sets provide a powerful means of modeling nonconvex functions and discrete requirements, though there has been a tendency to think of them only in terms of multiple-choice zero-one programming. This paper emphasizes the origins and generality of the special ordered set concept, and describes an application in which type 2 sets are used in several forms to model both logical conditions and nonlinear functions.Now at IBM Almaden Research Center, San Jose, CA 95120.     

Optimization of Electrical Energy Distribution for a Deficient System

An optimization algorithm for energy distribution in an isolated electrical power system that exhibits energy shortages for relatively long periods of time is introduced in this paper. The algorithm periodically revises the expected demand and the generation capacity to determine the electrical deficit. The objective is to minimize the total load of a select group of circuits to be interrupted, such that their loads most nearly approximate the electrical deficit. A probability model is used to characterize whether or not a circuit is available for being interrupted. The methodology also provides a recommended running overhead capacity and an interruption length for a given deficit condition. The state of each circuit in a given electrical system is defined as a pure binary variable and an optimal solution is found within the framework of the zero-one implicit enumeration algorithm.     

A new approach based on the surrogating method in the project time compression problems

This paper develops a mathematical model for project time compression problems in CPM/PERT type networks. It is noted this formulation of the problem will be an adequate approximation for solving the time compression problem with any continuous and non-increasing time-cost curve. The kind of this model is Mixed Integer Linear Program (MILP) with zero-one variables, and the Benders' decomposition procedure for analyzing this model has been developed. Then this paper proposes a new approach based on the surrogating method for solving these problems. In addition, the required computer programs have been prepared by the author to execute the algorithm. An illustrative example solved by the new algorithm, and two methods are compared by several numerical examples. Computational experience with these data shows the superiority of the new approach.     

Zero-one programming with many variables and few constraints

One of the more successful techniques for solving zero-one integer programs has been the implicit enumeration strategy first introduced by E. Balas. However, experience has shown that the efficiency of these enumerative techniques depends critically upon the bumber of variables. In this paper an algorithm is developed and computational experience provided for solving zero-one integer programs with many variables and few constraints. Sub-problems solved via implicit enumeration are generated from the linear programming relaxation and the variables in these sub-problems correspond to the fractional variables obtained in the linear program. Since the number of fractional variables in the linear program is bounded by the number of constraints in the linear program, the sub-problems will in general contain many fewer variables than the original zero-one integer program.     

Definition of extraction files and their optimization by zero-one programming

In commercial and administrative ADP it often happens that there is one large master file and many output files are to be made from this. One possible solution to avoid using the master file many times is to construct from it a few extraction files and from these compile the output files. In the following paper a method is described to define the extraction files and to optimize their contents by zero-one programming. An algorithm and an example are presented in a simplified case.     

A finitely convergent procedure for facial disjunctive programs

This paper addresses an important class of disjunctive programs called facial disjunctive programs, examples of which include the zero-one linear integer programming problem and the linear complementarity problem. Balas has characterized some fundamental properties of such problems, one of which has been used by Jeroslow to obtain a finitely convergent procedure. This paper exploits another basic property of facial disjunctive programs in order to develop an alternative finitely convergent algorithm.     

A Zero-One Goal-Programming Algorithm Using Partitioning and Constraint Aggregation

This paper offers a new approach to the solution of zero-one goal-programming problems. The number of non-zero variables required to satisfy a constraint completely is used to identify the priority levels that can be completely achieved, and also determine redundant constraints and invariant decision-variables. The priority levels that are so identified form the basis for a subprogramme of completely achievable constraints. These constraints are aggregated to form a single constraint, and a set of necessary and sufficient conditions are developed to generate the optimal solution. The algorithm has been coded in Pascal and compared with the Lee and Morris algorithm. The virtual CPU time required to solve those problems tested was less than 10 per cent of that required by the Lee and Morris algorithm. The algorithm may also be useful in solving other types of zero-one formulations.     

The flow shop problem with time lags and separated setup times

This paper generalizes Khurana-Bagga's flow-shop model which involves separated setup times and time lags where no restrictions are imposed on the processing and setup times as well as start and stop lags. It solves the two machine case and provides and approximate solution for the multimachine case. It also shows that Khurana-Bagga's algorithm is restricted to a special case of the two machine problem.     

A Method for Single Facility Multiple Products Scheduling

The single facility multiple products scheduling problem is formulated into a multiperiod mathematical programming model with zero-one variables. An algorithm to solve the scheduling problem by using the concept of state vectors of dynamic programming is described. An example of application of the model and the algorithm is also presented. It has been found that a suitable selection of a state vector reduces greatly the dimensionality of the problem     

A continuous approch for globally solving linearly constrained quadratic

In a continuous approach we propose an efficient method for globally solving linearly constrained quadratic zero-one programming considered as a d.c. (difference of onvex functions) program. A combination of the d.c. optimization algorithm (DCA) which has a finite convergence, and the branch-and-bound scheme was studied. We use rectangular bisection in the branching procedure while the bounding one proceeded by applying d.c.algorithms from a current best feasible point (for the upper bound) and by minimizing a well tightened convex underestimation of the objective function on the current subdivided domain (for the lower bound). DCA generates a sequence of points in the vertex set of a new polytope containing the feasible domain of the problem being considered. Moreover if an iterate is integral then all following iterates are integral too.Our combined algorithm converges so quite often to an integer approximate solution.Finally, we present computational results of several test problems with up to 1800

variables which prove the efficiency of our method, in particular, for linear zero-one programming     

一类特殊二维0-1规划的广义指派模型求解

二维0-1整数规划模型应用广泛,对广义指派问题的研究,解决了一些二维0-1整数规划问题.但有些实际问题具有特殊上限约束,目前还没有对应的方法.针对该实际情形,本文建立了相应的数学模型,利用对指派模型的推广,求得问题最优解,从理论上解决了这一类特殊约束二维0-1整数规划的最优解求取问题.并通过算例说明了方法的使用.     

A linear mixed-integer model for a purchasing problem involving discount structures

In a recent paper a quadratic mixed-integer programming model was presented for an industrial purchasing problem involving complicated discount structures. The solution method presented in the paper for this model involved the solution of a series of quadratic zero-one programming problems. The disadvantages of such an approach are immediately obvious to anyone familiar with the state-of-the-art of solution methods for nonlinear integer programming problems. In this paper a linear model is constructed for the same problem and its computational advantages over the nonlinear model are discussed.