An implementation of exact knapsack separation

Cutting planes have been used with great success for solving mixed integer programs. In recent decades, many contributions have led to successive improvements in branch-and-cut methods which incorporate cutting planes in branch and bound algorithm. Using advances that have taken place over the years on 0–1 knapsack problem, we investigate an efficient approach for 0–1 programs with knapsack constraints as local structure. Our approach is based on an efficient implementation of knapsack separation problem which consists of the four phases: preprocessing, row generation, controlling numerical errors and sequential lifting. This approach can be used independently to improve formulations with cutting planes generated or incorporated in branch and cut to solve a problem. We show that this approach allows us to efficiently solve large-scale instances of generalized assignment problem, multilevel generalized assignment problem, capacitated \(p\)-median problem and capacitated network location problem to optimality.     

An exact method with variable fixing for solving the generalized assignment problem

We propose a simple exact algorithm for solving the generalized assignment problem. Our contribution is twofold: we reformulate the optimization problem into a sequence of decision problems, and we apply variable-fixing rules to solve these effectively. The decision problems are solved by a simple depth-first lagrangian branch-and-bound method, improved by our variable-fixing rules to prune the search tree. These rules rely on lagrangian reduced costs which we compute using an existing but little-known dynamic programming algorithm.     

A generalized knapsack problem with variable coefficients

The ordinary knapsack problem is to find the optimal combination of items to be packed in a knapsack under a single constraint on the total allowable resources, where all coefficients in the objective function and in the constraint are constant.In this paper, a generalized knapsack problem with coefficients depending on variable parameters is proposed and discussed. Developing an effective branch and bound algorithm for this problem, the concept of relaxation and the efficiency function introduced here will play important roles. Furthermore, a relation between the algorithm and the dynamic programming approach is discussed, and subsequently it will be shown that the ordinary 0–1 knapsack problem, the linear programming knapsack problem and the single constrained linear programming problem with upper-bounded variables are special cases of the interested problem. Finally, practical applications of the problem and its computational experiences will be shown.     

An exact algorithm for the fixed-charge multiple knapsack problem

We formulate the fixed-charge multiple knapsack problem (FCMKP) as an extension of the multiple knapsack problem (MKP). The Lagrangian relaxation problem is easily solved, and together with a greedy heuristic we obtain a pair of upper and lower bounds quickly. We make use of these bounds in the pegging test to reduce the problem size. We also present a branch-and-bound (B&B) algorithm to solve FCMKP to optimality. This algorithm exploits the Lagrangian upper bound as well as the pegging result for pruning, and at each terminal subproblem solve MKP exactly by invoking MULKNAP code developed by Pisinger [Pisinger, D., 1999. An exact algorithm for large multiple knapsack problems. European Journal of Operational Research 114, 528–541]. As a result, we are able to solve almost all test problems with up to 32,000 items and 50 knapsacks within a few seconds on an ordinary computing environment, although the algorithm remains some weakness for small instances with relatively many knapsacks.     

A generalized bottleneck assignment problem

A solution procedure is presented for a generalization of the standard bottleneck assignment problem in which a secondary criterion is automatically provided. A partitioning problem is modeled by this bottleneck problem to provide an example of its application.     

On the exact separation of mixed integer knapsack cuts

During the last decades, much research has been conducted on deriving classes of valid inequalities for mixed integer knapsack sets, which we call knapsack cuts. Bixby et?al. (The sharpest cut: the impact of Manfred Padberg and his work. MPS/SIAM Series on Optimization, pp. 309?C326, 2004) empirically observe that, within the context of branch-and-cut algorithms to solve mixed integer programming problems, the most important inequalities are knapsack cuts derived by the mixed integer rounding (MIR) procedure. In this work we analyze this empirical observation by developing an algorithm to separate over the convex hull of a mixed integer knapsack set. The main feature of this algorithm is a specialized subroutine for optimizing over a mixed integer knapsack set which exploits dominance relationships. The exact separation of knapsack cuts allows us to establish natural benchmarks by which to evaluate specific classes of them. Using these benchmarks on MIPLIB 3.0 and MIPLIB 2003 instances we analyze the performance of MIR inequalities. Our computations, which are performed in exact arithmetic, are surprising: In the vast majority of the instances in which knapsack cuts yield bound improvements, MIR cuts alone achieve over 87% of the observed gain.     

Reducing the elastic generalized assignment problem to the standard generalized assignment problem

The elastic generalized assignment problem (eGAP) is a natural extension of the generalized assignment problem (GAP) where the capacities are not fixed but can be adjusted; this adjustment can be expressed by continuous variables. These variables might be unbounded or restricted by a lower or upper bound, respectively. This paper concerns techniques aiming at reducing several variants of eGAP to GAP, which enables us to employ standard approaches for the GAP. This results in a heuristic, which can be customized in order to provide solutions having an objective value arbitrarily close to the optimal.     

A survey of algorithms for the generalized assignment problem

