Minimizing number of tardy jobs on a single machine subject to periodic maintenance

This paper considers a single-machine scheduling problem with periodic maintenance. In this study, a schedule consists of several maintenance periods and each maintenance period is scheduled after a periodic time interval. The objective is to find a schedule that minimizes the number of tardy jobs subject to periodic maintenance and nonresumable jobs. Based on the Moore's algorithm, an effective heuristic is developed to provide a near-optimal schedule for the problem. A branch-and-bound algorithm is also proposed to find the optimal schedule. Some important theorems associated with the problem are implemented in the algorithm. Computational results are presented to demonstrate the effectiveness of the proposed heuristic.     

A new effective branch-and-bound algorithm to the high order MIMO detection problem

This paper develops a branch-and-bound method based on a new convex reformulation to solve the high order MIMO detection problem. First, we transform the original problem into a \(\{-1,1\}\) constrained quadratic programming problem with the smallest size. The size of the reformulated problem is smaller than those problems derived by some traditional transformation methods. Then, we propose a new convex reformulation which gets the maximized average objective value as the lower bound estimator in the branch-and-bound scheme. This estimator balances very well between effectiveness and computational cost. Thus, the branch-and-bound algorithm achieves a high total efficiency. Several simulations are used to compare the performances of our method and other benchmark methods. The results show that this proposed algorithm is very competitive for high accuracy and relatively good efficiency.     

Exact solution method to solve large scale integer quadratic multidimensional knapsack problems

In this paper we develop a branch-and-bound algorithm for solving a particular integer quadratic multi-knapsack problem. The problem we study is defined as the maximization of a concave separable quadratic objective function over a convex set of linear constraints and bounded integer variables. Our exact solution method is based on the computation of an upper bound and also includes pre-procedure techniques in order to reduce the problem size before starting the branch-and-bound process. We lead a numerical comparison between our method and three other existing algorithms. The approach we propose outperforms other procedures for large-scaled instances (up to 2000 variables and constraints). A extended abstract of this paper appeared in LNCS 4362, pp. 456–464, 2007.     

Minimization of maximum lateness under linear deterioration

This paper considers a single-machine scheduling problem to minimize the maximum lateness. The processing time of each job is a linear function of the time when the job starts processing. This problem is known to be -hard in the literature. In this paper, we design a branch-and-bound algorithm for deriving exact solutions by incorporating several properties concerning dominance relations and lower bounds. These properties produce synergic effects in accelerating the solution finding process such that the algorithm can solve problems of 100 jobs within 1 min on average. To compose approximate solutions, we revise a heuristic algorithm available in the literature and propose several hybrid variants. Numerical results evince that the proposed approaches are very effective in successfully reporting optimal solutions for most of the test cases.     

Dynamic Programming and Hill-Climbing Techniques for Constrained Two-Dimensional Cutting Stock Problems

In this paper we propose an algorithm for the constrained two-dimensional cutting stock problem (TDC) in which a single stock sheet has to be cut into a set of small pieces, while maximizing the value of the pieces cut. The TDC problem is NP-hard in the strong sense and finds many practical applications in the cutting and packing area. The proposed algorithm is a hybrid approach in which a depth-first search using hill-climbing strategies and dynamic programming techniques are combined. The algorithm starts with an initial (feasible) lower bound computed by solving a series of single bounded knapsack problems. In order to enhance the first-level lower bound, we introduce an incremental procedure which is used within a top-down branch-and-bound procedure. We also propose some hill-climbing strategies in order to produce a good trade-off between the computational time and the solution quality. Extensive computational testing on problem instances from the literature shows the effectiveness of the proposed approach. The obtained results are compared to the results published by Alvarez-Valdés et al. (2002).     

An improved MIP heuristic for the intermodal hub location problem

Optimization methods have been commonly developed for the intermodal hub location problem because it has a broad range of practical applications. These methods include exact methods (limited on solving large-size problems) and heuristics (no guarantee on solution quality). In order to avoid their weakness but to leverage their strength, we develop an improved MIP heuristic combining branch-and-bound, Lagrangian relaxation, and linear programming relaxation. In the heuristic, we generate a population of initial feasible solutions using the branch-and-bound and Lagrangian relaxation methods and create a linear-relaxed solution using the linear programming relaxation method. We combine these feasible and linear-relaxed solutions to fix a portion of hub location variables so as to create a number of restricted hub location subproblems. We then combine the branch-and-bound method to solve these restricted subproblems for iteratively improving solution quality. We discuss in detail the application of the method to the intermodal hub location problem. The discussion is followed by extensive statistical analysis and computational tests, where the analysis shows statistical significance of solutions for guiding the heuristic search and comparisons with other methods indicate that the proposed approach is computationally tractable and is able to obtain competitive results.     

