Extensions to the repetitive branch and bound algorithm for globally optimal clusterwise regression

A branch and bound strategy is proposed for solving the clusterwise regression problem, extending Brusco's repetitive branch and bound algorithm (RBBA). The resulting strategy relies upon iterative heuristic optimization, new ways of observation sequencing, and branch and bound optimization of a limited number of ending subsets. These three key features lead to significantly faster optimization of the complete set and the strategy has more general applications than only for clusterwise regression. Additionally, an efficient implementation of incremental calculations within the branch and bound search algorithm eliminates most of the redundant ones. Experiments using both real and synthetic data compare the various features of the proposed optimization algorithm and contrasts them against a benchmark mixed logical-quadratic programming formulation optimized by CPLEX. The results indicate that all components of the proposed algorithm provide significant improvements in processing times, and, when combined, generally provide the best performance, significantly outperforming CPLEX.     

A branch and bound algorithm for the cyclic job-shop problem with transportation

The cyclic job-shop problem with transportation can be used to describe optimization problems in fully automated manufacturing systems or assembly lines. We study the problem where the machines have no buffers, which rapidly decreases the number of feasible solutions and, therefore, makes it a lot harder to find those feasible solutions. After formulating the problem, we will characterize feasible solutions based on the route of the robot and their properties. With the aim of minimizing the cycle time, we have developed a tree search method to construct feasible solutions and combined it with a bounding procedure. Computational results are reported and compared to those gained by solving the problem with an LP solver.     

A 2-phase algorithm for solving the single allocation p-hub center problem

The single allocation p-hub center problem is an NP-hard location–allocation problem which consists of locating hub facilities in a network and allocating non-hub nodes to hub nodes such that the maximum distance/cost between origin–destination pairs is minimized. In this paper we present an exact 2-phase algorithm where in the first phase we compute a set of potential optimal hub combinations using a shortest path based branch and bound. This is followed by an allocation phase using a reduced sized formulation which returns the optimal solution. In order to get a good upper bound for the branch and bound we developed a heuristic for the single allocation p-hub center problem based on an ant colony optimization approach. Numerical results on benchmark instances show that the new solution approach is superior over traditional MIP-solver like CPLEX. As a result we are able to provide new optimal solutions for larger problems than those reported previously in literature. We are able to solve problems consisting of up to 400 nodes in reasonable time. To the best of our knowledge these are the largest problems solved in the literature to date.     

A branch and bound algorithm for an identical parallel machine scheduling problem with a job splitting property

We focus on the problem of scheduling n independent jobs on m identical parallel machines with the objective of minimizing total tardiness of the jobs considering a job splitting property. In this problem, it is assumed that a job can be split into sub-jobs and these sub-jobs can be processed independently on parallel machines. We develop several dominance properties and lower bounds for the problem, and suggest a branch and bound algorithm using them. Computational experiments are performed on randomly generated test problems and results show that the suggested algorithm solves problems of moderate sizes in a reasonable amount of computation time.     

A fast algorithm for the generalized parametric minimum cut problem and applications

Many combinatorial optimization problems are solved by a sequence of network flow computations on a network whose edge capacities are given as a function of a parameter . Recently Galloet al. [7] made a major advance in solving such parametric flow problems. They showed that for an important class of networks, calledmonotone parametric flow networks, a sequence ofO(n) flow computations could be solved in the same worst-case time bound as a single flow. However, these results require one of two special assumptions: either that the values are presented in increasing or decreasing order; or that the edge capacity functions are affine functions of . In this paper we show how to remove both of these assumptions while obtaining the same running times as in [7]. This observation generalizes and unifies the two major results of [7], and allows its ideas to be applied to many new combinatorial problems. Of greatest importance, it allows the efficient application of binary search and successive binary search to a sequence of network flow problems.This research was partially supported by Grants CCR-8803704 and CCR-8722848 from the National Science Foundation.     

A Tabu search algorithm for the network pricing problem

In this paper, we propose an efficient Tabu Search procedure for solving the NP-hard network pricing problem. By exploiting the problem's features, the algorithm allows the near-optimal solution of problem instances that are out of reach of exact combinatorial methods.     

A branch and bound method for isolation of faulty variables through missing variable analysis

Fault detection and diagnosis is a critical approach to ensure safe and efficient operation of manufacturing and chemical processing plants. Although multivariate statistical process monitoring has received considerable attention, investigation into the diagnosis of the source or cause of the detected process fault has been relatively limited. This is partially due to the difficulty in isolating multiple variables, which jointly contribute to the occurrence of fault, through conventional contribution analysis. In this work, a method based on probabilistic principal component analysis is proposed for fault isolation. Furthermore, a branch and bound method is developed to handle the combinatorial nature of problem involving finding the contributing variables, which are most likely to be responsible for the occurrence of fault. The efficiency of the method proposed is shown through benchmark examples, such as Tennessee Eastman process, and randomly generated cases.     

A cross entropy algorithm for the Knapsack problem with setups

