Reoptimizing the 0-1 knapsack problem

In this paper we study the problem where an optimal solution of a knapsack problem on n items is known and a very small number k of new items arrive. The objective is to find an optimal solution of the knapsack problem with n+k items, given an optimal solution on the n items (reoptimization of the knapsack problem). We show that this problem, even in the case k=1, is NP-hard and that, in order to have effective heuristics, it is necessary to consider not only the items included in the previously optimal solution and the new items, but also the discarded items. Then, we design a general algorithm that makes use, for the solution of a subproblem, of an α-approximation algorithm known for the knapsack problem. We prove that this algorithm has a worst-case performance bound of , which is always greater than α, and therefore that this algorithm always outperforms the corresponding α-approximation algorithm applied from scratch on the n+k items. We show that this bound is tight when the classical Ext-Greedy algorithm and the algorithm are used to solve the subproblem. We also show that there exist classes of instances on which the running time of the reoptimization algorithm is smaller than the running time of an equivalent PTAS and FPTAS.     

An Adapted Step Size Algorithm for a 0-1 Biknapsack Lagrangean Dual

This paper deals with a new algorithm for a 0-1 bidimensional knapsack Lagrangean dual which relaxes one of the two constraints. Classical iterative algorithms generate a sequence of multipliers which converges to an optimal one. In this way, these methods generate a sequence of 0-1 one-dimensional knapsack instances. Generally, the procedure for solving each instance is considered as a black box. We propose to design a new iterative scheme in which the computation of the step size takes into account the algorithmic efficiency of each instance. Our adapted step size iterative algorithm is compared favorably with several other algorithms for the 0-1 biknapsack Lagrangean dual over difficult instances for CPLEX 7.0.     

The 0-1 bidimensional knapsack problem: Toward an efficient high-level primitive tool

Efficient codes exist for exactly solving the 0-1 knapsack problem, which is a common primitive structure in relaxation and decomposition techniques for the solution of general models. We suggest moving to a higher primitive level by using the bidimensional knapsack, which can be used to enhance linear programming or Lagrangean type classical relaxations.With the ultimate aim of providing an exact and efficient solution to the bidimensional knapsack problem, we describe here a heuristic approach based on surrogate duality. In particular, we consider the usefulness of a specific preprocessing phase before a possible enumerative phase.Extensive numerical experiments, based on test problems from the literature as well as randomly generated instances, show that our code compares favorably with the GP procedure developed by Gavish and Pirkul for the multidimensional case.     

A decomposition heuristics for the container ship stowage problem

In this paper we face the problem of stowing a containership, referred to as the Master Bay Plan Problem (MBPP); this problem is difficult to solve due to its combinatorial nature and the constraints related to both the ship and the containers. We present a decomposition approach that allows us to assign a priori the bays of a containership to the set of containers to be loaded according to their final destination, such that different portions of the ship are independently considered for the stowage. Then, we find the optimal solution of each subset of bays by using a 0/1 Linear Programming model. Finally, we check the global ship stability of the overall stowage plan and look for its feasibility by using an exchange algorithm which is based on local search techniques. The validation of the proposed approach is performed with some real life test cases. This work has been developed within the research area: “The harbour as a logistic node” of the Italian Centre of Excellence on Integrated Logistics (CIELI) of the University of Genoa, Italy     

The 0-1 knapsack problem with fuzzy data

The 0-1 knapsack problem with imprecise profits and imprecise weights of items is considered. The imprecise parameters are modeled as fuzzy intervals. A method of choosing a solution under the uncertainty is proposed and two methods for solving the constructed models are provided.     

Lagrangean relaxation based heuristics for lot sizing with setup times

We consider a lot sizing problem with setup times where the objective is to minimize the total inventory carrying cost only. The demand is dynamic over time and there is a single resource of limited capacity. We show that the approaches implemented in the literature for more general versions of the problem do not perform well in this case. We examine the Lagrangean relaxation (LR) of demand constraints in a strong reformulation of the problem. We then design a primal heuristic to generate upper bounds and combine it with the LR problem within a subgradient optimization procedure. We also develop a simple branch and bound heuristic to solve the problem. Computational results on test problems taken from the literature show that our relaxation procedure produces consistently better solutions than the previously developed heuristics in the literature.     

Probabilistic properties of the dual structure of the multidimensional knapsack problem and fast statistically efficient algorithms

Properties of several dual characteristics of the multidimensional knapsack problem (such as the probability of existence of-optimal and optimal-feasible Lagrange function generalized saddle points, magnitude of relative duality gap, etc.) are investigated for different probabilistic models. Sufficient conditions of good asymptotic behavior of the dual characteristics are given. A fast statistically efficient approximate algorithm with linear running time complexity for problems with random coefficients is presented.This paper was written when the author was affiliated with Chelyabinsk State Technical University and the Moscow Physical and Technical Institute, Russia.     

