Scheduling on parallel identical machines to minimize total tardiness

This paper focuses on the problem of scheduling n independent jobs on m identical parallel machines for the objective of minimizing total tardiness of the jobs. We develop dominance properties and lower bounds, and develop a branch and bound algorithm using these properties and lower bounds as well as upper bounds obtained from a heuristic algorithm. Computational experiments are performed on randomly generated test problems and results show that the algorithm solves problems with moderate sizes in a reasonable amount of computation time.     

Nonanticipative duality,relaxations, and formulations for chance-constrained stochastic programs

We propose two new Lagrangian dual problems for chance-constrained stochastic programs based on relaxing nonanticipativity constraints. We compare the strength of the proposed dual bounds and demonstrate that they are superior to the bound obtained from the continuous relaxation of a standard mixed-integer programming (MIP) formulation. For a given dual solution, the associated Lagrangian relaxation bounds can be calculated by solving a set of single scenario subproblems and then solving a single knapsack problem. We also derive two new primal MIP formulations and demonstrate that for chance-constrained linear programs, the continuous relaxations of these formulations yield bounds equal to the proposed dual bounds. We propose a new heuristic method and two new exact algorithms based on these duals and formulations. The first exact algorithm applies to chance-constrained binary programs, and uses either of the proposed dual bounds in concert with cuts that eliminate solutions found by the subproblems. The second exact method is a branch-and-cut algorithm for solving either of the primal formulations. Our computational results indicate that the proposed dual bounds and heuristic solutions can be obtained efficiently, and the gaps between the best dual bounds and the heuristic solutions are small.     

Telecommunication Link Restoration Planning with Multiple Facility Types

To ensure uninterrupted service, telecommunication networks contain excess (spare) capacity for rerouting (restoring) traffic in the event of a link failure. We study the NP-hard capacity planning problem of economically installing spare capacity on a network to permit link restoration of steady-state traffic. We present a planning model that incorporates multiple facility types, and develop optimization-based heuristic solution methods based on solving a linear programming relaxation and minimum cost network flow subproblems. We establish bounds on the performance of the algorithms, and discuss problem instances that nearly achieve these worst-case bounds. In tests on three real-world problems and numerous randomly-generated problems containing up to 50 nodes and 150 edges, the heuristics provide good solutions (often within 0.5% of optimality) to problems with single facility type, in equivalent or less time than methods from the literature. For multi-facility problems, the gap between our heuristic solution values and the linear programming bounds are larger. However, for small graphs, we show that the optimal linear programming value does not provide a tight bound on the optimal integer value, and our heuristic solutions are closer to optimality than implied by the gaps.     

Null space conditions and thresholds for rank minimization

Minimizing the rank of a matrix subject to constraints is a challenging problem that arises in many applications in machine learning, control theory, and discrete geometry. This class of optimization problems, known as rank minimization, is NP-hard, and for most practical problems there are no efficient algorithms that yield exact solutions. A popular heuristic replaces the rank function with the nuclear norm—equal to the sum of the singular values—of the decision variable and has been shown to provide the optimal low rank solution in a variety of scenarios. In this paper, we assess the practical performance of this heuristic for finding the minimum rank matrix subject to linear equality constraints. We characterize properties of the null space of the linear operator defining the constraint set that are necessary and sufficient for the heuristic to succeed. We then analyze linear constraints sampled uniformly at random, and obtain dimension-free bounds under which our null space properties hold almost surely as the matrix dimensions tend to infinity. Finally, we provide empirical evidence that these probabilistic bounds provide accurate predictions of the heuristic’s performance in non-asymptotic scenarios.     

Convex optimization under combinatorial sparsity constraints

We present a heuristic approach for convex optimization problems containing different types of sparsity constraints. Whenever the support is required to belong to a matroid, we propose an exchange heuristic adapting the support in every iteration. The entering non-zero is determined by considering the dual multipliers of the bounds on variables being fixed to zero. While this algorithm is purely heuristic, we show experimentally that it often finds near-optimal solutions for cardinality-constrained knapsack problems and for sparse regression problems.     

Lower and upper bounds for location-arc routing problems with vehicle capacity constraints

This paper addresses multi-depot location arc routing problems with vehicle capacity constraints. Two mixed integer programming models are presented for single and multi-depot problems. Relaxing these formulations leads to other integer programming models whose solutions provide good lower bounds for the total cost. A powerful insertion heuristic has been developed for solving the underlying capacitated arc routing problem. This heuristic is used together with a novel location–allocation heuristic to solve the problem within a simulated annealing framework. Extensive computational results demonstrate that the proposed algorithm can find high quality solutions. We also show that the potential cost saving resulting from adding location decisions to the capacitated arc routing problem is significant.     