In this article we propose a new metaheuristic-based algorithm for the Integer Knapsack Problem with Setups. This problem is a generalization of the standard Integer Knapsack Problem, complicated by the presence of setup costs in the objective function as well as in the constraints. We propose a cross entropy based algorithm, where the metaheuristic scheme allows to relax the original problem to a series of well chosen standard Knapsack problems, solved through a dynamic programming algorithm. To increase the computational effectiveness of the proposed algorithm, we use a turnpike theorem, which sensibly reduces the number of iterations of the dynamic algorithm. Finally, to testify the robustness of the proposed scheme, we present extensive computational results. First, we illustrate the step-by-step behavior of the algorithm on a smaller, yet difficult, problem. Subsequently, to test the solution quality of the algorithm, we compare the results obtained on very large scale instances with the output of a branch and bound scheme. We conclude that the proposed algorithm is effective in terms of solution quality as well as computational time.     

A new ant colony optimization algorithm for the multidimensional Knapsack problem

The paper proposes a new ant colony optimization (ACO) approach, called binary ant system (BAS), to multidimensional Knapsack problem (MKP). Different from other ACO-based algorithms applied to MKP, BAS uses a pheromone laying method specially designed for the binary solution structure, and allows the generation of infeasible solutions in the solution construction procedure. A problem specific repair operator is incorporated to repair the infeasible solutions generated in every iteration. Pheromone update rule is designed in such a way that pheromone on the paths can be directly regarded as selecting probability. To avoid premature convergence, the pheromone re-initialization and different pheromone intensification strategy depending on the convergence status of the algorithm are incorporated. Experimental results show the advantages of BAS over other ACO-based approaches for the benchmark problems selected from OR library.     

Reduction strategies and exact algorithms for the disjunctively constrained knapsack problem

In this paper, we optimally solve the disjunctively constrained knapsack problem (DCKP), which is a variant of the standard knapsack problem with special disjunctive constraints. First, we develop a generic exact approach which can be considered as a three-phase procedure. The first phase tries to estimate a starting lower bound. The second phase applies a reduction procedure, combined with the lower bound, in order to fix some decision variables to the optimum. The third phase uses an exact branch and bound algorithm that identifies the optimal values of the free decision variables. Second, we design a specialized exact algorithm based upon a dichotomous search combined with a reduction procedure. Third and last, we propose a modified dichotomous search version which is based upon constructing an equivalent model to the DCKP, adding some dominating constraints, and injecting the so-called covering cut. We evaluate the performance of all versions of the algorithm and compare the obtained results to those of other exact algorithms of the literature. Encouraging results have been obtained.     

基于一种新型分支定价算法的电动车支线镇际快递配送路径规划研究

针对由电动汽车支持的支线镇际快递配送系统,提出一类新型的分支定价算法实现对车辆和货物的路径规划.研究利用时空网络将时间离散化构建模型,同时考虑了车辆资源、仓储资源和充电桩资源的管理问题.在分支定价算法中,分支策略和割平面策略的结合有效削弱了时间离散化所带来的对称性问题.强化策略则通过对生成路径变量进行有效筛选,并利用求...     

An improved multi-objective evolutionary algorithm for the vehicle routing problem with time windows

The vehicle routing problem with time windows is a complex combinatorial problem with many real-world applications in transportation and distribution logistics. Its main objective is to find the lowest distance set of routes to deliver goods, using a fleet of identical vehicles with restricted capacity, to customers with service time windows. However, there are other objectives, and having a range of solutions representing the trade-offs between objectives is crucial for many applications. Although previous research has used evolutionary methods for solving this problem, it has rarely concentrated on the optimization of more than one objective, and hardly ever explicitly considered the diversity of solutions. This paper proposes and analyzes a novel multi-objective evolutionary algorithm, which incorporates methods for measuring the similarity of solutions, to solve the multi-objective problem. The algorithm is applied to a standard benchmark problem set, showing that when the similarity measure is used appropriately, the diversity and quality of solutions is higher than when it is not used, and the algorithm achieves highly competitive results compared with previously published studies and those from a popular evolutionary multi-objective optimizer.     

A branch and bound method for the line balancing problem in U-shaped assembly lines with equipment requirements

In this study we consider a U-shaped assembly line balancing problem where each task uses a specified set of equipments and each type of equipment has a specified cost. Our problem is to assign the tasks together with their equipments to the workstations so as to minimize the total equipment cost. We formulate the problem as a mixed integer linear programming model that is capable of solving small sized instances. We propose a branch and bound algorithm that uses efficient precedence relations and lower bounds. We find that the algorithm is able to solve moderate sized problem instances in reasonable times.     

A block-based evolutionary algorithm for flow-shop scheduling problem

