A new iterative-doubling Greedy–Lookahead algorithm for the single container loading problem

The aim of the Single Container Loading Problem (SCLP) is to pack three-dimensional boxes into a three-dimensional container so as to maximize the volume utilization of the container. We propose a new block building approach that constructs packings by placing one block (of boxes) at a time until no more boxes can be loaded. The key to obtaining high quality solutions is to select the right block to place into the right free space cuboid (or residual space) in the container. We propose a new heuristic for evaluating the fitness of residual spaces, and use a tree search to decide the best residual space-block pair at each step. The resultant algorithm outperforms the best known algorithms based on the 1600 commonly used benchmark instances even when given fewer computational resources. We also adapted our approach to address the full support constraint. The computational results for the full support support variant on the 1600 instances similarly show a significant improvement over existing techniques even when given substantially fewer computational resources.     

Perturbation resilience for the facility location problem

We analyze a simple local search heuristic for the facility location problem using the notion of perturbation resilience: an instance is $\gamma$-perturbation resilient if all costs can be perturbed by a factor of $\gamma$ without changing the optimal solution.We prove that local search for FLP succeeds in finding the optimal solution for $\gamma$-perturbation resilient instances for $\gamma \ge 3$, and we show that this is tight.     

A hybrid simulation-optimization algorithm for the Hamiltonian cycle problem

In this paper, we propose a new hybrid algorithm for the Hamiltonian cycle problem by synthesizing the Cross Entropy method and Markov decision processes. In particular, this new algorithm assigns a random length to each arc and alters the Hamiltonian cycle problem to the travelling salesman problem. Thus, there is now a probability corresponding to each arc that denotes the probability of the event “this arc is located on the shortest tour.” Those probabilities are then updated as in cross entropy method and used to set a suitable linear programming model. If the solution of the latter yields any tour, the graph is Hamiltonian. Numerical results reveal that when the size of graph is small, say less than 50 nodes, there is a high chance the algorithm will be terminated in its cross entropy component by simply generating a Hamiltonian cycle, randomly. However, for larger graphs, in most of the tests the algorithm terminated in its optimization component (by solving the proposed linear program).     

A branch-and-cut procedure for the Udine Course Timetabling problem

A branch-and-cut procedure for the Udine Course Timetabling problem is described. Simple compact integer linear programming formulations of the problem employ only binary variables. In contrast, we give a formulation with fewer variables by using a mix of binary and general integer variables. This formulation has an exponential number of constraints, which are added only upon violation. The number of constraints is exponential. However, this is only with respect to the upper bound on the general integer variables, which is the number of periods per day in the Udine Course Timetabling problem.     

A comparison of problem decomposition techniques for the FAP

This paper proposes a problem decomposition approach to solve hard Frequency Assignment Problem instances with standard meta-heuristics. The proposed technique aims to divide the initial problem into a number of easier subproblems, solve them and then recompose the partial solutions into one of the original problem. We consider the COST-259 MI-FAP instances and other Cardiff University test problems in order to simulate larger and more realistic networks. For both benchmarks the standard implementations of meta-heuristics do not generally produce a satisfactory performance within reasonable times of execution. However, the decomposed assignment approach can improve their results, both in terms of solution quality and runtime.     

A memetic algorithm based on a NSGAII scheme for the flexible job-shop scheduling problem

The Flexible Job-Shop Scheduling Problem is concerned with the determination of a sequence of jobs, consisting of many operations, on different machines, satisfying several parallel goals. We introduce a Memetic Algorithm, based on the NSGAII (Non-Dominated Sorting Genetic Algorithm II) acting on two chromosomes, to solve this problem. The algorithm adds, to the genetic stage, a local search procedure (Simulated Annealing). We have assessed its efficiency by running the algorithm on multiple objective instances of the problem. We draw statistics from those runs, which indicate that this Memetic Algorithm yields good and low-cost solutions.     

A family of NCP functions and a descent method for the nonlinear complementarity problem

