The reformulation of two mixed integer programming problems

Two practical problems are described, each of which can be formulated in more than one way as a mixed integer programming problem. The computational experience with two formulations of each problem is given. It is pointed out how in each case a reformulation results in the associated linear programming problem being more constrained. As a result the reformulated mixed integer problem is easier to solve. The problems are a multi-period blending problem and a mining investment problem.     

Constrained integer linear fractional programming problem

An integer linear fractional programming problem, whose integer solution is required to satisfy any h out of given n sets of constraints has been discussed in this paper. Method for ranking and scanning all integer points has also been developed and a numerical illustration is included in support of theory.     

Multicriteria integer programming: A (hybrid) dynamic programming recursive approach

Dynamic programming recursive equations are used to develop a procedure to obtain the set of efficient solutions to the multicriteria integer linear programming problem. An alternate method is produced by combining this procedure with branch and bound rules. Computational results are reported.     

An improved partial enumeration algorithm for integer programming problems

In this paper, we present an improved Partial Enumeration Algorithm for Integer Programming Problems by developing a special algorithm, named PE_SPEEDUP (partial enumeration speedup), to use whatever explicit linear constraints are present to speedup the search for a solution. The method is easy to understand and implement, yet very effective in dealing with many integer programming problems, including knapsack problems, reliability optimization, and spare allocation problems. The algorithm is based on monotonicity properties of the problem functions, and uses function values only; it does not require continuity or differentiability of the problem functions. This allows its use on problems whose functions cannot be expressed in closed algebraic form. The reliability and efficiency of the proposed PE_SPEEDUP algorithm has been demonstrated on some integer optimization problems taken from the literature.     

An accelerated covering relaxation algorithm for solving 0–1 positive polynomial programs

The purpose of this note is to present an accelerated algorithm for solving 0–1 positive polynomial (PP) problems. Like our covering relaxation algorithm (Management Science 1979), the accelerated algorithm is a cutting plane method, which uses the linear set covering problem as a relaxation for PP. However, a unique and novel feature of the accelerated algorithm is that it attempts to generate cutting planes from heuristic solutions to the set covering problem whenever possible. Computational results reveal that this strategy of generating cutting planes has led to a significant reduction in the computational time required to solve a PP problem.This research was partially supported by National Sciences and Engineering Research Council Canada Grants 67-4181 and 67-3998, Office of Naval Research Contract N00014-76-C-0418, and National Science Foundation Grant ECS80-22027.     

Cross decomposition for mixed integer programming

Many methods for solving mixed integer programming problems are based either on primal or on dual decomposition, which yield, respectively, a Benders decomposition algorithm and an implicit enumeration algorithm with bounds computed via Lagrangean relaxation. These methods exploit either the primal or the dual structure of the problem. We propose a new approach, cross decomposition, which allows exploiting simultaneously both structures. The development of the cross decomposition method captures profound relationships between primal and dual decomposition. It is shown that the more constraints can be included in the Langrangean relaxation (provided the duality gap remains zero), the fewer the Benders cuts one may expect to need. If the linear programming relaxation has no duality gap, only one Benders cut is needed to verify optimality.     

Arc-based integer programming formulations for three variants of proportional symbol maps

Proportional symbol maps are a cartographic tool that employs scaled symbols to represent data associated with specific locations. The symbols we consider are opaque disks, which may be partially covered by other overlapping disks. We address the problem of creating a suitable drawing of the disks that maximizes one of two quality metrics: the total and the minimum visible length of disk boundaries. We study three variants of this problem, two of which are known to be NP-hard and another whose complexity is open. We propose novel integer programming formulations for each problem variant and test them on real-world instances with a branch-and-cut algorithm. When compared with state-of-the-art models from the literature, our models significantly reduce computation times for most instances.     

A polynomial algorithm for an integer quadratic non-separable transportation problem

We study the problem of minimizing the total weighted tardiness when scheduling unti-length jobs on a single machine, in the presence of large sets of identical jobs. Previously known algorithms, which do not exploit the set structure, are at best pseudo-polynomial, and may be prohibitively inefficient when the set sizes are large. We give a polynomial algorithm for the problem, whose number of operations is independent of the set sizes. The problem is reformulated as an integer program with a quadratic, non-separable objective and transportation constraints. Employing methods of real analysis, we prove a tight proximity result between the integer solution to that problem and a fractional solution of a related problem. The related problem is shown to be polynomially solvable, and a rounding algorithm applied to its solution gives the optimal integer solution to the original problem.Supported in part by the National Science Foundation under grant ECS-85-01988, and by the Office of Naval Research under grant N00014-88-K-0377.Supported in part by Allon Fellowship, by Air Force grants 89-0512 and 90-0008 and by DIMACS (Center for Discrete Mathematics and Theoretical Computer Science), a National Science Foundation Science and Technology Center—NSF-STC88-09648. Part of the research of this author was performed in DIMACS Center, Rutgers University.Supported in part by Air Force grant 84-0205.     

A result in surrogate duality for certain integer programming problems

We consider linear programming problems with some equality constraints. For such problems, surrogate relaxation formulations relaxing equality constraints existwith zero primal-dual gap both when all variables are restricted to be integers and when no variable is required to be integer. However, for such surrogate formulations, when the variables are mixed-integer, the primal-dual gap may not be zero. We establish this latter result by a counterexample.     

A partial enumeration algorithm for pure nonlinear integer programming

