This paper addresses a single machine total weighted tardiness (TWT) batch-scheduling problem in which jobs have release dates, nonidentical sizes, and are compatible between each other. We propose two integer linear programming models: the first one is a time-indexed formulation (TIF), and the second is an innovative time-size-indexed formulation (TSIF). Although TIF clearly outperforms the existing formulation for the problem, TSIF is capable of producing much stronger bounds in practice. The latter also enables us to develop an efficient column-generation (CG) algorithm. The pricing subproblem corresponds to a resource-constrained shortest path problem that is solved using a bucket graph–based labeling algorithm. The solutions of such a subproblem may contain cycles (reprocessing of jobs), and thus, a memory mechanism called dynamic arc-based ng-sets is employed in the labeling with a view toward avoiding some of them. Moreover, we also implement a preprocessing scheme based on Lagrangian relaxation to perform variable fixing. Extensive computational experiments were carried out in 810 benchmark instances. The proposed CG algorithm is capable of solving instances with up to 100 jobs to optimality. In addition, we believe that this is the first exact approach for a TWT batch-scheduling variant capable of systematically solving instances with up to 50 jobs. High-quality results are also reported for three special cases of the problem—more precisely, when (i) the penalty weights are unitary, (ii) there are no release dates, and (iii) all due dates are set to zero and, hence, the objective becomes equivalent to minimizing the weighted completion time. Summary of Contribution: This paper provides the first exact algorithm for a standard variant of a batch-scheduling total weighted tardiness problem that can solve instances with up to 100 jobs to optimality, a considerable leap with respect to previous works. In particular, we propose a time-indexed formulation that has the advantage of being relatively simple to implement, and yet we show that it is not theoretically dominated by the other innovative formulation proposed in the paper referred to as the time-size-indexed formulation (TSIF). Moreover, we present a Lagrangian approach to quickly fix variables and an iterative column-generation (CG) procedure over a Dantzig–Wolfe decomposition of TSIF that combines an efficient pricing algorithm with a dynamic scheme to adjust the subproblem constraints. The proposed CG approach is capable of producing very strong bounds for the problem as well as for some of its special cases.

This work presents an improved branch-cut-and-price algorithm for the identical parallel machine scheduling problem minimizing a generic function of the job completion times. A new family of cuts is proposed to strengthen the arc-time-indexed formulation, along with an efficient separation algorithm. Also, the projection of the arc-time-indexed into a time-indexed formulation is introduced to take advantage of the variable fixings performed in the larger variable space. The improved algorithm was capable of solving 146 out of 150 instances in the literature, with 12 being solved for the first time. Also, the running time for the 134 previously solved instances decreased by 95.7% on the average.

Major advances were recently obtained in the exact solution of Vehicle Routing Problems (VRPs). Sophisticated Branch-Cut-and-Price (BCP) algorithms for some of the most classical VRP variants now solve many instances with up to a few hundreds of customers. However, adapting and reimplementing those successful algorithms for other variants can be a very demanding task. This work proposes a BCP solver for a generic model that encompasses a wide class of VRPs. It incorporates the key elements found in the best recent VRP algorithms: ng-path relaxation, rank-1 cuts with limited memory, and route enumeration; all generalized through the new concept of “packing set”. This concept is also used to derive a new branch rule based on accumulated resource consumption and to generalize the Ryan and Foster branch rule. Extensive experiments on several variants show that the generic solver has an excellent overall performance, in many problems being better than the best existing specific algorithms. Even some non-VRPs, like bin packing, vector packing and generalized assignment, can be modeled and effectively solved.

Primal heuristics have become essential components in mixed integer programming (MIP) solvers. Extending MIP-based heuristics, our study outlines generic procedures to build primal solutions in the context of a branch-and-price approach and reports on their performance. Our heuristic decisions carry on variables of the Dantzig–Wolfe reformulation, the motivation being to take advantage of a tighter linear programming relaxation than that of the original compact formulation and to benefit from the combinatorial structure embedded in these variables. We focus on the so-called diving methods that use reoptimization after each linear programming rounding. We explore combinations with diversification-intensification paradigms such as limited discrepancy search, sub-MIP, local branching, and strong branching. The dynamic generation of variables inherent to a column generation approach requires specific adaptation of heuristic paradigms. We manage to use simple strategies to get around these technical issues. Our numerical results on generalized assignment, cutting stock, and vertex-coloring problems set new benchmarks, highlighting the performance of diving heuristics as generic procedures in a column generation context and producing better solutions than state-of-the-art specialized heuristics in some cases.