Improved convergent heuristics for the 0-1 multidimensional knapsack problem

At the end of the seventies, Soyster et al. (Eur. J. Oper. Res. 2:195–201, 1978) proposed a convergent algorithm that solves a series of small sub-problems generated by exploiting information obtained through a series of linear programming relaxations. This process is suitable for the 0-1 mixed integer programming problems when the number of constraints is relatively smaller when compared to the number of variables. In this paper, we first revisit this algorithm, once again presenting it and some of its properties, including new proofs of finite convergence. This algorithm can, in practice, be used as a heuristic if the number of iterations is limited. We propose some improvements in which dominance properties are emphasized in order to reduce the number of sub problems to be solved optimally. We also add constraints to these sub-problems to speed up the process and integrate adaptive memory. Our results show the efficiency of the proposed improvements for the 0-1 multidimensional knapsack problem.     

A Lagrangean heuristic for the maximal covering location problem

We develop a Lagrangean heuristic for the maximal covering location problem. Upper bounds are given by a vertex addition and substitution heuristic and lower bounds are produced through a subgradient optimization algorithm. The procedure was tested in networks of up to 150 vertices. A duality gap was generally present at the end of the heuristic for the larger problems. The test problems were run in an IBM 3090-600J ‘super-computer’; the maximum computing time was kept below three minutes of CPU.     

A technique for speeding up the solution of the Lagrangean dual

