Average-weight-controlled bin-oriented heuristics for the one-dimensional bin-packing problem

Bin-oriented heuristics for one-dimensional bin-packing problem construct solutions by packing one bin at a time. Several such heuristics consider two or more subsets for each bin and pack the one with the largest total weight. These heuristics sometimes generate poor solutions, due to a tendency to use many small items early in the process. To address this problem, we propose a method of controlling the average weight of items packed by bin-oriented heuristics. Constructive heuristics and an improvement heuristic based on this approach are introduced. Additionally, reduction methods for bin-oriented heuristics are presented. The results of an extensive computational study show that: (1) controlling average weight significantly improves solutions and reduces computation time of bin-oriented heuristics; (2) reduction methods improve solutions and processing times of some bin-oriented heuristics; and (3) the new improvement heuristic outperforms all other known complex heuristics, in terms of both average solution quality and computation time.     

The quadratic three-dimensional assignment problem: Exact and approximate solution methods

This paper reports on algorithm development for solving the quadratic three-dimensional assignment problem (Q3AP). The Q3AP arises, for example, in the implementation of a hybrid ARQ (automatic repeat request) scheme for enriching diversity among multiple packet re-transmissions, by optimizing the mapping of data bits to modulation symbols. Typical practical problem sizes would be 8, 16, 32 and 64.     

An approximate solution of one-dimensional piston problem

A new theory of shock dynamics has been developed in the form of a finite number of compatibility conditions along shock rays. It has been used to study the growth or decay of shock strength for accelerating or decelerating piston starting with a nonzero piston velocity. The results show good agreement with those obtained by Harten's high resolution TVD scheme.     

An approximate solution algorithm for the one-dimensional online median problem

The online median problem consists in finding a sequence of incremental solutions of the k-median problem with k increasing. A particular case of the problem is considered: the clients and facilities are located on the real line. The best algorithm available for the one-dimensional case has competitive ratio 8. We give an improved 5.83-competitive algorithm.     

Exact and approximate solutions to the multisource weber problem

The problem considered is the choice of locations form sources so as to minimize the sum of weighted distances betweenn fixed sinks and the source closest to each sink. The weights represent the amounts to be shipped between the sinks and their respective sources; the allowable source locations are free of restriction. An algorithm for the approximate solution of the problem, and computational experience with it, are discussed first. A branch-and-bound algorithm for exact solution of the problem is then developed, and computational experience with it is described.For a more detailed discussion of the analyses contained in the present paper, the computational results, and for detailed program listings, the reader is referred to [8]. Tapes for the two programs discussed in the present paper are available at cost of reproduction from Program Analysis Division, Institute for Defense Analyses, Arlington, Virginia.     

Energetic reasoning and bin-packing problem, for bounding a parallel machine scheduling problem

This paper deals with an extension of energetic reasoning, using some efficient lower bounds of the bin-packing problem, to get tight lower bounds for the P|r _i , q _i |C _max. The link between P||C _max and bin-packing problem is well-known. Our purpose is to extend the use of efficient lower bounds of the bin-packing problem to P|r _i , q _i |C _max. We focus on some time-intervals, to compute the mandatory parts of activities within this time-interval and then to deduce an associated bin-packing instance. Thus, lower bounds of the bin-packing problem are used to get new satisfiability tests for the parallel machine problem. We also propose to extend the classical time-bound adjustments of release dates and deadlines to efficiently use bin-packing lower bounds. Experimental results that prove the efficiency of our approach on several kind of instances are reported.     

A morph-based simulated annealing heuristic for a modified bin-packing problem

