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 branch-and-bound algorithm for hard multiple knapsack problems

The multiple knapsack problem (MKP) is a classical combinatorial optimization problem. A recent algorithm for some classes of the MKP is bin-completion, a bin-oriented, branch-and-bound algorithm. In this paper, we propose path-symmetry and path-dominance criteria for pruning nodes in the MKP branch-and-bound search space. In addition, we integrate the ??bound-and-bound?? upper bound validation technique used in previous MKP solvers. We show experimentally that our new MKP solver, which successfully integrates dominance based pruning, symmetry breaking, and bound-and-bound, significantly outperforms previous solvers on some classes of hard problem instances.     

An exact algorithm for the knapsack sharing problem with common items

We are concerned with a variation of the knapsack problem as well as of the knapsack sharing problem, where we are given a set of n items and a knapsack of a fixed capacity. As usual, each item is associated with its profit and weight, and the problem is to determine the subset of items to be packed into the knapsack. However, in the problem there are s players and the items are divided into s + 1 disjoint groups, N_k (k = 0, 1, … , s). The player k is concerned only with the items in N₀ ∪ N_k, where N₀ is the set of ‘common’ items, while N_k represents the set of his own items. The problem is to maximize the minimum of the profits of all the players. An algorithm is developed to solve this problem to optimality, and through a series of computational experiments, we evaluate the performance of the developed algorithm.     

An exact algorithm for team orienteering problems

Optimising routing of vehicles constitutes a major logistic stake in many industrial contexts. We are interested here in the optimal resolution of special cases of vehicle routing problems, known as team orienteering problems. In these problems, vehicles are guided by a reward that can be collected from customers, while the length of routes is limited. The main difference with classical vehicle routing problems is that not all customers have to be visited. The solution method we propose here is based on a Branch & Price algorithm. It is, as far as we know, the first exact method proposed for such problems, except for a preliminary work from Gueguen (Methodes de résolution exacte pour problémes de tournées de véhicules. Thése de doctorat, école Centrale Paris 1999) and a work from Butt and Ryan (Comput Oper Res 26(4):427–441 1999). It permits to solve instances with up to 100 customers.      

An O(n) algorithm for quadratic knapsack problems

An algorithm is presented which solves bounded quadratic optimization problems with n variables and one linear constraint in at most O(n) steps. The algorithm is based on a parametric approach combined with well-known ideas for constructing efficient algorithms. It improves an O(n log n) algorithm which has been developed for a more restricted case of the problem.     

An asymptotically exact polynomial algorithm for equipartition problems

We describe an approximate algorithm for a special ‘quadratic semi-assignment problem’ arising from ‘equipartition’ applications, where one wants to cluster n objects with given weights w_i into p classes, so as to minimize the variance of the class-weights. The algorithm can be viewed both as a list scheduling method and as a special case of a heuristic procedure, due to Nemhauser and Carlson, for quadratic semi-assignment problems. Our main result is that the relative approximation error is O(1/n) when p and r = (maxw_i)/(min w_i) are bounded.     

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.     

多背包问题的半定松驰算法

The multiple knapsack problem denoted by MKP (B,S,rn,n) can be defined as follows. A set B of n items and a set S of rn knapsacks are given such that each item j has a profit pi and weight wj,and each knapsack i has a capacity Ci. The goal is to find a subset of items of maximum profit such that they have a feasible packing in the knapsacks. MKP (B,S,m,n) is strongly NP-Complete and no polynomial time approximation algorithm can have an approximation ratio better than 0.5. In the last ten years,semi-definite programming has been empolyed to solve some combinatorial problems successfully. This paper firstly presents a semi-definite relaxation algorithm (MKPS) for MKP (B,S,rn,n). It is proved that MKPS have a approximation ratio better than 0. 5 for a subclass of MKP (B,S,m,n) with n≤100, m≤5 and max^nj=1{wj}/min^mi=1={Ci}≤2/3.     

An exact algorithm for the capacitated facility location problems with single sourcing

Facility location problems are often encountered in many areas such as distribution, transportation and telecommunication. We describe a new solution approach for the capacitated facility location problem in which each customer is served by a single facility. An important class of heuristic solution methods for these problems are Lagrangian heuristics which have been shown to produce high quality solutions and at the same time be quite robust. A primal heuristic, based on a repeated matching algorithm which essentially solves a series of matching problems until certain convergence criteria are satisfied, is incorporated into the Lagrangian heuristic. Finally, a branch-and-bound method, based on the Lagrangian heuristic is developed, and compared computationally to the commercial code CPLEX. The computational results indicate that the proposed method is very efficient.     

An algorithm for solving large capacitated warehouse location problems

In this paper we present a lower bound for the capacitated warehouse location problem based upon lagrangean relaxation of a mixed-integer formulation of the problem. Feasible solution exclusion constraints are used together with problem reduction tests derived from both the original problem and the lagrangean relaxation.By incorporating the lower bound and the reduction tests into a tree search procedure we are able to solve problems involving up to 500 potential warehouse locations and 1000 customers.     

An optimization algorithm for a penalized knapsack problem

