General purpose heuristics for integer programming—Part I

In spite of the many special purpose heuristics for specific classes of integer programming (IP) problems, there are few developments that focus on general purpose integer programming heuristics. This stems partly from the perception that general purpose methods are likely to be less effective than specialized procedures for specific problems, and partly from the perception that there is no unifying theoretical basis for creating general purpose heuristics. Still, there is a general acknowledgment that methods which are not limited to solving IP problems on a class by class basis, but which apply to a broader range of problems, have significant value. We show that certain ideas proposed in the 1970s, which are often overlooked, can be reformulated and linked with more recent developments to give a useful theoretical framework for generating general purpose IP heuristics. This framework, which has the appeal of being highly visual, makes use of cutting plane derivations that also give a natural basis for marrying heuristics with exact branch and cut methods for integer programming problems.     

A provably convergent heuristic for stochastic bicriteria integer programming

We propose a general-purpose algorithm APS (Adaptive Pareto-Sampling) for determining the set of Pareto-optimal solutions of bicriteria combinatorial optimization (CO) problems under uncertainty, where the objective functions are expectations of random variables depending on a decision from a finite feasible set. APS is iterative and population-based and combines random sampling with the solution of corresponding deterministic bicriteria CO problem instances. Special attention is given to the case where the corresponding deterministic bicriteria CO problem can be formulated as a bicriteria integer linear program (ILP). In this case, well-known solution techniques such as the algorithm by Chalmet et al. can be applied for solving the deterministic subproblem. If the execution of APS is terminated after a given number of iterations, only an approximate solution is obtained in general, such that APS must be considered a metaheuristic. Nevertheless, a strict mathematical result is shown that ensures, under rather mild conditions, convergence of the current solution set to the set of Pareto-optimal solutions. A modification replacing or supporting the bicriteria ILP solver by some metaheuristic for multicriteria CO problems is discussed. As an illustration, we outline the application of the method to stochastic bicriteria knapsack problems by specializing the general framework to this particular case and by providing computational examples.     

Mathematical programming based heuristics for the 0–1 MIP: a survey

The 0–1 mixed integer programming problem is used for modeling many combinatorial problems, ranging from logical design to scheduling and routing as well as encompassing graph theory models for resource allocation and financial planning. This paper provides a survey of heuristics based on mathematical programming for solving 0–1 mixed integer programs (MIP). More precisely, we focus on the stand-alone heuristics for 0–1 MIP as well as those heuristics that use linear programming techniques or solve a series of linear programming models or reduced problems, deduced from the initial one, in order to produce a high quality solution of a considered problem. Our emphasis will be on how mathematical programming techniques can be used for approximate problem solving, rather than on comparing performances of heuristics.     

Classification of Dantzig–Wolfe reformulations for binary mixed integer programming problems

In this note, we provide a classification of Dantzig–Wolfe reformulations for Binary Mixed Integer Programming Problems. We specifically focus on modeling the binary conditions in the convexification approach to the Dantzig–Wolfe decomposition. For a general Binary Mixed Integer Programming problem, an extreme point of the overall problem does not necessarily correspond to an extreme point of the subproblem. Therefore, the binary conditions cannot in general be imposed on the new master problem variables but must be imposed on the original binary variables. In some cases, however, it is possible to impose the binary restrictions directly on the new master problem variables. The issue of imposing binary conditions on the original variables versus the master problem variables has not been discussed systematically for MIP problems in general in the literature and most of the research has been focused on the pure binary case. The classification indicates in which cases you can, and cannot, impose binary conditions on the new master problem variables.     

Chvátal closures for mixed integer programming problems