This paper presents a local-search heuristic, based on the simulated annealing (SA) algorithm for a modified bin-packing problem (MBPP). The objective of the MBPP is to assign items of various sizes to a fixed number of bins, such that the sum-of-squared deviation (across all bins) from the target bin workload is minimized. This problem has a number of practical applications which include the assignment of computer jobs to processors, the assignment of projects to work teams, and infinite-loading machine scheduling problems. The SA-based heuristic we developed uses a morph-based search procedure when looking for better allocations. In a large computational study we evaluated 12 versions of this new heuristic, as well as two versions of a previously published SA-based heuristic that used a completely random search. The primary performance measure for this evaluation was the mean percent above the best known objective value (MPABKOV). Since the MPABKOV associated with the best version of the random-search SA heuristic was more than 290 times larger than that of the best version of the morph-based SA heuristic, we conclude that the morphing process is a significant enhancement to SA algorithms for these problems.     

Exact methods for the knapsack problem and its generalizations

A unified approach and a summary of the most important results concerned with exact methods for solving the (binary) knapsack problem and its generalizations are given. We stress the importance of dual methods for solving linear programming relaxations of the considered problems. Two ways of generalization of the knapsack problem are described. If the special ordered sets are added, then the multiple-choice knapsack problem is obtained. If the constraints have the nested structure, then we get the nested knapsack problem. Also the multiple-choice nested knapsack problem is discussed.     

Exact and heuristic methods for the selective maintenance problem

We present in this paper, new resolution methods for the selective maintenance problem. This problem consists in finding the best choice of maintenance actions to be performed on a multicomponent system, so as to maximize the system reliability, within a time window of a limited duration. When the number of components of the system is important, this combinatorial problem is not easy to solve, in particular because of the nonlinear objective function modeling the system reliability. This problem did not receive much attention yet. Consequently, rare are the effective resolution methods that are offered to the user. We thus developed heuristics and an exact method based on a branch and bound procedure, which we apply to various system configurations. We compare the obtained results, and we evaluate the best method to be used in various situations.     

Sequential heuristic for the two-dimensional bin-packing problem

A heuristic approach for the two-dimensional bin-packing problem is proposed. The algorithm is based on the sequential heuristic procedure that generates each pattern to produce some items and repeats until all items are produced. Both guillotine and non-guillotine patterns can be used. Each pattern is obtained from calling a pattern-generation procedure, where the objective is to maximize the pattern value. The item values are adjusted after the generation of each pattern using a value correction formula. The algorithm is compared with five published algorithms, using 50 groups of benchmark instances. The results indicate that the algorithm is the most efficient in improving solution quality.     

Ranking lower bounds for the bin-packing problem

In this paper, we evaluate different known lower bounds for the bin-packing problem including linear programming relaxation (LP), Lagrangean relaxation (LR), Lagrangean decomposition (LD) and the Martello–Toth (MT) [Martello, S., Toth, P., Knapsack Problems: Algorithms and Computer Implementations, Wiley, New York, 1990] lower bounds. We give conditions under which Lagrangean bounds are superior to the LP bound, show that Lagrangean decomposition (LD) yields the same bound as Lagrangean relaxation (LR) and prove that the MT lower bound is a Lagrangean bound evaluated at a finite set of Lagrange multipliers; hence, it is no better than the LR and LD lower bounds.     

The pricing problem. Part I: Exact and approximate algorithms

In the article we consider the pricing problem and show it to be NP-hard in the strong sense. Some exact and approximate algorithms are developed based on decomposition, genetic local search, and tabu search. The results of some computational experiments are provided.     

Exact solutions of the phase transition problem in a one-dimensional model case

Solutions of the phase transition problem are obtained explicitly in a one-dimensional model case for both positive and zero surface tension coefficients. The dependence of the equilibrium states on the parameters of the problem is investigated.     

The traveling purchaser problem with stochastic prices: Exact and approximate algorithms

The paper formulates an extension of the traveling purchaser problem where multiple types of commodities are sold at spatially distributed locations with stochastic prices (each following a known probability distribution). A purchaser’s goal is to find the optimal routing and purchasing strategies that minimize the expected total travel and purchasing costs needed to purchase one unit of each commodity. The purchaser reveals the actual commodity price at a seller upon arrival, and then either purchases the commodity at the offered price, or rejects the price and visits a next seller. In this paper, we propose an exact solution algorithm based on dynamic programming, an iterative approximate algorithm that yields bounds for the minimum total expected cost, and a greedy heuristic for fast solutions to large-scale applications. We analyze the characteristics of the problem and test the computational performance of the proposed algorithms. The numerical results show that the approximate and heuristic algorithms yield near-optimum strategies and very good estimates of the minimum total cost.     