This paper surveys algorithms for the well-known problem of finding the minimum cost assignment of jobs to agents so that each job is assigned exactly once and agents are not overloaded. All approaches seem to be based on branch-and-bound with bound supplied through heuristics and through relaxations of the primal problem formulation. From the survey one can select building blocks for the design of one's own tailor-made algorithm. The survey also reveals that although just about every mathematical programming technique was tried on this problem, there is still a lack of a representative set of test problems on which competing enumeration algorithms can be compared, as well as a shortage of effective heuristics.     

A branch and bound algorithm for the generalized assignment problem

This paper describes what is termed the generalized assignment problem. It is a generalization of the ordinary assignment problem of linear programming in which multiple assignments of tasks to agents are limited by some resource available to the agents. A branch and bound algorithm is developed that solves the generalized assignment problem by solving a series of binary knapsack problems to determine the bounds. Computational results are cited for problems with up to 4 000 0–1 variables, and comparisons are made with other algorithms.This research was partly supported by ONR Contracts N00014-67-A-0126-0008 and N00014-67-A-0126-0009 with the Center for Cybernetic Studies, The University of Texas.     

Bees algorithm for generalized assignment problem

Bees algorithm (BA) is a new member of meta-heuristics. BA tries to model natural behavior of honey bees in food foraging. Honey bees use several mechanisms like waggle dance to optimally locate food sources and to search new ones. This makes them a good candidate for developing new algorithms for solving optimization problems. In this paper a brief review of BA is first given, afterwards development of a BA for solving generalized assignment problems (GAP) with an ejection chain neighborhood mechanism is presented. GAP is a NP-hard problem. Many meta-heuristic algorithms were proposed for its solution. So far BA is generally applied to continuous optimization. In order to investigate the performance of BA on a complex integer optimization problem, an attempt is made in this paper. An extensive computational study is carried out and the results are compared with several algorithms from the literature.     

Upper and lower bounding procedures for the multiple knapsack assignment problem

We formulate the multiple knapsack assignment problem (MKAP) as an extension of the multiple knapsack problem (MKP), as well as of the assignment problem. Except for small instances, MKAP is hard to solve to optimality. We present a heuristic algorithm to solve this problem approximately but very quickly. We first discuss three approaches to evaluate its upper bound, and prove that these methods compute an identical upper bound. In this process, reference capacities are derived, which enables us to decompose the problem into mutually independent MKPs. These MKPs are solved euristically, and in total give an approximate solution to MKAP. Through numerical experiments, we evaluate the performance of our algorithm. Although the algorithm is weak for small instances, we find it prospective for large instances. Indeed, for instances with more than a few thousand items we usually obtain solutions with relative errors less than 0.1% within one CPU second.     

LP based heuristics for the multiple knapsack problem with assignment restrictions

Starting with a problem in wireless telecommunication, we are led to study the multiple knapsack problem with assignment restrictions. This problem is NP-hard. We consider special cases and their computational complexity. We present both randomized and deterministic LP based algorithms, and show both theoretically and computationally their usefulness for large-scale problems.     

Fast separation for the three-index assignment problem

A critical step in a cutting plane algorithm is separation, i.e., establishing whether a given vector x violates an inequality belonging to a specific class. It is customary to express the time complexity of a separation algorithm in the number of variables n. Here, we argue that a separation algorithm may instead process the vector containing the positive components of x,  denoted as supp(x),  which offers a more compact representation, especially if x is sparse; we also propose to express the time complexity in terms of |supp(x)|. Although several well-known separation algorithms exploit the sparsity of x,  we revisit this idea in order to take sparsity explicitly into account in the time-complexity of separation and also design faster algorithms. We apply this approach to two classes of facet-defining inequalities for the three-index assignment problem, and obtain separation algorithms whose time complexity is linear in |supp(x)| instead of n. We indicate that this can be generalized to the axial k-index assignment problem and we show empirically how the separation algorithms exploiting sparsity improve on existing ones by running them on the largest instances reported in the literature.     

A polyhedral study of the semi-continuous knapsack problem

We study the convex hull of the feasible set of the semi-continuous knapsack problem, in which the variables belong to the union of two intervals. Such structure arises in a wide variety of important problems, e.g. blending and portfolio selection. We show how strong inequalities valid for the semi-continuous knapsack polyhedron can be derived and used in a branch-and-cut scheme for problems with semi-continuous variables. To demonstrate the effectiveness of these inequalities, which we call collectively semi-continuous cuts, we present computational results on real instances of the unit commitment problem, as well as on a number of randomly generated instances of linear programming with semi-continuous variables.     

An algorithm for the generalized quadratic assignment problem

This paper reports on a new algorithm for the Generalized Quadratic Assignment problem (GQAP). The GQAP describes a broad class of quadratic integer programming problems, wherein M pair-wise related entities are assigned to N destinations constrained by the destinations’ ability to accommodate them. This new algorithm is based on a Reformulation Linearization Technique (RLT) dual ascent procedure. Experimental results show that the runtime of this algorithm is as good or better than other known exact solution methods for problems as large as M=20 and N=15. Current address of P.M. Hahn: 2127 Tryon Street, Philadelphia, PA 19146-1228, USA.     

