An Application of Branch and Cut to Open Pit Mine Scheduling

The economic viability of the modern day mine is highly dependent upon careful planning and management. Declining trends in average ore grades, increasing mining costs and environmental considerations will ensure that this situation will remain in the foreseeable future. The operation and management of a large open pit mine having a life of several years is an enormous and complex task. Though a number of optimization techniques have been successfully applied to resolve some important problems, the problem of determining an optimal production schedule over the life of the deposit is still very much unresolved. In this paper we will critically examine the techniques that are being used in the mining industry for production scheduling indicating their limitations. In addition, we present a mixed integer linear programming model for the scheduling problems along with a Branch and Cut solution strategy. Computational results for practical sized problems are discussed.     

A branch and bound algorithm for the robust shortest path problem with interval data

Many real problems can be modelled as robust shortest path problems on interval digraphs, where intervals represent uncertainty about real costs and a robust path is not too far from the shortest path for each possible configuration of the arc costs.A branch and bound algorithm for this problem is presented.     

Practical algorithms for transposition-invariant string-matching

We consider the problems of (1) longest common subsequence (LCS) of two given strings in the case where the first may be shifted by some constant (that is, transposed) to match the second, and (2) transposition-invariant text searching using indel distance. These problems have applications in music comparison and retrieval. We introduce two novel techniques to solve these problems efficiently. The first is based on the branch and bound method, the second on bit-parallelism. Our branch and bound algorithm computes the longest common transposition-invariant subsequence (LCTS) in time O((m²+loglogσ)logσ) in the best case and O((m²+logσ)σ) in the worst case, where m and σ, respectively, are the length of the strings and the size of the alphabet. On the other hand, we show that the same problem can be solved by using bit-parallelism and thus obtain a speedup of O(w/logm) over the classical algorithms, where the computer word has w bits. The advantage of this latter algorithm over the present bit-parallel ones is that it allows the use of more complex distances, including general integer weights. Since our branch and bound method is very flexible, it can be further improved by combining it with other efficient algorithms such as our novel bit-parallel algorithm. We experiment on several combination possibilities and discuss which are the best settings for each of those combinations. Our algorithms are easily extended to other musically relevant cases, such as δ-matching and polyphony (where there are several parallel texts to be considered). We also show how our bit-parallel algorithm is adapted to text searching and illustrate its effectiveness in complex cases where the only known competing method is the use of brute force.     

Effect of the subdivision strategy on convergence and efficiency of some global optimization algorithms

We investigate subdivision strategies that can improve the convergence and efficiency of some branch and bound algorithms of global optimization. In particular, a general class of so called weakly exhaustive simplicial subdivision processes is introduced that subsumes all previously known radial exhaustive processes. This result provides the basis for constructing flexible subdivision strategies that can be adapted to take advantage of various problem conditions.     

On the Center of Continuous Maps of Dendrites

The structure and the depth of the center of a continuous map of a dendrite with a closed countable set of branch points of a finite order are studied. It is proved that the center of that map coincides with the closure of the set of periodic points. It is shown also that for an arbitrary natural number n S 2 there are the dendrite X n with a closed countable set of branch points of a finite order and the continuous map f n : X n M X n with n as the depth of the center.     

A statistical model for global optimization by means of select and clone

A statistical model tor giobai optimization is constructed generalizing some properties ofthe Wiener process to the multidimensional case. A new approach, which is similar to the Branch and Bound approach, is proposed to the construction of algorithms based on statistical models. A two dimensional version of the algorithm is implemented, and test results are presented     

醇对非离子型表面活性剂浊点的影响

研究了醇对非离子型表面活性剂浊点的影响，发现直链醇的碳原子数小于４时随着其在表面活性剂中含量的增加浊点上升；当碳原子数大于４时，则随着醇含量的增加浊点下降。醇的构型对浊点起着重要作用。     

Optimization of capacity expansion planning for gas transportation networks

This paper presents techniques for solving the problem of minimizing investment costs on an existing gas transportation network. The goal of this program is to find, first, the optimal location of pipeline segments to be reinforced and, second, the optimal sizes (among a discrete commercial list of diameters) under the constraint of satisfaction of demands with high enough pressure for all users.     

Single machine scheduling with family setups to minimize total earliness and tardiness

This paper considers the problem of scheduling a given number of jobs on a single machine to minimize total earliness and tardiness when family setup times exist. The paper proposes optimal branch-and-bound algorithms for both the group technology assumption and if the group technology assumption is removed. A heuristic algorithm is proposed to solve larger problems with the group technology assumption removed. The proposed algorithms were empirically evaluated on problems of various sizes and parameters. The paper also explores how the choice of procedure affects total earliness and tardiness if an implementation of lean production methods has resulted in a reduction in setup times. An important finding of these empirical investigations is that scheduling jobs by removing the group technology assumption can significantly reduce total earliness and tardiness.     

Improving the efficiency of DC global optimization methods by improving the DC representation of the objective function

There are infinitely many ways of representing a d.c. function as a difference of convex functions. In this paper we analyze how the computational efficiency of a d.c.optimization algorithm depends on the representation we choose for the objective function, and we address the problem of characterizing and obtaining a computationally optimal representation. We introduce some theoretical concepts which are necessary for this analysis and report some numerical experiments.