A comparative numerical analysis for the guillotine two-dimensional cutting problem

In this work, the behavior of four algorithms in the resolution of the two-dimensional constrained guillotine cutting problem is analyzed. This problem is concerned about the way a set of pieces should be cut from a plate of greater dimensions, considering guillotine cutting and a constrained number of times a piece can be cut from the plate. In this study three combinatorial and two heuristic methods are considered. In the combinatorial methods from the set of pieces, a minimum loss layout is constructively generated based on Wang's algorithm. In addition, an evolutionary and an annealing type approach are considered. All of these models have been implemented on a high performance Silicon Graphics machine. Performance of each algorithm is analyzed both in terms of percentage waste and running time. In order to do that, a set of 1000 instances are classified according to their combinatorial degree and subsequently evaluated. This revised version was published online in June 2006 with corrections to the Cover Date.     

A comparison of average and discounted cost models for the dynamic lot size inventory problem

It is a common practice in the inventory literature to use average cost models as approximations to the theoretically correct discounted cost models. An average cost model minimizes the average undiscounted cost per period, while a discounted cost model minimizes the total discounted cost over the problem horizon. This paper attempts to answer an important question: How good are the results (the total discounted costs) for the average cost models compared to those for the discounted cost models? This question has been conclusively answered for the simplest inventory model where the demand rate and other parameters are assumed to remain constant in time. This paper addresses this issue for the first time for the case where demand rates are allowed to be nonstationary in time.A discounted cost model has been developed in the paper to carry out this comparison. It is shown that a simple dynamic programming algorithm can be used to find optimal order policies for the discounted cost model.The effect of the varying interest rates and other parameters on the relative performance of the average cost model has been studied by developing an insightful analysis and also by doing a computational study. The results show that, while the average cost model can cost as much as about 26% more than the discounted cost model in extreme cases, this increase is not significant for the parameter values in the range of the common interest.     

Analysis of heuristics for finding a maximum weight planar subgraph

The problem of identifying a planar subgraph of maximum total weight in an edge-weighted graph has application to the layout of facilities in a production system and elsewhere in industrial engineering.This problem is NP-hard, and so we confine our attention to polynomial-time heuristics. In this paper we analyse the performance of some heuristics for this problem.     

The consensus string problem for a metric is NP-complete

Given a set S of strings, a consensus string of S based on consensus error is a string w that minimizes the sum of the distances between w and all the strings in S. In this paper, we show that the problem of finding a consensus string based on consensus error is NP-complete when the penalty matrix is a metric.     

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.     

A simple dual algorithm for the generalised assignment problem

A new algorithm for the generalised assignment problem is described in this paper. The dual-type algorithm uses a simple heuristic derived from a relaxation of the problem. The algorithm has been tested on generalised assignment problems of substantial size and compared to an exact integer programming approach and a well-established heuristic approach. Computational results look promising in terms of speed and solution quality.     

A primal-proximal heuristic applied to the French Unit-commitment problem

This paper is devoted to the numerical resolution of unit-commitment problems, with emphasis on the French model optimizing the daily production of electricity. The solution process has two phases. First a Lagrangian relaxation solves the dual to find a lower bound; it also gives a primal relaxed solution. We then propose to use the latter in the second phase, for a heuristic resolution based on a primal proximal algorithm. This second step comes as an alternative to an earlier approach, based on augmented Lagrangian (i.e. a dual proximal algorithm). We illustrate the method with some real-life numerical results. A companion paper is devoted to a theoretical study of the heuristic in the second phase.     

A generalization of a classical zero-sum problem

In this note, we supply the details of the proof of the fact that if a₁,…,a_n+Ω(n) are integers, then there exists a subset M⊂{1,…,n+Ω(n)} of cardinality n such that the equation

     

A method of estimating computational complexity based on input conditions for N-vehicle problem

This paper proposes a method of estimating computational complexity of problem through analyzing its input condition for N-vehicle exploration problem. The N-vehicle problem is firstly formulated to determine the optimal replacement in the set of permutations of 1 to N. The complexity of the problem is factorial of N （input scale of problem）. To balance accuracy and efficiency of general algorithms, this paper mentions a new systematic algorithm design and discusses correspondence between complexity of problem and its input condition, other than just putting forward a uniform approximation algorithm as usual. This is a new technique for analyzing computation of NP problems. The method of corresponding is then presented. We finally carry out a simulation to verify the advantages of the method： 1） to decrease computation in enumeration; 2） to efficiently obtain computational complexity for any N-vehicle case; 3） to guide an algorithm design for any N-vehicle case according to its complexity estimated by the method.     

Optimal synthesis in a control problem with Lipschitz input data

We propose a numerical algorithm for constructing an optimal synthesis in the control problem for a nonlinear system on a fixed time interval. We estimate the difference between the values of the cost functional on optimal trajectories and on the trajectories constructed according to this algorithm. The operation of the algorithm is illustrated by solving model examples on the plane.     

A heuristic for the Steiner problem in graphs