We study a variation of the knapsack problem in which each item has a profit, a weight and a penalty; the sum of profits of the selected items minus the largest penalty associated with the selected items must be maximized. We present an ILP formulation and an exact optimization algorithm.     

An efficient algorithm for the Lagrangean dual of nonlinear knapsack problems with additional nested constraints

This paper presents an efficient algorithm for solving the Lagrangean dual of nonlinear knapsack problems with additional nested constraints. The dual solution provides a feasible primal solution (if it exists) and associated lower and upper bounds on the optimal objective function value of the primal problem. Computational experience is cited indicating computation time, number of dual iterations, and “tightness” of the bounds.     

An exact algorithm for subgraph homeomorphism

The subgraph homeomorphism problem is to decide if there is an injective mapping of the vertices of a pattern graph into vertices of a host graph so that the edges of the pattern graph can be mapped into (internally) vertex-disjoint paths in the host graph. The restriction of subgraph homeomorphism where an injective mapping of the vertices of the pattern graph into vertices of the host graph is already given in the input instance is termed fixed-vertex subgraph homeomorphism.We show that fixed-vertex subgraph homeomorphism for a pattern graph on p vertices and a host graph on n vertices can be solved in time 2^n−pn^O(1) or in time 3^n−pn^O(1) and polynomial space. In effect, we obtain new non-trivial upper bounds on the time complexity of the problem of finding k vertex-disjoint paths and general subgraph homeomorphism.     

An exact algorithm for graph partitioning

An exact algorithm is presented for solving edge weighted graph partitioning problems. The algorithm is based on a branch and bound method applied to a continuous quadratic programming formulation of the problem. Lower bounds are obtained by decomposing the objective function into convex and concave parts and replacing the concave part by an affine underestimate. It is shown that the best affine underestimate can be expressed in terms of the center and the radius of the smallest sphere containing the feasible set. The concave term is obtained either by a constant diagonal shift associated with the smallest eigenvalue of the objective function Hessian, or by a diagonal shift obtained by solving a semidefinite programming problem. Numerical results show that the proposed algorithm is competitive with state-of-the-art graph partitioning codes.     

An exact Block–Newton algorithm for solving fluid–structure interaction problems

In this Note, we introduce a partitioned Newton based method for solving nonlinear coupled systems arising in the numerical approximation of fluid–structure interaction problems. The originality of this Schur–Newton algorithm lies in the exact Jacobians evaluation involving the fluid–structure linearized subsystems which are here fully developed. To cite this article: M.Á. Fernández, M. Moubachir, C. R. Acad. Sci. Paris, Ser. I 336 (2003).     

An RQP algorithm using a differentiable exact penalty function for inequality constrained problems

In this paper we propose a recursive quadratic programming algorithm for nonlinear programming problems with inequality constraints that uses as merit function a differentiable exact penalty function. The algorithm incorporates an automatic adjustment rule for the selection of the penalty parameter and makes use of an Armijo-type line search procedure that avoids the need to evaluate second order derivatives of the problem functions. We prove that the algorithm possesses global and superlinear convergence properties. Numerical results are reported.     

An iterative algorithm for large size least-squares constrained regularization problems

In this paper we propose an iterative algorithm to solve large size linear inverse ill posed problems. The regularization problem is formulated as a constrained optimization problem. The dual Lagrangian problem is iteratively solved to compute an approximate solution. Before starting the iterations, the algorithm computes the necessary smoothing parameters and the error tolerances from the data.The numerical experiments performed on test problems show that the algorithm gives good results both in terms of precision and computational efficiency.     

A Bound and Bound algorithm for the zero-one multiple knapsack problem

By the term “Bound and Bound” we define a particular tree-search technique for the ILP, which, for a maximization problem, makes use of a lower bound to determine the branches to follow in the decision tree. This technique is applied to the solution of the Zero-One Multiple Knapsack Problem and an algorithm is derived; an illustrative example of the procedure is provided. We present extensive computational results showing that the method is capable of solving problems up to 4 knapsacks and 200 variables with running times considerably smaller than those of the most commonly utilized algorithms.     

Using the idea of expanded core for the exact solution of bi-objective multi-dimensional knapsack problems

We propose a methodology for obtaining the exact Pareto set of Bi-Objective Multi-Dimensional Knapsack Problems, exploiting the concept of core expansion. The core concept is effectively used in single objective multi-dimensional knapsack problems and it is based on the “divide and conquer” principle. Namely, instead of solving one problem with n variables we solve several sub-problems with a fraction of n variables (core variables). In the multi-objective case, the general idea is that we start from an approximation of the Pareto set (produced with the Multi-Criteria Branch and Bound algorithm, using also the core concept) and we enrich this approximation iteratively. Every time an approximation is generated, we solve a series of appropriate single objective Integer Programming (IP) problems exploring the criterion space for possibly undiscovered, new Pareto Optimal Solutions (POS). If one or more new POS are found, we appropriately expand the already found cores and solve the new core problems. This process is repeated until no new POS are found from the IP problems. The paper includes an educational example and some experiments.