Multicriteria models for planning power-networking events

In this paper, we develop effective methods for solving the power-networking problem encountered by the Tulsa Metro Chamber. The primary objective is the maximization of unique contacts made in meetings with multiple rotations of participants. Mixed-integer and constraint-programming models are developed to optimize small- to medium-scale problems, and a heuristic method is developed for large-scale problems representative of the Chamber’s application. Tight bounds on the dual objective are presented. The constraint-programming model developed as phase one for the heuristic yields many new best-known solutions to the related social-golfer problem. The solutions generated for the power-networking problem enables the Chamber of Commerce to plan meeting assignments much more effectively.     

A hybrid heuristic for the diameter constrained minimum spanning tree problem

We propose a hybrid GRASP and ILS based heuristic for the diameter constrained minimum spanning tree problem. The latter typically models network design applications where, under a given quality requirement, all vertices must be connected at minimum cost. An adaptation of the one time tree heuristic is used to build feasible diameter constrained spanning trees. Solutions thus obtained are then attempted to be improved through local search. Four different neighborhoods are investigated, in a scheme similar to VND. Upper bounds within 2% of optimality were obtained for problems in two test sets from the literature. Additionally, upper bounds stronger than those previously obtained in the literature are reported for OR-Library instances.     

Minimizing maximum tardiness and number of tardy jobs on parallel machines subject to minimum flow-time

This paper considers the problems of scheduling jobs on parallel identical machines where an optimal schedule is defined as one that gives the smallest maximum tardiness (or the minimum number of tardy jobs) among the set of schedules with optimal total flow-time (the sum of the completion times of all jobs). We show that these problems are unary NP-Hard, develop lower bounds for these two secondary criteria problems, and describe heuristic algorithms for their solution. Results of a computational study show that the proposed heuristic algorithms are quite effective and efficient in solving these hierarchical criteria scheduling problems.     

Decomposition approaches in permutation scheduling problems with application to the M-machine flow shop scheduling problems

In this article, we consider three decomposition techniques for permutation scheduling problems. We introduce a general iterative decomposition algorithm for permutation scheduling problems and apply it to the permutation flow shop scheduling problem. We also develop bounds needed for this iterative decomposition approach and compare its computational requirements to that of the traditional branch and bound algorithms. Two heuristic algorithms based on the iterative decomposition approach are also developed. extensive numerical study indicates that the heuristic algorithms are practical alternatives to very costly exact algorithms for large flow shop scheduling problems.     

Integrating heuristic information into exact methods: The case of the vertex p-centre problem

We solve the vertex p-centre problem optimally using an exact method that considers both upper and lower bounds as part of its search engine. Tight upper bounds are generated quickly via an efficient three-level heuristic, which are then used to derive potential ‘lower bounds’ accordingly. These two pieces of information when used together make our chosen exact method more efficient at obtaining optimal solutions relatively quickly. The proposed implementation produced excellent results when tested on the OR Library data set. This integrated approach can be adopted for those exact methods that consider both upper and lower bounds within their search engine and hence provide a wider spectrum of applicability in other hard combinatorial problems.     

Multiple-type,two-dimensional bin packing problems: Applications and algorithms

In this paper we consider a class of bin selection and packing problems (BPP) in which potential bins are of various types, have two resource constraints, and the resource requirement for each object differs for each bin type. The problem is to select bins and assign the objects to bins so as to minimize the sum of bin costs while meeting the two resource constraints. This problem represents an extension of the classical two-dimensional BPP in which bins are homogeneous. Typical applications of this research include computer storage device selection with file assignment, robot selection with work station assignment, and computer processor selection with task assignment. Three solution algorithms have been developed and tested: a simple greedy heuristic, a method based onsimulated annealing (SA) and an exact algorithm based onColumn Generation with Branch and Bound (CG). An LP-based method for generating tight lower bounds was also developed (LB). Several hundred test problems based on computer storage device selection and file assignment were generated and solved. The heuristic solved problems up to 100 objects in less than a second; average solution value was within about 3% of the optimum. SA improved solutions to an average gap of less than 1% but a significant increase in computing time. LB produced average lower bounds within 3% of optimum within a few seconds. CG is practical for small to moderately-sized problems — possibly as many as 50 objects.     

The two-machine total completion time flow shop problem