A UNIVERSITY EXAMINATION-SCHEDULING MODEL TO MINIMIZE MULTIPLE-EXAMINATION DAYS FOR STUDENTS

Scheduling university examinations is often done with the objective of spreading a student's required examinations over an examination week. That is the equivalent of the problem of minimizing the number of examinations a student must take on any one day. An approach to scheduling exams which relates the problem to the classical assignment problem is discussed. The model developed is a symmetry-constrained assignment model, and the solution method requires use of a branch-and-bound algorithm. Results from application of the algorithm to six semesters of actual data are presented.     

A Combined D.C. Optimization—Ellipsoidal Branch-and-Bound Algorithm for Solving Nonconvex Quadratic Programming Problems

In this paper we propose a new branch-and-bound algorithm by using an ellipsoidal partition for minimizing an indefinite quadratic function over a bounded polyhedral convex set which is not necessarily given explicitly by a system of linear inequalities and/or equalities. It is required that for this set there exists an efficient algorithm to verify whether a point is feasible, and to find a violated constraint if this point is not feasible. The algorithm is based upon the fact that the problem of minimizing an indefinite quadratic form over an ellipsoid can be efficiently solved by some available (polynomial and nonpolynomial time) algorithms. In particular, the d.c. (difference of convex functions) algorithm (DCA) with restarting procedure recently introduced by Pham Dinh Tao and L.T. Hoai An is applied to globally solving this problem. DCA is also used for locally solving the nonconvex quadratic program. It is restarted with current best feasible points in the branch-and-bound scheme, and improved them in its turn. The combined DCA-ellipsoidal branch-and-bound algorithm then enhances the convergence: it reduces considerably the upper bound and thereby a lot of ellipsoids can be eliminated from further consideration. Several numerical experiments are given.     

On risk-averse maximum weighted subgraph problems

In this work, we consider a class of risk-averse maximum weighted subgraph problems (R-MWSP). Namely, assuming that each vertex of the graph is associated with a stochastic weight, such that the joint distribution is known, the goal is to obtain a subgraph of minimum risk satisfying a given hereditary property. We employ a stochastic programming framework that is based on the formalism of modern theory of risk measures in order to find minimum-risk hereditary structures in graphs with stochastic vertex weights. The introduced form of risk function for measuring the risk of subgraphs ensures that optimal solutions of R-MWS problems represent maximal subgraphs. A graph-based branch-and-bound (BnB) algorithm for solving the proposed problems is developed and illustrated on a special case of risk-averse maximum weighted clique problem. Numerical experiments on randomly generated Erdös-Rényi graphs demonstrate the computational performance of the developed BnB.     

Combinatorial Optimization in Rapidly Mutating Drug-Resistant Viruses

Resistance to chemicals is a common current problem in many pests and pathogens that formerly were controlled by chemicals. An extreme case occurs in rapidly mutating viruses such as Human Immunodeficiency Virus (HIV), where the emergence of selective drug resistance within an individual patient may become an important factor in treatment choice. The HIV patient subpopulation that already has experienced at least one treatment failure due to drug resistance is considered more challenging to treat because the treatment options have been reduced. A triply nested combinatorial optimization problem occurs in computational attempts to optimize HIV patient treatment protocol (drug regimen) with respect to drug resistance, given a set of HIV genetic sequences from the patient. In this paper the optimization problem is characterized, and the objects involved are represented computationally. An implemented branch-and-bound algorithm that computes a solution to the problem is described and proved correct. Data shown includes empirical timing results on representative patient data, example clinical output, and summary statistics from an initial small-scale human clinical trial.     

Improvements to MCS algorithm for the maximum clique problem