In this paper, we present a heuristic for the Steiner problem in graphs (SPG) along with some experimental results. The heuristic is based on an approach similar to Prim's algorithm for the minimum spanning tree. However, in this approach, arcs are associated with preference weights which are used to break ties among alternative choices of shortest paths occurring during the course of the algorithm. The preference weights are calculated according to a global view which takes into consideration the effect of all the regular nodes, nodes to be connected, on determining the choice of an arc in the solution tree.     

A linear programming reformulation of the standard quadratic optimization problem

The problem of minimizing a quadratic form over the standard simplex is known as the standard quadratic optimization problem (SQO). It is NP-hard, and contains the maximum stable set problem in graphs as a special case. In this note, we show that the SQO problem may be reformulated as an (exponentially sized) linear program (LP). This reformulation also suggests a hierarchy of polynomial-time solvable LP’s whose optimal values converge finitely to the optimal value of the SQO problem. The hierarchies of LP relaxations from the literature do not share this finite convergence property for SQO, and we review the relevant counterexamples.     

A computational comparison of algorithms for the inventory routing problem

The inventory routing problem is a distribution problem in which each customer maintains a local inventory of a product such as heating oil and consumes a certain amount of that product each day. Each day a fleet of trucks is dispatched over a set of routes to resupply a subset of the customers. In this paper, we describe and compare algorithms for this problem defined over a short planning period, e.g. one week. These algorithms define the set of customers to be serviced each day and produce routes for a fleet of vehicles to service those customers. Two algorithms are compared in detail, one which first allocates deliveries to days and then solves a vehicle routing problem and a second which treats the multi-day problem as a modified vehicle routing problem. The comparison is based on a set of real data obtained from a propane distribution firm in Pennsylvania. The solutions obtained by both procedures compare quite favorably with those in use by the firm.Part of this work was performed while this author was visiting the University of Waterloo.     

Bounds for the symmetric 2-peripatetic salesman problem

The 2-Peripatetic Salesman Problem (2-PSP) minimizes the total length of 2 edge-disjoint Hamil-tonian cycles. This type of problems arises in designing communication or computer networks, or whenever one aims to increase network reliability using disjoint tours. The NP-hardness of the 2-PSP is shown. Lower bound values are obtained by generalizing the 1-tree approach for the TSP to a 2 edge-disjoint 1-trees approach for the 2-PSP. One can construct 2 edge-disjoint 1-trees using a greedy algorithm, into which a partitioning procedure is incorporated that runs O(n ² log n) time. Upper bound solutions are obtained by two heuristics based on a lower bound solution and by a modified Savings heuristic for problems up to 140 cities.     

A probabilistic analysis of the set covering problem

A probabilistic analysis of the minimum cardinality set covering problem (SCP) is developed, considering a stochastic model of the (SCP), withn variables andm constraints, in which the entries of the corresponding (m, n) incidence matrix are independent Bernoulli distributed random variables, each with constant probabilityp of success. The behaviour of the optimal solution of the (SCP) is then investigated as bothm andn grow asymptotically large, assuming either an incremental model for the evolution of the matrix (for each size, the matrixA is obtained bordering a matrix of smaller size by new columns and rows) or an independent one (for each size, an entirely new set of entries forA are considered). Two functions ofm are identified, which represent a lower and an upper bound onn in order the (SCP) to be a.e. feasible and not trivial. Then, forn lying within these bounds, an asymptotic formula for the optimum value of the (SCP) is derived and shown to hold a.e.The performance of two simple randomized algorithms is then analyzed. It is shown that one of them produces a solution value whose ratio to the optimum value asymptotically approaches 1 a.e. in the incremental model, but not in the independent one, in which case the ratio is proved to be tightly bounded by 2 a.e. Thus, in order to improve the above result, a second randomized algorithm is proposed, for which it is proved that the ratio between the approximate solution value and the optimum approaches 1 a.e. also in the independent model.     

The harmonious coloring problem is NP-complete for interval and permutation graphs

In this paper, we prove that the harmonious coloring problem is NP-complete for connected interval and permutation graphs. Given a simple graph G, a harmonious coloring of G is a proper vertex coloring such that each pair of colors appears together on at most one edge. The harmonious chromatic number is the least integer k for which G admits a harmonious coloring with k colors. Extending previous work on the NP-completeness of the harmonious coloring problem when restricted to the class of disconnected graphs which are simultaneously cographs and interval graphs, we prove that the problem is also NP-complete for connected interval and permutation graphs.     

A class of heuristics for the constrained forest problem

The constrained forest problem seeks a minimum-weight spanning forest in an undirected edge-weighted graph such that each tree spans at least a specified number of vertices. We present a structured class of greedy heuristics for this NP-hard problem, and identify the best heuristic.     

A polynomial-time linear decision tree for the traveling salesman problem and other NP-complete problems

We show that the position of an input point in the Euclideand-dimensional space with respect to a given set of hyperplanes can be determined efficiently by linear decision trees. As an application, we prove that many concrete problems whose recognition versions are NP-complete, like the traveling salesman problem, many other shortest path problems, and integer programming, have polynomial-time upper bounds in the linear decision tree model of computation.