We propose techniques for the solution of the LP relaxation and the Lagrangean dual in combinatorial optimization and nonlinear programming problems. Our techniques find the optimal solution value and the optimal dual multipliers of the LP relaxation and the Lagrangean dual in polynomial time using as a subroutine either the Ellipsoid algorithm or the recent algorithm of Vaidya. Moreover, in problems of a certain structure our techniques find not only the optimal solution value, but the solution as well. Our techniques lead to significant improvements in the theoretical running time compared with previously known methods (interior point methods, Ellipsoid algorithm, Vaidya's algorithm). We use our method to the solution of the LP relaxation and the Langrangean dual of several classical combinatorial problems, like the traveling salesman problem, the vehicle routing problem, the Steiner tree problem, thek-connected problem, multicommodity flows, network design problems, network flow problems with side constraints, facility location problems,K-polymatroid intersection, multiple item capacitated lot sizing problem, and stochastic programming. In all these problems our techniques significantly improve the theoretical running time and yield the fastest way to solve them.     

An iterative variable-based fixation heuristic for the 0-1 multidimensional knapsack problem

An iterative scheme which is based on a dynamic fixation of the variables is developed to solve the 0-1 multidimensional knapsack problem. Such a scheme has the advantage of generating memory information, which is used on the one hand to choose the variables to fix either permanently or temporarily and on the other hand to construct feasible solutions of the problem. Adaptations of this mechanism are proposed to explore different parts of the search space and to enhance the behaviour of the algorithm. Encouraging results are presented when tested on the correlated instances of the 0-1 multidimensional knapsack problem.     

Revisiting surrogate relaxation for the multidimensional knapsack problem

The multidimensional knapsack problem (MKP) is a classic problem in combinatorial optimisation. Several authors have proposed to use surrogate relaxation to compute upper bounds for the MKP. In their papers, the surrogate dual is solved heuristically. We show that, using a modern dual simplex solver as a subroutine, one can solve the surrogate dual exactly in reasonable computing times. On the other hand, the resulting upper bound tends to be strong only for relatively small MKP instances.     

Solving the 0–1 proportional knapsack problem by sampling

In this paper, we deal with the proportional knapsack problem that is a variation on the ordinary knapsack problem. In the proportional knapsack problem, we look at filling an urn with objects having two characteristics: color and weight. The colors of the objects in the urn should be proportional to the distribution of the colors in the object universe, and the total weight of the objects in the urn should be as close as possible to the capacity of the urn. The formulation of the problem was motivated by a real-life application from the area of finance, called a dollar roll. We show that the proportional knapsack problem is NP-hard, and then, using sampling, develop a heuristic procedure for solving the problem.Partial support from the Fund for the Promotion of Research and from the Alexander Goldberg Memorial Fund at Technion is gratefully acknowledged.     

On complexity of unconstrained hyperbolic 0-1 programming problems

Single- and multiple-ratio unconstrained hyperbolic 0-1 programming problems are considered. We prove that checking whether these problems have a unique solution is NP-hard. Furthermore, we show that finding the global maximizer of problems with unique solution remains NP-hard. We also discuss complexity of local search and approximability for multiple-ratio problems.     

A theoretical and empirical investigation on the Lagrangian capacities of the 0-1 multidimensional knapsack problem

We present a novel Lagrangian method to find good feasible solutions in theoretical and empirical aspects. After investigating the concept of Lagrangian capacity, which is the value of the capacity constraint that Lagrangian relaxation can find an optimal solution, we formally reintroduce Lagrangian capacity suitable to the 0-1 multidimensional knapsack problem and present its new geometric equivalent condition including a new associated property. Based on the property, we propose a new Lagrangian heuristic that finds high-quality feasible solutions of the 0-1 multidimensional knapsack problem. We verify the advantage of the proposed heuristic by experiments. We make comparisons with existing Lagrangian approaches on benchmark data and show that the proposed method performs well on large-scale data.     

A faster algorithm for the continuous bilevel knapsack problem

We construct a fast algorithm with time complexity $O(nlogn)$ for a continuous bilevel knapsack problem with interdiction constraints for $n$ items. This improves on a recent algorithm from the literature with quadratic time complexity $O\left(n^2\right)$.     

On branching heuristics for the bi-objective 0/1 unidimensional knapsack problem

This paper focuses on branching strategies that are involved in branch and bound algorithms when solving multi-objective optimization problems. The choice of the branching variable at each node of the search tree constitutes indeed an important component of these algorithms. In this work we focus on multi-objective knapsack problems. In the literature, branching heuristics used for these problems are static, i.e., the order on the variables is determined prior to the execution. This study investigates the benefit of defining more sophisticated branching strategies. We first analyze and compare a representative set of classic branching heuristics and conclude that none can be identified as the best overall heuristic. Using an oracle, we highlight that combining branching heuristics within the same branch and bound algorithm leads to considerably reduced search trees but induces high computational costs. Based on learning adaptive techniques, we propose then dynamic adaptive branching strategies that are able to select the suitable heuristic to apply at each node of the search tree. Experiments are conducted on the bi-objective 0/1 unidimensional knapsack problem.     

A Tabu Search Algorithm for Quadratic 0—1 Programming Problem

1.IntroductionThemathematicalmodelofaquaduatico-1programmingproblemisasfollows:MinimizesubjecttwhereI,AsfaraspaperL1'2Jcanseemedel(I)(fordu=O)isveryimPOrtantinthemarshallingofsinglegrouptrainbetweenmarshallingstationsinrailwaynetworkandthemarshallingoftraininnetw0rkwiththetw0types0fvehiclefl0w,butproblem(I)isNP-C.C0nsiderarelax-ationproblemasf0llows:MinimizeIngeneral,solvingrelaxati0nproblemiseasierthansolvingcombinatiorial0ptimalpr0b-lem,thesameaslinearpr0grammingproblemissolvableinPOly…     

A “reduce and solve” approach for the multiple-choice multidimensional knapsack problem

The multiple-choice multidimensional knapsack problem (MMKP) is a well-known NP-hard combinatorial optimization problem with a number of important applications. In this paper, we present a “reduce and solve” heuristic approach which combines problem reduction techniques with an Integer Linear Programming (ILP) solver (CPLEX). The key ingredient of the proposed approach is a set of group fixing and variable fixing rules. These fixing rules rely mainly on information from the linear relaxation of the given problem and aim to generate reduced critical subproblem to be solved by the ILP solver. Additional strategies are used to explore the space of the reduced problems. Extensive experimental studies over two sets of 37 MMKP benchmark instances in the literature show that our approach competes favorably with the most recent state-of-the-art algorithms. In particular, for the set of 27 conventional benchmarks, the proposed approach finds an improved best lower bound for 11 instances and as a by-product improves all the previous best upper bounds. For the 10 additional instances with irregular structures, the method improves 7 best known results.     

An efficient linearization technique for mixed 0-1 polynomial problem

This paper addresses a new and efficient linearization technique to solve mixed 0-1 polynomial problems to achieve a global optimal solution. Given a mixed 0-1 polynomial term z=c_tx₁x₂…x_ny, where x₁,x₂,…,x_n are binary (0-1) variables and y is a continuous variable. Also, c_t can be either a positive or a negative parameter. We transform z into a set of auxiliary constraints which are linear and can be solved by exact methods such as branch and bound algorithms. For this purpose, we will introduce a method in which the number of additional constraints is decreased significantly rather than the previous methods proposed in the literature. As is known in any operations research problem decreasing the number of constraints leads to decreasing the mathematical computations, extensively. Thus, research on the reducing number of constraints in mathematical problems in complicated situations have high priority for decision makers. In this method, each n-auxiliary constraints proposed in the last method in the literature for the linearization problem will be replaced by only 3 novel constraints. In other words, previous methods were dependent on the number of 0-1 variables and therefore, one auxiliary constraint was considered per 0-1 variable, but this method is completely independent of the number of 0-1 variables and this illustrates the high performance of this method in computation considerations. The analysis of this method illustrates the efficiency of the proposed algorithm.