In this paper we present improvements to one of the most recent and fastest branch-and-bound algorithm for the maximum clique problem—MCS algorithm by Tomita et al. (Proceedings of the 4th international conference on Algorithms and Computation, WALCOM’10, pp. 191–203, 2010). The suggested improvements include: incorporating of an efficient heuristic returning a high-quality initial solution, fast detection of clique vertices in a set of candidates, better initial colouring, and avoiding dynamic memory allocation. Our computational study shows some impressive results, mainly we have solved p_hat1000-3 benchmark instance which is intractable for MCS algorithm and got speedups of 7, 3000, and 13000 times for gen400_p0.9_55, gen400_p0.9_65, and gen400_p0.9_75 instances correspondingly.     

Pareto mimic algorithm: An approach to the team orienteering problem

The team orienteering problem is an important variant of the vehicle routing problem. In this paper, a new algorithm, called Pareto mimic algorithm, is proposed to deal with it. This algorithm maintains a population of incumbent solutions which are updated using Pareto dominance. It uses a new operator, called mimic operator, to generate a new solution by imitating an incumbent solution. Furthermore, to improve the quality of a solution, it employs an operator, called swallow operator which attempts to swallow (or insert) an infeasible node and then repair the resulting infeasible solution. A comparative study supports the effectiveness of the proposed algorithm, especially, our algorithm can quickly find new better results for several large-scale instances. We also demonstrate that Pareto mimic algorithm can be generalized to solve other routing problems, e.g., the capacitated vehicle routing problem.     

An Arborescent Network Formulation and Dual Ascent Based Procedure for the Two-Stage Multi-Item Dynamic Demand Lotsize Problem

Traditional approaches for modeling and solving dynamic demand lotsize problems are based on Zangwill's single-source network and dynamic programming algorithms. In this paper, we propose an arborescent fixed-charge network (ARBNET) programming model and dual ascent based branch-and-bound procedure for the two-stage multi-item dynamic demand lotsize problem. Computational results show that the new approach is significantly more efficient than earlier solution strategies. The largest set of problems that could be solved using dynamic programming contained 4 end items and 12 time periods, and required 475.38 CPU seconds per problem. The dual ascent algorithms averaged .06 CPU seconds for this problem set, and problems with 30 end items and 24 time periods were solved in 85.65 CPU seconds. Similar results verify the superiority of the new approach for handling backlogged demand. An additional advantage of the algorithm is the availability of a feasible solution, with a known worst-case optimality gap, throughout the problem-solving process.     

FIRM EXPANSION THROUGH FRANCHISING: A MODEL AND SOLUTION PROCEDURES

This paper presents a practical model for firm expansion through franchising. The model allows the possibility of opening both company-owned and franchised stores. The objective is to maximize the expected returns to the franchisor from both types of stores, subject to the total capital outlay budget and the excess capacity available at each warehouse. A relaxation for this problem is studied and a heuristic solution procedure that makes use of this relaxation is developed. Experimental results over a wide range of problem structures show this solution methodology to be very effective, with gaps between feasible solution values and upper bounds generally in the 0 to 1 percent range. An efficient branch-and-bound code also is developed. This code is tested on problems with up to 100 potential store locations and 20 regions. It is found to be at least two orders of magnitude faster than a state-of-the-art commercial integer programming package.     

On approximation of the fixed charge transportation problem

In this paper we present a new approximation for computing lower bound for the fixed charge transportation problem (FCTP). The lower bounds thus generated delivered 87% optimal solutions for 56 randomly generated small, up to 6×10 in size, problems in an experimental design. For somewhat larger, 10×10 and 10×15 size problems, the lower bounds delivered an average error of 5%, approximately, using a fraction of CPU times as compared to CPLEX to solve these problems. The proposed lower bound may be used as a superior initial solution with any other existing branch-and-bound method or tabu search heuristic procedure to enhance convergence to the optimal solution for large size problems which cannot be solved by CPLEX due to time constraints.     

Branch-and-Bound Strategies for the Log Bucking Problem

Tree bucking is the initial production process in converting felled trees into useable wood products. This process has been previously modelled as a dynamic programming problem. Unlike other production problems that have been modelled as dynamic programming problems, there have been no serious attempts to formulate this problem as a branch-and-bound model and then examine the model's performance. This research develops the tree bucking problem as a branch-and-bound model to be tested by varying several parameters. The testing is performed in two phases: (1) a sensitivity analysis is performed to test two key parameters used by the model, and (2) branching strategies are tested on various problem scenarios. The size of the solution sets searched by the technique vary from as low as 40 to as many as 41,000 possible combinations.     

