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.     

Testing optimality for quadratic 0–1 unconstrained problems

This paper analyses a necessary and sufficient optimality condition for quadratic pseudo-Boolean unconstrained problems. It is proved that in general testing any necessary and sufficient optimality condition is a difficult task for anyNP-hard problem. An-optimality condition is derived together with an approximation scheme to test it.This work has been supported by the Progetto Finalizzato Trasporti 2, 93.01799.PF74.Professor Paolo Carraresi died unexpectedly on March 5, 1994. At the time of his death this paper had been completed. While undertaking the final revision, the other two authors were reminded just how much they were indebted to Professor Carraresi after many years of common work together.     

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.     

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.     

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.     

An adaptive nonmonotone global Barzilai–Borwein gradient method for unconstrained optimization

The Barzilai–Borwein (BB) gradient method has received many studies due to its simplicity and numerical efficiency. By incorporating a nonmonotone line search, Raydan (SIAM J Optim. 1997;7:26–33) has successfully extended the BB gradient method for solving general unconstrained optimization problems so that it is competitive with conjugate gradient methods. However, the numerical results reported by Raydan are poor for very ill-conditioned problems because the effect of the degree of nonmonotonicity may be noticeable. In this paper, we focus more on the nonmonotone line search technique used in the global Barzilai–Borwein (GBB) gradient method. We improve the performance of the GBB gradient method by proposing an adaptive nonmonotone line search based on the morphology of the objective function. We also prove the global convergence and the R-linear convergence rate of the proposed method under reasonable assumptions. Finally, we give some numerical experiments made on a set of unconstrained optimization test problems of the CUTEr collection. The results show the efficiency of the proposed method in the sense of the performance profile introduced (Math Program. 2002;91:201–213) by Dolan and Moré.     

An exact algorithm for the 0–1 linear knapsack problem with a single continuous variable

The 0–1 linear knapsack problem with a single continuous variable (KPC) is an extension of the binary knapsack problem (KP). It is an NP-hard problem. In this paper, we show that KPC can be reduced to KP and a pseudo-knapsack problem (PKP), which is similar to the traditional knapsack problem except that the profits of items may be non-positive, and the weight sum has two sided limits on capacity. We use the Dynamic Programming algorithm COMBO (Martello et al., Manag Sci 45(3):414–424, 1999) to solve KP, and modify the branch and bound method EXPKNAP (Pisinger, Eur J Oper Res 87:175–187, 1995) for KP to solve the PKP. Numerical experiments show the efficiency of our method.     

BFC-MSMIP: an exact branch-and-fix coordination approach for solving multistage stochastic mixed 0–1 problems

We present an exact algorithmic framework, so-called BFC-MSMIP, for optimizing multistage stochastic mixed 0–1 problems with complete recourse. The uncertainty is represented by using a scenario tree and lies anywhere in the model. The problem is modeled by a splitting variable representation of the Deterministic Equivalent Model of the stochastic problem, where the 0–1 variables and the continuous variables appear at any stage. The approach uses the Twin Node Family concept within the algorithmic framework, so-called Branch-and-Fix Coordination, for satisfying the nonanticipativity constraints in the 0–1 variables. Some blocks of additional strategies are used in order to show the performance of the proposed approach. The blocks are related to the scenario clustering, the starting branching and the branching order strategies, among others. Some computational experience is reported. It shows that the new approach obtains the optimal solution in all instances under consideration.      

An algorithm to perform a complete right-hand-side parametrical analysis for a 0–1-integer linear programming problem

We designed and implemented an algorithm to solve the continuous right-hand side parametric 0–1-Integer Linear Programming (ILP) problem, that is to solve a family of 0–1-ILP problems in which the problems are related by having identical objective and matrix coefficients. Our algorithm works by choosing an appropiate finite sequence of non-parametric 0–1-Mixed Integer Linear Programming (MILP) problems in order to obtain a complete parametrical analysis. The algorithm may be implemented by using any software capable of solving MILP problems.     

The multiparametric 0–1-integer linear programming problem: A unified approach

We designed an algorithm for the multiparametric 0–1-integer linear programming (ILP) problem with the perturbation of the constraint matrix, the objective function and the right-hand side vector simultaneously considered. Our algorithm works by choosing an appropriate finite sequence of non-parametric mixed integer linear programming (MILP) problems in order to obtain a complete multiparametrical analysis. The algorithm may be implemented by using any software capable of solving MILP problems.     

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...     

A compact variant of the QCR method for quadratically constrained quadratic 0–1 programs

Quadratic Convex Reformulation (QCR) is a technique that was originally proposed for quadratic 0–1 programs, and then extended to various other problems. It is used to convert non-convex instances into convex ones, in such a way that the bound obtained by solving the continuous relaxation of the reformulated instance is as strong as possible. In this paper, we focus on the case of quadratically constrained quadratic 0–1 programs. The variant of QCR previously proposed for this case involves the addition of a quadratic number of auxiliary continuous variables. We show that, in fact, at most one additional variable is needed. Some computational results are also presented.     

An incremental primal–dual method for nonlinear programming with special structure

We propose a new class of incremental primal–dual techniques for solving nonlinear programming problems with special structure. Specifically, the objective functions of the problems are sums of independent nonconvex continuously differentiable terms minimized subject to a set of nonlinear constraints for each term. The technique performs successive primal–dual increments for each decomposition term of the objective function. The primal–dual increments are calculated by performing one Newton step towards the solution of the Karush–Kuhn–Tucker optimality conditions of each subproblem associated with each objective function term. We show that the resulting incremental algorithm is q-linearly convergent under mild assumptions for the original problem.     

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.     

An interactive fuzzy satisficing method for multiobjective 0–1 programming problems with fuzzy numbers through genetic algorithms with double strings

In this paper, by considering the experts' vague or fuzzy understanding of the nature of the parameters in the problem-formulation process, multiobjective 0–1 programming problems involving fuzzy numbers are formulated. Using the a-level sets of fuzzy numbers, the corresponding nonfuzzy α-programming problem is introduced. The fuzzy goals of the decision maker (DM) for the objective functions are quantified by eliciting the corresponding linear membership functions. Through the introduction of an extended Pareto optimality concept, if the DM specifies the degree α and the reference membership values, the corresponding extended Pareto optimal solution can be obtained by solving the augmented minimax problems through genetic algorithms with double strings. Then an interactive fuzzy satisficing method for deriving a satisficing solution for the DM efficiently from an extended Pareto optimal solution set is presented. An illustrative numerical example is provided to demonstrate the feasibility and efficiency of the proposed method.