In last decades, there has been much effort on the solution and the analysis of the nonlinear complementarity problem (NCP) by reformulating NCP as an unconstrained minimization involving an NCP function. In this paper, we propose a family of new NCP functions, which include the Fischer-Burmeister function as a special case, based on a p-norm with p being any fixed real number in the interval (1,+∞), and show several favorable properties of the proposed functions. In addition, we also propose a descent algorithm that is indeed derivative-free for solving the unconstrained minimization based on the merit functions from the proposed NCP functions. Numerical results for the test problems from MCPLIB indicate that the descent algorithm has better performance when the parameter p decreases in (1,+∞). This implies that the merit functions associated with p∈(1,2), for example p=1.5, are more effective in numerical computations than the Fischer-Burmeister merit function, which exactly corresponds to p=2. J.-S. Chen is a member of Mathematics Division, National Center for Theoretical Sciences, Taipei Office. J.-S. Chen’s work is partially supported by National Science Council of Taiwan.     

Semismooth Newton Schwarz iterative methods for the linear complementarity problem

Semismooth Newton method is an effective method for solving a nonsmooth equation, which arises from a reformulation of the complementarity problem. Under appropriate conditions, we verify the monotone convergence of the method. We also present semismooth Newton Schwarz iterative methods for the nonsmooth equation. Under suitable conditions, the methods exhibit monotone and superlinear convergence properties.     

Bi-level programming model of container port game in the container transport supernetwork

In order to analyze the behavior of every participant in decision making, the container transportation business process and the container transportation supernetwork are presented. Furthermore, two kinds of container transport supernetwork equilibrium models are established. Then we established EPEC model, in which the upper layer ports go on non-cooperation competition while the lower layer shippers compete for the path of minimum expense. Finally, a simulation example is employed to show the validity and rationality of bi-level programming model.     

An ant colony optimization approach for the multidimensional knapsack problem

Ant colony optimization is a metaheuristic that has been applied to a variety of combinatorial optimization problems. In this paper, an ant colony optimization approach is proposed to deal with the multidimensional knapsack problem. It is an extension of Max Min Ant System which imposes lower and upper trail limits on pheromone values to avoid stagnation. In order to choose the lower trail limit, we provide a new method which takes into account the influence of heuristic information. Furthermore, a local search procedure is proposed to improve the solutions constructed by ants. Computational experiments on benchmark problems are carried out. The results show that the proposed algorithm can compete efficiently with other promising approaches to the problem.     

Optimization of container inspection strategy via a genetic algorithm

It is estimated that 90% of the world’s freight is moved as containerized cargo, with over 125 million TEUs (Twenty foot Equivalent Units) of container being shipped by 2010. To inspect this volume of cargo for explosives, drugs or other contraband is a daunting challenge. This paper presents an optimization technique for developing an inspection strategy that will provide a specified detection rate for containers containing contraband at a minimum cost. Nested genetic algorithms are employed to optimize the topology of an inspection strategy decision tree, the placement of sensors on the tree and the sensor thresholds which partition suspicious containers (containers believed to contain contraband) from innocuous containers (containers which are believed to be free of contraband). The results of this optimization technique are compared to previously published techniques.     

Neighborhood analysis: a case study on curriculum-based course timetabling

In this paper, we present an in-depth analysis of neighborhood relations for local search algorithms. Using a curriculum-based course timetabling problem as a case study, we investigate the search capability of four neighborhoods based on three evaluation criteria: percentage of improving neighbors, improvement strength and search steps. This analysis shows clear correlations of the search performance of a neighborhood with these criteria and provides useful insights on the very nature of the neighborhood. This study helps understand why a neighborhood performs better than another one and why and how some neighborhoods can be favorably combined to increase their search power. This study reduces the existing gap between reporting experimental assessments of local search-based algorithms and understanding their behaviors.     

A combinatorial optimization algorithm for solving the branchwidth problem

In this paper, we consider the problem of computing an optimal branch decomposition of a graph. Branch decompositions and branchwidth were introduced by Robertson and Seymour in their series of papers that proved the Graph Minors Theorem. Branch decompositions have proven to be useful in solving many NP-hard problems, such as the traveling salesman, independent set, and ring routing problems, by means of combinatorial algorithms that operate on branch decompositions. We develop an implicit enumeration algorithm for the optimal branch decomposition problem and examine its performance on a set of classical graph instances.     

An improved multi-staged algorithmic process for the solution of the examination timetabling problem