International audience

The quadratic assignment problem (QAP) is a combinatorial optimization problem that arises in many real-world applications, such as equipment allocation in industry. The QAP is NP-hard and, in practice, one of the hardest combinatorial optimization problems to solve to optimality. Exact solutions of QAP are typically obtained by the branch-and-bound method. This method, however, potentially requires a high computational effort, and the use of good lower bounds is essential to prune the search tree. Branch-and-bound algorithms that use the dual-ascent procedure based on the level-2 reformulation linearization technique (RLT2) belong to the state of the art on exactly solving QAP. In this work, we propose a parallel implementation of that branch-and-bound algorithm. Our approach uses the Auction Algorithm of Bertsekas and Castañon to solve the linear assignment problems of RLT2, which allows us to take advantage of the massive parallel environment of graphics processing units to speed up the lower bound computation and implement some memory optimization techniques to address large-size problems. We report experimental results that show significant execution time reductions compared to previous works and allow us to provide, for the first time, exact solutions for two instances of QAP: tai35b and tai40b.

This paper addresses the close-enough traveling salesman problem. In this problem, rather than visiting the vertex (customer) itself, the salesman must visit a specific region containing such vertex. To solve this problem, we propose a simple yet effective exact algorithm, based on branch-and-bound and second order cone programming. The proposed algorithm was tested in 824 instances suggested in the literature. Optimal solutions are obtained for open problems with up to a thousand vertices. We consider instances both in two- and three-dimensional space.

Abstract The latest trends in high performance computing systems show an increasing demand on the use of a large scale multicore system in an efficient way so that high compute‐intensive applications can be executed reasonably well. However, the exploitation of the degree of parallelism available at each multicore component can be limited by the poor utilization of the memory hierarchy. Actually, the multicore architecture introduces some distinct features that are already observed in shared memory and distributed environments. One example is that subsets of cores can share different subsets of memory. In order to achieve high performance, it is imperative that a careful allocation scheme of an application is carried out on the available cores, based on a scheduling specification that considers not only processors characteristics but also memory contention. This paper proposes a multicore cluster representation that captures relevant performance characteristics in multicores systems such as the influence of memory hierarchy and contention on application performance. Improved performance was achieved by a branch‐and‐bound application applied to the partitioning sets problem that incorporated a memory aware load balancing strategy based on the proposed multicore cluster representation. An in‐depth analysis on this application execution showed its applicability to modern systems. Copyright © 2014 John Wiley & Sons, Ltd.

The expansion of a telecommunications network faces two sources of uncertainty, which are the demand for traffic that will transit through the expanded network and the outsourcing cost that the network operator will have to pay to handle the traffic that exceeds the capacity of her network. The latter is determined by the future cost of telecommunications services, whose negative correlation with the total demand is empirically measured in the literature through the price elasticity of demand.

We study the robust constrained shortest path problem under resource uncertainty. After proving that the problem is in the strong sense for arbitrary uncertainty sets, we focus on budgeted uncertainty sets introduced by Bertsimas and Sim (2003) and their extension to variable uncertainty by Poss (2013). We apply classical techniques to show that the problem with capacity constraints can be solved in pseudopolynomial time. However, we prove that the problem with time windows is in the strong sense when is not fixed, using a reduction from the independent set problem. We introduce then new robust labels that yield dynamic programming algorithms for the problems with time windows and capacity constraints. The running times of these algorithms are pseudopolynomial when is fixed, exponential otherwise. We present numerical results for the problem with time windows which show the effectiveness of the label-setting algorithm based on the new robust labels. Our numerical results also highlight the reduction in price of robustness obtained when using variable budgeted uncertainty instead of classical budgeted uncertainty. © 2015 Wiley Periodicals, Inc.NETWORKS, Vol. 66(2), 98–111 2015