Exact and inexact penalty methods for the generalized bilevel programming problem

We consider a hierarchical system where a leader incorporates into its strategy the reaction of the follower to its decision. The follower's reaction is quite generally represented as the solution set to a monotone variational inequality. For the solution of this nonconvex mathematical program a penalty approach is proposed, based on the formulation of the lower level variational inequality as a mathematical program. Under natural regularity conditions, we prove the exactness of a certain penalty function, and give strong necessary optimality conditions for a class of generalized bilevel programs.     

Exact and hybrid methods for the multiperiod field service routing problem

This article deals with a particular class of routing problem, consisting of the planning and routing of technicians in the field. This problem has been identified as a multiperiod, multidepot uncapacitated vehicle routing problem with specific constraints that we call the multiperiod field service routing problem (MPFSRP). We propose a set covering formulation of the problem for the column generation technique and we develop an exact branch and price solution method for small-sized instances. We also propose several heuristic versions for larger instances. We present the results of experiments on realistic data adapted from an industrial application.     

Inclusion-exclusion: Exact and approximate

It is often required to find the probability of the union of givenn eventsA ₁ ,...,A _n . The answer is provided, of course, by the inclusion-exclusion formula: Pr(A _i )= _i – _i<j Pr(A _i A _j )±.... Unfortunately, this formula has exponentially many terms, and only rarely does one manage to carry out the exact calculation. From a computational point of view, finding the probability of the union is an intractable, #P-hard problem, even in very restricted cases. This state of affairs makes it reasonable to seek approximate solutions that are computationally feasible. Attempts to find such approximate solutions have a long history starting already with Boole [1]. A recent step in this direction was taken by Linial and Nisan [4] who sought approximations to the probability of the union, given the probabilities of allj-wise intersections of the events forj=1,...k. The developed a method to approximate Pr(A _i ), from the above data with an additive error of exp . In the present article we develop an expression that can be computed in polynomial time, that, given the sums _|S|=j Pr( _iS A _i ) forj=1,...k, approximates Pr(A _i ) with an additive error of exp . This error is optimal, up to the logarithmic factor implicit in the notation.The problem of enumerating satisfying assignments of a boolean formula in DNF formF=v _l ^m C _i is an instance of the general problem that had been extensively studied [7]. HereA _i is the set of assignments that satisfyC _i , and Pr( _iS A _i )=a _S /2ⁿ where _iS C _i is satisfied bya _S assignments. Judging from the general results, it is hard to expect a decent approximation ofF's number of satisfying assignments, without knowledge of the numbersa _S for, say, all cardinalities . Quite surprisingly, already the numbersa _S over |S|log(n+1)uniquely determine the number of satisfying assignments for F.We point out a connection between our work and the edge-reconstruction conjecture. Finally we discuss other special instances of the problem, e.g., computing permanents of 0,1 matrices, evaluating chromatic polynomials of graphs and for families of events whose VC dimension is bounded.Work supported in part by a grant of the Binational Israel-US Science Foundation.Work supported in part by a grant of the Binational Israel-US Science Foundation and by the Israel Science Foundation.     

Efficient algorithms for the offline variable sized bin-packing problem

We addresses a variant of the classical one dimensional bin-packing problem where several types of bins with unequal sizes and costs are presented. Each bin-type includes limited and/or unlimited identical bins. The goal is to minimize the total cost of bins needed to store a given set of items, each item with some space requirements. Four new heuristics to solve this problem are proposed, developed and compared. The experiments results show that higher quality solutions can be obtained using the proposed algorithms.