The efficient creation of examination timetables is a recurring and important problem for universities worldwide. Good timetables typically are characterized by balanced distances between consecutive exams for all students. In this contribution an approach for the examination timetabling problem as defined in the second International Timetabling Competition () is presented. The solution approach is managed on the top level by GRASP (Greedy Randomized Adaptive Search Procedure) and it involves several optimization algorithms, heuristics and metaheuristics. A construction phase is executed first producing a relatively high quality feasible solution and an improvement phase follows that further ameliorates the produced timetable. Each phase consists of stages that are consumed in a circular fashion. The procedure produces feasible solutions for each dataset provided under the runtime limit imposed by the rules of the ITC07 competition. Results are presented and analyzed.     

A comparison of feasible direction methods for the stochastic transportation problem

The feasible direction method of Frank and Wolfe has been claimed to be efficient for solving the stochastic transportation problem. While this is true for very moderate accuracy requirements, substantially more efficient algorithms are otherwise diagonalized Newton and conjugate Frank–Wolfe algorithms, which we describe and evaluate. Like the Frank–Wolfe algorithm, these two algorithms take advantage of the structure of the stochastic transportation problem. We also introduce a Frank–Wolfe type algorithm with multi-dimensional search; this search procedure exploits the Cartesian product structure of the problem. Numerical results for two classic test problem sets are given. The three new methods that are considered are shown to be superior to the Frank–Wolfe method, and also to an earlier suggested heuristic acceleration of the Frank–Wolfe method.     

Exact asymptotics for the stationary distribution of a Markov chain: a production model

We derive rough and exact asymptotic expressions for the stationary distribution π of a Markov chain arising in a queueing/production context. The approach we develop can also handle “cascades,” which are situations where the fluid limit of the large deviation path from the origin to the increasingly rare event is nonlinear. Our approach considers a process that starts at the rare event. In our production example, we can have two sequences of states that asymptotically lie on the same line, yet π has different asymptotics on the two sequences.     

Simple and fast surrogate constraint heuristics for the maximum independent set problem

In a recent paper Glover (J. Heuristics 9:175–227, 2003) discussed a variety of surrogate constraint-based heuristics for solving optimization problems in graphs. The key ideas put forth in the paper were illustrated by giving specializations designed for certain covering and coloring problems. In particular, a family of methods designed for the maximum cardinality independent set problem was presented. In this paper we report on the efficiency and effectiveness of these methods based on considerable computational testing carried out on test problems from the literature as well as some new test problems.     

Approximate and exact algorithms for the double-constrained two-dimensional guillotine cutting stock problem

In this paper, we propose approximate and exact algorithms for the double constrained two-dimensional guillotine cutting stock problem (DCTDC). The approximate algorithm is a two-stage procedure. The first stage attempts to produce a starting feasible solution to DCTDC by solving a single constrained two dimensional cutting problem, CDTC. If the solution to CTDC is not feasible to DCTDC, the second stage is used to eliminate non-feasibility. The exact algorithm is a branch-and-bound that uses efficient lower and upper bounding schemes. It starts with a lower bound reached by the approximate two-stage algorithm. At each internal node of the branching tree, a tailored upper bound is obtained by solving (relaxed) knapsack problems. To speed up the branch and bound, we implement, in addition to ordered data structures of lists, symmetry, duplicate, and non-feasibility detection strategies which fathom some unnecessary branches. We evaluate the performance of the algorithm on different problem instances which can become benchmark problems for the cutting and packing literature.     

Tabu search for the linear ordering problem with cumulative costs

Given a matrix of weights, the Linear Ordering Problem (LOP) consists of finding a permutation of the columns and rows in order to maximize the sum of the weights in the upper triangle. This well known NP-complete problem can also be formulated on a complete weighted graph, where the objective is to find an acyclic tournament that maximizes the sum of arc weights. The variant of the LOP that we target here was recently introduced and adds a cumulative non-linear propagation of the costs to the sum of the arc weights. We first review the previous methods for the LOP and for this variant with cumulative costs (LOPCC) and then propose a heuristic algorithm for the LOPCC, which is based on the Tabu Search (TS) methodology. Our method achieves search intensification and diversification through the implementation of both short and long term memory structures. Our extensive experimentation with 224 instances shows that the proposed procedure outperforms existing methods in terms of solution quality and has reasonable computing-time requirements.