Abstract This article presents a robust branch‐cut‐and‐price algorithm for the heterogeneous fleet vehicle routing problem (HFVRP), vehicles may have distinct capacities and costs. The columns in the formulation are associated to q‐routes, a relaxation of capacitated elementary routes that makes the pricing problem solvable in pseudopolynomial time. Powerful new families of cuts are also proposed, which are expressed over a very large set of variables. Those cuts do not increase the complexity of the pricing subproblem. Experiments are reported where instances with up to 75 vertices were solved to optimality, a major improvement with respect to previous algorithms. © 2009 Wiley Periodicals, Inc. NETWORKS, 2009

Consider a website containing a collection of webpages with data such as in Yahoo or the Open Directory project. Each page is associated with a weight representing the frequency with which that page is accessed by users. In the tree hierarchy representation, accessing each page requires the user to travel along the path leading to it from the root. By enhancing the index tree with additional edges (hotlinks) one may reduce the access cost of the system. In other words, the hotlinks reduce the expected number of steps needed to reach a leaf page from the tree root, assuming that the user knows which hotlinks to take. The hotlink enhancement problem involves finding a set of hotlinks minimizing this cost. This article proposes the first exact algorithm for the hotlink enhancement problem. This algorithm runs in polynomial time for trees with logarithmic depth. Experiments conducted with real data show that significant improvement in the expected number of accesses per search can be achieved in websites using this algorithm. These experiments also suggest that the simple and much faster heuristic proposed previously by Czyzowicz et al. [2003] creates hotlinks that are nearly optimal in the time savings they provide to the user. The version of the hotlink enhancement problem in which the weight distribution on the leaves is unknown is discussed as well. We present a polynomial-time algorithm that is optimal for any tree for any depth.

Let us consider an ordered vector A[1:n]. If the cost of testing each position is similar, then the standard binary search is the best strategy to search the vector. This is true in both the average and worst case. However, if the costs are nonuniform, then the best strategy is not necessarily the standard binary search. The best algorithm to construct a strategy that minimizes the expected search cost runs in O(n 3 ) time and requires O(n 2 ) space. The same complexities hold for the best algorithm to construct a strategy that minimizes the worst case search cost. Here, we show how to efficiently construct search strategies that are at most at a constant factor from the optimal one. These constructions take linear time and use only linear space. For both the problem of minimizing the expected search cost, under uniform access probabilities, and the problem of minimizing the worst case search cost, we present algorithms that require O(n) space and give a $(2+\epsilon+o(1))$-approximated solution in O(n) time for any fixed value of $\epsilon > 0$.