An approximation algorithm for the generalized assignment problem

The generalized assignment problem can be viewed as the following problem of scheduling parallel machines with costs. Each job is to be processed by exactly one machine; processing jobj on machinei requires timep _ij and incurs a cost ofc _ij ; each machinei is available forT _i time units, and the objective is to minimize the total cost incurred. Our main result is as follows. There is a polynomial-time algorithm that, given a valueC, either proves that no feasible schedule of costC exists, or else finds a schedule of cost at mostC where each machinei is used for at most 2T _i time units.We also extend this result to a variant of the problem where, instead of a fixed processing timep _ij , there is a range of possible processing times for each machine—job pair, and the cost linearly increases as the processing time decreases. We show that these results imply a polynomial-time 2-approximation algorithm to minimize a weighted sum of the cost and the makespan, i.e., the maximum job completion time. We also consider the objective of minimizing the mean job completion time. We show that there is a polynomial-time algorithm that, given valuesM andT, either proves that no schedule of mean job completion timeM and makespanT exists, or else finds a schedule of mean job completion time at mostM and makespan at most 2T. Research partially supported by an NSF PYI award CCR-89-96272 with matching support from UPS, and Sun Microsystems, and by the National Science Foundation, the Air Force Office of Scientific Research, and the Office of Naval Research, through NSF grant DMS-8920550.Research supported in part by a Packard Fellowship, a Sloan Fellowship, an NSF PYI award, and by the National Science Foundation, the Air Force Office of Scientific Research, and the Office of Naval Research, through NSF grant DMS-8920550.     

A new exact discrete linear reformulation of the quadratic assignment problem

The quadratic assignment problem (QAP) is a challenging combinatorial problem. The problem is NP-hard and in addition, it is considered practically intractable to solve large QAP instances, to proven optimality, within reasonable time limits. In this paper we present an attractive mixed integer linear programming (MILP) formulation of the QAP. We first introduce a useful non-linear formulation of the problem and then a method of how to reformulate it to a new exact, compact discrete linear model. This reformulation is efficient for QAP instances with few unique elements in the flow or distance matrices. Finally, we present optimal results, obtained with the discrete linear reformulation, for some previously unsolved instances (with the size n = 32 and 64), from the quadratic assignment problem library, QAPLIB.     

The elastic generalized assignment problem

The generalized assignment problem (GAP) has been studied by numerous researchers over the past 30 years or so. Simply stated, one must find a minimum-cost assignment of tasks to agents such that each task is assigned to exactly one agent and such that each agent's resource capacity is honoured. The problem is known to be NP-hard. In this paper, we study the elastic generalized assignment problem (EGAP). The elastic version of GAP allows agent resource capacity to be violated at additional cost. Another version allows undertime costs to be assessed as well if an agent's resource capacity is not used to its full extent. The EGAP is also NP-hard. We describe a special-purpose branch-and-bound algorithm that utilizes linear programming cuts, feasible solution generators, Lagrangean relaxation and subgradient optimization. We present computational results on a large collection of randomly generated ‘hard’ problems with up to 4000 binary variables.     

A polyhedral study of the cardinality constrained knapsack problem

 A cardinality constrained knapsack problem is a continuous knapsack problem in which no more than a specified number of nonnegative variables are allowed to be positive. This structure occurs, for example, in areas such as finance, location, and scheduling. Traditionally, cardinality constraints are modeled by introducing auxiliary 0-1 variables and additional constraints that relate the continuous and the 0-1 variables. We use an alternative approach, in which we keep in the model only the continuous variables, and we enforce the cardinality constraint through a specialized branching scheme and the use of strong inequalities valid for the convex hull of the feasible set in the space of the continuous variables. To derive the valid inequalities, we extend the concepts of cover and cover inequality, commonly used in 0-1 programming, to this class of problems, and we show how cover inequalities can be lifted to derive facet-defining inequalities. We present three families of non-trivial facet-defining inequalities that are lifted cover inequalities. Finally, we report computational results that demonstrate the effectiveness of lifted cover inequalities and the superiority of the approach of not introducing auxiliary 0-1 variables over the traditional MIP approach for this class of problems. Received: March 13, 2003 Published online: April 10, 2003 Key Words. mixed-integer programming – knapsack problem – cardinality constrained programming – branch-and-cut     

GRASP with path-relinking for the generalized quadratic assignment problem

The generalized quadratic assignment problem (GQAP) is a generalization of the NP-hard quadratic assignment problem (QAP) that allows multiple facilities to be assigned to a single location as long as the capacity of the location allows. The GQAP has numerous applications, including facility design, scheduling, and network design. In this paper, we propose several GRASP with path-relinking heuristics for the GQAP using different construction, local search, and path-relinking procedures. We introduce a novel approximate local search scheme, as well as a new variant of path-relinking that deals with infeasibilities. Extensive experiments on a large set of test instances show that the best of the proposed variants is both effective and efficient.