Combinatorial problems like flow shop scheduling, travel salesman problem etc. get complicated and are difficult to solve when the problem size increases. To overcome this problem, we present a block-based evolutionary algorithm (BBEA) which will conduct evolutionary operations on a set of blocks instead of genes. BBEA includes the block mining and block recombination approaches. A block mining algorithm is developed to decompose a chromosome into a set of blocks and rest of genes. The block is with a fixed length and can be treated as a building block in forming a new chromosome later on. To guide the block mining process, a gene linkage probability matrix is defined that shows the linkage strength among genes. Therefore the blocks can be further evolved during the evolutionary processes using this matrix. In the block recombination approach, the blocks along with the rest of genes are recombined to form a new chromosome. This new evolutionary approach of BBEA is tested on a set of discrete problems. Experimental results show that BBEA is very competitive when compared with traditional GA, EA or ACGA and HGIA approaches and it can largely improve the performance of evolutionary algorithm and save a fair amount of computational times simultaneously.     

Analysis of transient of the datagram traffic for a demand assignment TDMA satellite access scheme

A modified version of the datagram capacity assignment of the FODA (fifo ordered demand assignment) access scheme, named FODA/IBEA, (information bit energy adaptive) is briefly presented. The main difference from the previous version (besides the fade countermeasure feature) is the possibility of the system to migrate, depending on the overall loading conditions, from a sort of fixed TDMA (time division multiple access) (called pre-assignment mode), in which each active station shares the spare capacity with all the others, to a more complex mechanism. The response of the system to a step of traffic at one of the active stations is studied, and the analytical expressions of the most significant variables are derived. The results of the analysis are first compared with the experimental ones and then used to show the sensitivity of the system's behavior with respect to some parameters. The possibility of adopting the capacity allocation algorithm in a distributed mode is also discussed.     

The reverse greedy algorithm for the metric k-median problem

The Reverse Greedy algorithm (RGreedy) for the k-median problem works as follows. It starts by placing facilities on all nodes. At each step, it removes a facility to minimize the total distance to the remaining facilities. It stops when k facilities remain. We prove that, if the distance function is metric, then the approximation ratio of RGreedy is between Ω(logn/loglogn) and O(logn).     

A theoretical development for the total tardiness problem and its application in branch and bound algorithms

This paper deals with the single machine total tardiness problem, and proves that if the job sequences produced by two heuristics, named as Time Forward and Time Backward algorithms, have the same starting and ending job subsequences, then there exists an optimal job sequence with the starting and ending job subsequences. The computation experiments show that there is a significant improvement of the running time of a branch and bound algorithm with the incorporation of the new property.     

Dynamic window reduction for the multiple depot vehicle scheduling problem with time windows

We consider a widespread branch-and-price approach to solve the multiple depot vehicle scheduling problem with time windows. We describe a dynamic time window reduction technique to speed up this approach. The time windows are transferred from nodes to arcs in order to take advantage of dual information and to tighten as much as possible the time variable domains. The performance of the proposed technique is evaluated through computational experiments on randomly generated instances involving several depots and up to 900 tasks.     

Maximizing the Robustness of TDMA Networks with Applications to TTP/C

In this study we show how one can use Fault-Tolerant Units (FTU) in an optimal way to make a TDMA network robust to bursty random perturbations. We consider two possible objectives. If one wants to minimize the probability of losing all replicas of a given message, then the optimal policy is to spread the replicas over time. This is proved using convexity properties of the loss probability. On the contrary if one wants to minimize the probability of losing at least one replica, then the optimal solution is to group all replicas together. This is proved by using majorization techniques. Finally we show how these ideas can be adapted for the TTP/C protocol. Bruno Gaujal is a research director at INRIA Rhone-Alpes since 2003 where he is the leader of the group on large scale networks. He has held several positions in INRIA Sophia-Antipolis, Loria and ENS-Lyon before. His main interest are performance evaluation and control of discrete event dynamic systems. Nicolas Navet received the M.S. in Computer Science from the University of Berlin (Germany) in 1994 and the PhD in Computer Science from the University of Nancy in 1999. Before joining the INRIA (LORIA Lab.) in November 2000, he was research scientist at Gemplus Software. His research interests include scheduling theory, the design of communication protocols for real-time and fault-tolerant data transmission and probabilistic risk evaluation when transient faults may occur (for instance, due to electromagnetic interferences). More information on his work can be found at url http://www.loria.fr/~nnavet.     

A rock-paper-scissors evolutionary algorithm for the TDMA broadcast scheduling problem

In wireless ad-hoc networks, the broadcast scheduling problem (BSP) is commonly viewed as a well-known NP-complete combinatorial optimization problem. The purpose of the BSP is to achieve a transmission schedule with collision-free time slots in a time division multiple access ad-hoc network. The transmission schedule is optimized by minimizing the frame length of the node transmissions and maximizing the utilization of the shared channel. In this work, we propose a new evolutionary algorithm to solve the BSP by adopting the rock-paper-scissors dynamics found in natural systems. We use three types of species with strategies of different levels of intensification and diversification to simulate the rock-paper-scissors dynamics. Based on this evolutionary game, in which the success of one species relies on the behavior of others, the dynamic coexistence of three species can be achieved to control the balance between intensification and diversification. The experimental results demonstrate that our algorithm is efficient and effective at solving large instances of the BSP.