The minimum-redundancy prefix code problem is to determine, for a given list W=[/spl omega//sub 1/,..., /spl omega//sub n/] of n positive symbol weights, a list L=[l/sub 1/,...,l/sub n/] of n corresponding integer codeword lengths such that /spl Sigma//sub i=1//sup n/ 2/sup -li//spl les/1 and /spl Sigma//sub i=1//sup n/ /spl omega//sub i/l/sub i/ is minimized. Let us consider the case where W is already sorted. In this case, the output list L can be represented by a list M=[m/sub 1/,..., m/sub H/], where m/sub l/, for l=1,...,H, denotes the multiplicity of the codeword length l in L and H is the length of the greatest codeword. Fortunately, H is proved to be O(min(log(1/p/sub 1/),n)), where p/sub 1/ is the smallest symbol probability, given by /spl omega//sub 1///spl Sigma//sub i=1//sup n/ /spl omega//sub i/. We present the Fast LazyHuff (F-LazyHuff), the Economical LazyHuff (E-LazyHuff), and the Best LazyHuff (B-LazyHuff) algorithms. F-LazyHuff runs in O(n) time but requires O(min(H/sup 2/, n)) additional space. On the other hand, E-LazyHuff runs in O(n+nlog(n/H)) time, requiring only O(H) additional space. Finally, B-LazyHuff asymptotically overcomes, the previous algorithms, requiring only O(n) time and O(H) additional space. Moreover, our three algorithms have the advantage of not writing over the input buffer during code calculation, a feature that is very useful in some applications.

Proposes an algorithm for finding a binary search tree that minimizes the worst-case cost when the access costs are non-uniform and depend on the last accessed key. For this kind of problem, which is commonly found when accessing data stored on magnetic or optical disks, we present an algorithm that finds an optimal search strategy with an expected running time of O(n/sup 2/log n), under some reasonable assumptions on the cost matrix. It is worth mentioning that the best previous algorithm for this problem runs in /spl Theta/(n/sup 3/) time.

Given an alphabet /spl Sigma/={a/sub 1/,...,a/sub n/) and a corresponding list of weights [w/sub 1/,...,w/sub n/], a Huffman code for this alphabet is a prefix code that minimizes the weighted length of a code string, defined to be /spl Sigma//sub i=1//sup n/w/sub i/l/sub i/, where l/sub i/ is the length of the code assigned to a/sub i/. We present ES-ParHuff, a work-efficient PRAM CREW algorithm for constructing Huffman codes. An important feature of the algorithm is its simplicity. This algorithm is a direct parallelization of Huffman's algorithm. ES-ParHuff runs in O(Hloglog(n/H)) time with O(n) work, where H is the length of the longest generated code.

[Summary form only given]. For data communication purposes, the initial parsing required by the static Huffman algorithm represents a big disadvantage. This is because the data must be transmitted on-line. As soon as the symbol arrives at the transmitter, it must be encoded and transmitted to the receiver. In these situations, adaptive Huffman codes have been largely used. This method determines the mapping from symbol alphabet to codewords based upon a running estimate of the alphabet symbol weights. The code is adaptive, just changing to remain optimal for the current estimates. Two methods have been presented in the literature for implementing dynamic Huffman coding. The first one was the FGK algorithm (Knuth, 1985) and the second was the /spl Lambda/ algorithm (Vitter, 1987). Vitter proved that the total number of bits D/sub t/ transmitted by the FGK algorithm for a message with t symbols is bounded below by S/sub t/-n+1, where S/sub t/ is the number of bits required by the static Huffman method and bounded above by 2S/sub t/+t-4n+2. Furthermore, he conjectured that D/sub t/ is bounded above by S/sub t/+O(t). We present an amortized analysis to prove this conjecture by showing that D/sub t//spl les/S/sub t/+2t-2k-[log min(k+1,n)], where k is the number of distinct symbols in the message. We also present an example where D/sub t/=S/sub t/+2t-2k-3[(t-k)/k]-[log(k+1)], showing that the proposed bound is asymptotically tight. These results explain the good performance of FGK observed by some authors through practical experiments.

The minimum redundancy prefix code problem is to determine, for a given list W=[w/sub 1/,...,w/sub n/] of n positive symbol weights, a list L=[l/sub 1/,...,l/sub n/] of n corresponding integer codeword lengths such that /spl Sigma//sub i=1//sup n/2/sup -li//spl les/1 and /spl Sigma//sub i=1//sup n/w/sub i/l/sub i/ is minimized. Let us consider the case where W is already sorted. In this case, the output list L can be represented by a list M=[m/sub 1/,...,m/sub H/], where m(l/sub 1/), for l=1,...,H, denotes the multiplicity of the codeword length l in L and H is the length of the greatest codeword. Fortunately, H is proved to be O(min{log(1/(p/sub 1/)),n}), where p/sub 1/ is the smallest symbol probability, given by w/sub 1///spl Sigma//sub i=1//sup n/w/sub i/. We present the F-LazyHuff and the E-LazyHuff algorithms. F-LazyHuff runs in O(n) time but requires O(min{H/sup 2/,n}) additional space. On the other hand, E-LazyHuff runs in O(nlog(n/H)) time, requiring only O(H) additional space. Finally, since our two algorithms have the advantage of not writing at the input buffer during the code calculation, we discuss some applications where this feature is very useful.

Huffman codes, combined with word-based models, are considered efficient compression schemes for full-text retrieval systems. The decoding rate for these schemes can be substantially improved if the maximum length of the codewords is not greater then the machine word size L. However, if the vocabulary is large, simple methods for generating optimal length-restricted codes are either too slow or require a significantly large amount of memory. We present an in-place, simple and fast implementation for the BRCI (Build, Remove, Condense and Insert) algorithm, an approximative method for length-restricted coding. It overwrites a sorted input list of n weights with the corresponding codeword lengths in O(n) time. In addition, the worst-case compression loss introduced by BRCI codes with respect to unrestricted Huffman codes is proved to be negligible for all practical values of both L and n.