Chvátal introduced the idea of viewing cutting planes as a system for proving that every integral solution of a given set of linear inequalities satisfies another given linear inequality. This viewpoint has proven to be very useful in many studies of combinatorial and integer programming problems. The basic ingredient in these cutting-plane proofs is that for a polyhedronP and integral vectorw, if max(wx|x P, wx integer} =t, thenwx t is valid for all integral vectors inP. We consider the variant of this step where the requirement thatwx be integer may be replaced by the requirement that be integer for some other integral vector . The cutting-plane proofs thus obtained may be seen either as an abstraction of Gomory's mixed integer cutting-plane technique or as a proof version of a simple class of the disjunctive cutting planes studied by Balas and Jeroslow. Our main result is that for a given polyhedronP, the set of vectors that satisfy every cutting plane forP with respect to a specified subset of integer variables is again a polyhedron. This allows us to obtain a finite recursive procedure for generating the mixed integer hull of a polyhedron, analogous to the process of repeatedly taking Chvátal closures in the integer programming case. These results are illustrated with a number of examples from combinatorial optimization. Our work can be seen as a continuation of that of Nemhauser and Wolsey on mixed integer cutting planes.Supported by Sonderforschungsbereich 303 (DFG) and by NSF Grant Number ECS-8611841.Supported by NSF Grant Number ECS-8418392 and Sonderforschungsbereich 303 (DFG), Institut für Ökonometrie und Operations Research, Universität Bonn, FR Germany.     

Some new perspectives for solving 0–1 integer programming problems using Balas method

Computational Management Science - Egon Balas’s additive algorithm, also known as implicit enumeration, is a technique that uses a branch-and-bound (B&B) approach to finding optimal...     

On the polynomial mixed 0–1 fractional programming problems

This paper proposes a new method of solving polynomial mixed 0–1 fractional programming (P01FP) problems to obtain a global optimum. Given a polynomial 0–1 term x₁x₂,…,x_ny, where x_i is a 0–1 variable and y is a continuous variable; we develop a linearization technique to transfer the x₁x₂,…,x_ny term into a set of mixed 0–1 linear inequalities. Based on this technique, the P01FP can then be solved by a branch-and-bound method to obtain the global solution.     

A cutting-plane approach to mixed 0–1 stochastic integer programs

We consider a mixed 0–1 integer programming problem with dual block-angular structure arising in two-stage stochastic programming. A relaxation is proposed such that the problem is decomposed into subproblems each corresponding to the outcomes of the random variable. The convex hull of feasible solutions for the relaxation is characterized using results from disjunctive programming and it is shown how Lift-and-Project cuts can be generated for one subproblem and made valid for different outcomes.     

A mixed integer nonlinear programming model for the optimal repair–replacement in the firm

Optimal repair–replacement problem is an important aspect of economic decision making at the firm and aggregate levels. In this paper, we extend the continuous time optimal replacement model in the firm under technological progress by considering the possibility of repairing/replacing the machines during their lifetime period. In our model, two possible decisions can be recognized by the managers in which the machines are repaired under the efficiency condition or replaced under the availability of technological progress in the firm. As a special case, we restrict the model to the more real case in which all the growth, purchase price and repair cost functions are assumed to be in the exponential form. The solvability of the model in this case is also discussed.     

An evolutionary heuristic for quadratic 0–1 programming

In this paper we present a heuristic algorithm for the well-known Unconstrained Quadratic 0–1 Programming Problem. The approach is based on combining solutions in a genetic paradigm and incorporates intensification algorithms used to improve solutions and speed up the method. Extensive computational experiments on instances with up to 500 variables are presented and we compare our approach both with powerful heuristic and exact algorithms from the literature establishing the effectiveness of the method in terms of solutions quality and computing time.     

Fuzzy programming for multiobjective 0–1 programming problems through revised genetic algorithms

Recently, genetic algorithms (GAs), a new learning paradigm that models a natural evolution mechanism, have received a great deal of attention regarding their potential as optimization techniques for solving combinatorial optimization problems. In this paper, we focus on multiobjective 0–1 programming problems as a generalization of the traditional single objective ones. By considering the imprecise nature of human judgements, we assume that the decision maker may have fuzzy goal for each of the objective functions. After eliciting the linear membership functions through the interaction with the decision maker, we adopt the fuzzy decision of Bellman and Zadeh or minimum-operator for combining them. In order to investigate the applicability of the conventional GAs for the solution of the formulated problems, a lot of numerical simulations are performed by assuming several genetic operators. Then, instead of using the penalty function for treating the constraints, we propose three types of revised GAs which generate only feasible solutions. Illustrative numerical examples demonstrate both feasibility and efficiency of the proposed methods.     

Interactive fuzzy programming for multi-level 0–1 programming problems through genetic algorithms