In this paper we study the NP-hard scheduling problem of minimizing total completion time in a two-machine flow shop. Five known lower bounds are discussed and two new ones are presented. A new dominance criterion is also proposed. Several versions of a branch and bound method are derived by applying, both individually and combined, these lower bounds. A heuristic procedure is also presented that uses a constructive O(n²) time method, which computes a good starting solution, together with a neighborhood search based on pairwise interchanges. Computational results show that the exact method can handle problems of up to 30 jobs in size within a reasonable amount of time and that the heuristic procedure has an average error of less than 0.5% from the optimal value and less than 2.7% from the lower bound.     

Lower Bounds for Fixed Spectrum Frequency Assignment

Determining lower bounds for the sum of weighted constraint violations in fixed spectrum frequency assignment problems is important in order to evaluate the performance of heuristic algorithms. It is well known that, when adopting a binary constraints model, clique and near-clique subproblems have a dominant role in the theory of lower bounds for minimum span problems. In this paper we highlight their importance for fixed spectrum problems. We present a method based on the linear relaxation of an integer programming formulation of the problem, reinforced with constraints derived from clique-like subproblems. The results obtained are encouraging both in terms of quality and in terms of computation time.     

A tree search algorithm for the multi-commodity location problem

The multi-commodity location problem is an extension of the simple plant location problem. The problem is to decide on locations of facilities to meet customer demands for several commodities in such a way that total fixed plus variable costs are minimized. Only one commodity may be supplied from any location.In this paper a primal and a dual heuristic for producing good bounds are presented. A method of improving these bounds by using a new Lagrangean relaxation for the problem is also presented. Computational results with problems taken from the literature are provided.     

An approach for the Steiner problem in directed graphs

We present a scheme to solve the Steiner problem in directed graphs using a heuristic method to obtain upper bounds and thek shortest arborescences algorithm to compute lower bounds. We propose to combine these ideas in an enumerative algorithm. Computational results are presented for both thek shortest arborescences algorithm and the heuristic method, including reduction tests for the problem.This work was partially supported by CNP_q, FINEP, CAPES and IBM do Brasil.     

Optimization with an approximate Lagrangian

An error analysis is provided for discrete Lagrangian cell problems where the exact objective function for each cell is approximated by a simpler expression. Easily-calculated rigorous and heuristic bounds are given for the error in the value of the objective function. The solution itself, however, can be significantly distorted.     

A Method for Solving Container Packing for a Single Size of Box

There is an extensive literature on heuristic algorithms for two-dimensional cutting problems and three-dimensional packing, but there seems to be very little on the three-dimensional single-box type packing problem. This paper gives a structure for dealing with that problem as a heuristic. It also presents a set of upper bounds on the optimal fit. Finally, the paper compares a particular application of the algorithmic structure with the George and Robinson multiple-box type heuristic.     

An efficient heuristic for scheduling in a flowshop to minimize total weighted flowtime of jobs

The problem of scheduling in a flowshop is considered with the objective of minimizing the total weighted flowtime of jobs. A heuristic algorithm is developed by the introduction of lower bounds on the completion times of jobs and the development of heuristic preference relations for the scheduling problem under study. An improvement scheme is incorporated in the heuristic to enhance the quality of its solution. The proposed heuristic, with and without the improvement scheme, and the existing heuristics are evaluated by a large number of randomly generated problems. The results of an extensive computational investigation for various problem sizes are presented. It has been observed that both versions of the proposed heuristic perform better than the existing heuristics in giving a superior solution quality and that the proposed heuristic without the improvement scheme yields a good solution by requiring a negligible CPU time. In addition, an experimental investigation is carried out to evaluate the effectiveness of the improvement scheme when implemented in the proposed heuristic and the existing heuristics, as well as the effectiveness of a variant of the scheme. The results are also discussed.     

Lagrangian-relaxation-based solution procedures for a multiproduct capacitated facility location problem with choice of facility type

This paper presents exact and heuristic solution procedures for a multiproduct capacitated facility location (MPCFL) problem in which the demand for a number of different product families must be supplied from a set of facility sites, and each site offers a choice of facility types exhibiting different capacities. MPCFL generalizes both the uncapacitated (or simple) facility location (UFL) problem and the pure-integer capacitated facility location problem. We define a branch-and-bound algorithm for MPCFL that utilizes bounds formed by a Lagrangian relaxation of MPCFL which decomposes the problem into UFL subproblems and easily solvable 0-1 knapsack subproblems. The UFL subproblems are solved by the dual-based procedure of Erlenkotter. We also present a subgradient optimization-Lagrangian relaxation-based heuristic for MPCFL. Computational experience with the algorithm and heuristic are reported. The MPCFL heuristic is seen to be extremely effective, generating solutions to the test problems that are on average within 2% of optimality, and the branch-and-bound algorithm is successful in solving all of the test problems to optimality.