An ant colony optimization approach for the proportionate multiprocessor open shop

Multiprocessor open shop makes a generalization to classical open shop by allowing parallel machines for the same task. Scheduling of this shop environment to minimize the makespan is a strongly NP-Hard problem. Despite its wide application areas in industry, the research in the field is still limited. In this paper, the proportionate case is considered where a task requires a fixed processing time independent of the job identity. A novel highly efficient solution representation is developed for the problem. An ant colony optimization model based on this representation is proposed with makespan minimization objective. It carries out a random exploration of the solution space and allows to search for good solution characteristics in a less time-consuming way. The algorithm performs full exploitation of search knowledge, and it successfully incorporates problem knowledge. To increase solution quality, a local exploration approach analogous to a local search, is further employed on the solution constructed. The proposed algorithm is tested over 100 benchmark instances from the literature. It outperforms the current state-of-the-art algorithm both in terms of solution quality and computational time.

     

Commercial territory design planning with realignment and disjoint assignment requirements

A territory design problem motivated by a bottled beverage distribution company is addressed. The problem consists of finding a partition of the entire set of city blocks into a given number of territories subject to several planning criteria. Each unit has three measurable activities associated to it, namely, number of customers, product demand, and workload. The plan must satisfy planning criteria such as territory compactness, territory balancing with respect to each of the block activity measures, and territory connectivity, meaning that there must exist a path between any pair of units in a territory totally contained in it. In addition, there are some disjoint assignment requirements establishing that some specified units must be assigned to different territories, and a similarity with existing plan requirement. An optimal design is one that minimizes a measure of territory dispersion and similarity with existing design. A mixed-integer linear programming model is presented. This model is unique in the commercial territory design literature as it incorporates the disjoint assignment requirements and similarity with existing plan. Previous methods developed for related commercial districting problems are not applicable. A solution procedure based on an iterative cut generation strategy within a branch-and-bound framework is proposed. The procedure aims at solving large-scale instances by incorporating several algorithmic strategies that helped reduce the problem size. These strategies are evaluated and tested on some real-world instances of 5000 and 10,000 basic units. The empirical results show the effectiveness of the proposed method and strategies in finding near optimal solutions to these very large instances at a reasonably small computational effort.     

Multiple phase neighborhood Search—GRASP based on Lagrangean relaxation, random backtracking Lin–Kernighan and path relinking for the TSP

In this paper, a new modified version of Greedy Randomized Adaptive Search Procedure (GRASP), called Multiple Phase Neighborhood Search—GRASP (MPNS-GRASP), is proposed for the solution of the Traveling Salesman Problem. In this method, some procedures have been included to the classical GRASP algorithm in order to improve its performance and to cope with the major disadvantage of GRASP which is that it does not have a stopping criterion that will prevent the algorithm from spending time in iterations that give minor, if any, improvement in the solution. Thus, in MPNS-GRASP a stopping criterion based on Lagrangean Relaxation and Subgradient Optimization is proposed. Also, a different way for expanding the neighborhood search is used based on a new strategy, the Circle Restricted Local Search Moves strategy. A new variant of the Lin-Kernighan algorithm, called Random Backtracking Lin-Kernighan that helps the algorithm to diversify the search in non-promising regions of the search space is used in the Expanding Neighborhood Search phase of the algorithm. Finally, a Path Relinking Strategy is used in order to explore trajectories between elite solutions. The proposed algorithm is tested on numerous benchmark problems from TSPLIB with very satisfactory results.     

Multi-neighborhood based path relinking for two-sided assembly line balancing problem

This paper presents a multi-neighborhood based path relinking algorithm (MN-PR) for solving the two-sided assembly line balancing problem. By incorporating an effective local search into a path relinking framework, the proposed MN-PR algorithm integrates a number of distinguishing features, such as a multi-neighborhood based local search procedure, a dedicated path relinking operator to generate new solutions and a strategy to fix an infeasible solution generated by the path relinking procedure to a feasible one. Our proposed MN-PR algorithm is tested on a set of totally 45 public instances widely used in the literature. Comparisons with other reference algorithms show the efficacy of the proposed algorithm in terms of the solution quality. Particularly, the proposed MN-PR algorithm is able to improve the best upper bounds for one instance with 65 tasks and 326 cycle time. This paper also presents an analysis to show the significance of the main components of the proposed algorithm.