In this paper, we propose interactive fuzzy programming for multi-level 0–1 programming problems through genetic algorithms. Our method is supposed to apply to hierarchical decision problems in which decision-making at each level is sequential from upper to lower level and decision makers are essentially cooperative. After determining the fuzzy goals of the decision makers at all levels, a satisfactory solution is derived efficiently by updating the satisfactory degrees of the decision makers at the upper level with considerations of overall satisfactory balance among all levels. An illustrative numerical example for three-level 0–1 programming problems is provided to demonstrate the feasibility of the proposed method.     

Linear programming for the 0–1 quadratic knapsack problem

In this paper we consider the quadratic knapsack problem which consists in maximizing a positive quadratic pseudo-Boolean function subject to a linear capacity constraint. We propose a new method for computing an upper bound. This method is based on the solution of a continuous linear program constructed by adding to a classical linearization of the problem some constraints rebundant in 0–1 variables but nonredundant in continuous variables. The obtained upper bound is better than the bounds given by other known methods. We also propose an algorithm for computing a good feasible solution. This algorithm is an elaboration of the heuristic methods proposed by Chaillou, Hansen and Mahieu and by Gallo, Hammer and Simeone. The relative error between this feasible solution and the optimum solution is generally less than 1%. We show how these upper and lower bounds can be efficiently used to determine the values of some variables at the optimum. Finally we propose a branch-and-bound algorithm for solving the quadratic knapsack problem and report extensive computational tests.     

bc–opt: a branch-and-cut code for mixed integer programs

A branch-and-cut mixed integer programming system, called bc–opt, is described, incorporating most of the valid inequalities that have been used or suggested for such systems, namely lifted 0-1 knapsack inequalities, 0-1 gub knapsack and integer knapsack inequalities, flowcover and continuous knapsack inequalities, path inequalities for fixed charge network flow structure and Gomory mixed integer cuts. The principal development is a set of interface routines allowing these cut routines to generate cuts for new subsets or aggregations of constraints. The system is built using the XPRESS Optimisation Subroutine Library (XOSL) which includes a cut manager that handles the tree and cut management, so that the user only essentially needs to develop the cut separation routines. Results for the MIPLIB3.0 library are presented - 37 of the instances are solved very easily, optimal or near optimal solution are produced for 18 other instances, and of the 4 remaining instances, 3 have 0, +1, -1 matrices for which bc–opt contains no special features. Received May 11, 1997 / Revised version received March 8, 1999?Published online June 11, 1999     

Quantitative stability analysis for vector problems of 0–1 programming

We consider multiple objective 0–1 programming problems in the situation where parameters of objective functions and linear constraints are exposed to independent perturbations. We study quantitative characteristics of stability (stability radii) of problem solutions. An approach to deriving formulae and estimations of stability radii is presented. This approach is applied to stability analysis of the linear 0–1 programming problem and problems with two types of nonlinear objective functions: linear absolute value and quadratic.     

A new penalty parameter for linearly constrained 0–1 quadratic programming problems

The equivalence between the linearly constrained 0–1 quadratic programming problem and the continuous quadratic programming problem is studied in this note. Specifically, we show that the existing penalty parameter from the literature can be further improved.     

Heuristics and reduction methods for multiple constraints 0–1 linear programming problems

This work extends the efficient results relative to the 0–1 knapsack problem to the multiple inequality constraints 0–1 linear programming problems. The two crucial phases for the solving of this type of problems are presented: (i) Two linear expected time complexity greedy algorithms are proposed for the determination of a lower bound on the optimal value by using a cascade of surrogate relaxations of the original problem whose sizes are decreasing step by step. A comparative study with the best known heuristic methods is reported; it concerned the accuracy of the approximate solutions and the practical computational times. (ii) This greedy algorithm is inserted in an efficient reduction framework. Variables and constraints are eliminated by the conjunction of tests applied to Lagrangean and surrogate relaxations of the original problem. A lot of computational results are summarized by considering test problems of the literature.     

Fractional 0–1 programming: applications and algorithms

We consider a class of nonlinear integer optimization problems commonly known as fractional 0–1 programming problems (also, often referred to as hyperbolic 0–1 programming problems), where the objective is to optimize the sum of ratios of affine functions subject to a set of linear constraints. Such problems arise in diverse applications across different fields, and have been the subject of study in a number of papers during the past few decades. In this survey we overview the literature on fractional 0–1 programs including their applications, related computational complexity issues and solution methods including exact, approximation and heuristic algorithms.