In this paper, a partial enumeration algorithm is developed for a class of pure IP problems. Then, a computational algorithm, named PE_SPEEDUP (partial enumeration speedup), has been developed to use whatever explicit linear constraints are present to speedup the search for a solution. The method is easy to understand and implement, yet very effective in dealing with many pure IP problems, including knapsack problems, reliability optimization, and spare allocation problems. The algorithm is based on monotonicity properties of the problem functions, and uses function values only; it does not require continuity or differentiability of the problem functions. This allows its use on problems whose functions cannot be expressed in closed algebraic form. The reliability and efficiency of the proposed algorithm and the PE_SPEEDUP algorithm has been demonstrated on some integer optimization problems taken from the literature.     

Complexity of some parametric integer and network programming problems

Two examples of parametric cost programming problems—one in network programming and one in NP-hard 0-1 programming—are given; in each case, the number of breakpoints in the optimal cost curve is exponential in the square root of the number of variables in the problem. This research is partially supported by the Air Force Office of Scientic Research. Air Force Number AFOSR-78-3646     

An integer linear programming approach for bilinear integer programming

We introduce a new Integer Linear Programming (ILP) approach for solving Integer Programming (IP) problems with bilinear objectives and linear constraints. The approach relies on a series of ILP approximations of the bilinear IP. We compare this approach with standard linearization techniques on random instances and a set of real-world product bundling problems.     

A reduction dynamic programming algorithm for the bi-objective integer knapsack problem

This paper presents a backward state reduction dynamic programming algorithm for generating the exact Pareto frontier for the bi-objective integer knapsack problem. The algorithm is developed addressing a reduced problem built after applying variable fixing techniques based on the core concept. First, an approximate core is obtained by eliminating dominated items. Second, the items included in the approximate core are subject to the reduction of the upper bounds by applying a set of weighted-sum functions associated with the efficient extreme solutions of the linear relaxation of the multi-objective integer knapsack problem. Third, the items are classified according to the values of their upper bounds; items with zero upper bounds can be eliminated. Finally, the remaining items are used to form a mixed network with different upper bounds. The numerical results obtained from different types of bi-objective instances show the effectiveness of the mixed network and associated dynamic programming algorithm.     

Finite checkability for integer rounding properties in combinatorial programming problems

LetA be a nonnegative integral matrix with no zero columns. Theinteger round-up property holds forA if for each nonnegative integral vectorw, the solution value to the integer programming problem min{1 y: yA w, y 0, y integer} is obtained by rounding up to the nearest integer the solution value to the corresponding linear programming problem min{1 y: yA w, y 0}. Theinteger round-down property is similarly defined for a nonnegative integral matrixB with no zero rows by considering max{1 y: yB w, y 0, y integer} and its linear programming correspondent. It is shown that the integer round-up and round-down properties can be checked through a finite process. The method of proof motivates a new and elementary proof of Fulkerson's Pluperfect Graph Theorem.Research partially supported by NSF Grants ENG76-09936 and ENG78-09882.     

Sensitivity theorems in integer linear programming

We consider integer linear programming problems with a fixed coefficient matrix and varying objective function and right-hand-side vector. Among our results, we show that, for any optimal solution to a linear program max{wx: Axb}, the distance to the nearest optimal solution to the corresponding integer program is at most the dimension of the problem multiplied by the largest subdeterminant of the integral matrixA. Using this, we strengthen several integer programming proximity results of Blair and Jeroslow; Graver; and Wolsey. We also show that the Chvátal rank of a polyhedron {x: Axb} can be bounded above by a function of the matrixA, independent of the vectorb, a result which, as Blair observed, is equivalent to Blair and Jeroslow's theorem that each integer programming value function is a Gomory function.Supported by a grant from the Alexander von Humboldt Stiftung.Since September 1985: Department of Operations Research, Upson Hall, Cornell University, Ithaca, NY 14853, USA.Partially supported by the Sonderforschungbereich 21 (DFG), Institut für Ökonometrie und Operations Research of the University of Bonn, FR Germany.     

A real coded genetic algorithm for solving integer and mixed integer optimization problems

In this paper, a real coded genetic algorithm named MI-LXPM is proposed for solving integer and mixed integer constrained optimization problems. The proposed algorithm is a suitably modified and extended version of the real coded genetic algorithm, LXPM, of Deep and Thakur [K. Deep, M. Thakur, A new crossover operator for real coded genetic algorithms, Applied Mathematics and Computation 188 (2007) 895-912; K. Deep, M. Thakur, A new mutation operator for real coded genetic algorithms, Applied Mathematics and Computation 193 (2007) 211-230]. The algorithm incorporates a special truncation procedure to handle integer restrictions on decision variables along with a parameter free penalty approach for handling constraints. Performance of the algorithm is tested on a set of twenty test problems selected from different sources in literature, and compared with the performance of an earlier application of genetic algorithm and also with random search based algorithm, RST2ANU, incorporating annealing concept. The proposed MI-LXPM outperforms both the algorithms in most of the cases which are considered.     

Penalty for zero–one integer equivalent problem

The equivalence of zero–one integer programming and a concave quadratic penalty function problem has been shown by Raghavachari, for a sufficiently large value of the penalty. A lower bound for this penalty is obtained here, which in specific cases cannot be reduced.This research was supported in part by the Computer Science Section of the National Science Foundation under Research Grant MCS 8101214.     

A nonlinear Lagrangian dual for integer programming

Nonlinear Lagrangian theory offers a success guarantee for the dual search via construction of a nonlinear support of the perturbation function at the optimal point. In this paper, a new nonlinear dual formulation of an exponential form is proposed for bounded integer programming. This new formulation possesses an asymptotic strong duality property and guarantees a success in identifying a primal optimum solution. No actual dual search is needed in the solution process when the parameter of the nonlinear Lagrangian formulation is set to be large enough.