A prototype column generation strategy for the multiple container loading problem

The multiple container loading cost minimization problem (MCLCMP) is a practical and useful problem in the transportation industry, where products of various dimensions are to be loaded into containers of various sizes so as to minimize the total shipping cost. The MCLCMP can be naturally formulated as a set cover problem and solved using column generation techniques, which is a popular method for handling huge numbers of variables. However, the direct application of column generation is not effective because feasible solutions to the pricing subproblem is required, which for the MCLCMP is NP-hard. We show that efficiency can be greatly improved by generating prototypes that approximate feasible solutions to the pricing problem rather than actual columns. For many hard combinatorial problems, the subproblem in column generation based algorithms is NP-hard; if suitable prototypes can be quickly generated that approximate feasible solutions, then our strategy can also be applied to speed up these algorithms.     

多层防御模式下武器目标分配决策的群体智能优化算法

武器目标分配(WTA)是军事运筹学中经典的NP完全问题,迄今为止未找到求精确解的多项式时间算法.针对武器数量、布防空间、运行维护成本以及人力资源等多约束下的多层防御WTA问题,采用粒子群优化(PSO)和蚁群优化(ACO)两种群体智能算法求解.给出了PSO和ACO算法实现方案,通过一个算例评估两个算法的性能.结果表明,两种算法都能给出高质量的近似最优解,对求解WTA问题是有效的.PSO在解的质量、算法鲁棒性和计算效率方面均优于ACO.     

Problem difficulty of real instances of convoy planning

Moving men and materials in large numbers and quantities is a long-standing military problem faced by all arms. An important part of this is the routing of convoys so that they reach their correct destinations in the shortest time. The optimization problem at the heart of this problem is referred to as the convoy movement problem. Previous work on the convoy movement problem has made the assumption that the problem is difficult in practice because of the NP-hardness of the problem in combination with the limited success of early approaches based on genetic algorithms. As a result subsequent work has focused on mathematical programming-based methods, principally Lagrangian relaxation. In this paper, we demonstrate that a straightforward reformulation of the problem renders the real-world like instances, used to benchmark previous approaches, amenable to solution by simple heuristics. The main lessons learnt from this work is that analysis of the problem in conjunction with simple algorithms can, in practice, yield surprisingly effective solutions.     

Finding preferred subsets of Pareto optimal solutions

Multi-objective optimization algorithms can generate large sets of Pareto optimal (non-dominated) solutions. Identifying the best solutions across a very large number of Pareto optimal solutions can be a challenge. Therefore it is useful for the decision-maker to be able to obtain a small set of preferred Pareto optimal solutions. This paper analyzes a discrete optimization problem introduced to obtain optimal subsets of solutions from large sets of Pareto optimal solutions. This discrete optimization problem is proven to be NP-hard. Two exact algorithms and five heuristics are presented to address this problem. Five test problems are used to compare the performances of these algorithms and heuristics. The results suggest that preferred subset of Pareto optimal solutions can be efficiently obtained using the heuristics, while for smaller problems, exact algorithms can be applied.     

相异路径选择问题的模型与仿真结果研究

相异路径选线问题考虑的是,给定一运输网络的源宿接点,找出源宿节点之间在空间上有差异的路径,多个相异路径对于军事后勤供应,有害物品运输等在异常情况（如原来的最佳线路因气候等原因不可用）下的决策,具有重要意义。本着重对四种生成空间相异路径的算法进行了分析和评价,并构建了基于边的通道最短路的相异路径的算法,在此基础上,主要对IRM,GSP和EGSP给出了仿真实验计算结果,通过对结果的分析,找到了影响结果的几个关键因素。     

Polynomial Algorithms for a Class of Discrete Minmax Linear Programming Problems

We consider the problem of obtaining integer solutions to a minmax linear programming problem. Although this general problem is NP-complete, it is shown that a restricted version of this problem can be solved in polynomial time. For this restricted class of problems two polynomial time algorithms are suggested, one of which is strongly polynomial whenever its continuous analogue and an associated linear programming problem can be solved by a strongly polynomial algorithm. Our algorithms can also be used to obtain integer solutions for the minmax transportation problem with an inequality budget constraint. The equality constrained version of this problem is shown to be NP-complete. We also provide some new insights into the solution procedures for the continuous minmax linear programming problem.     

Optimal search strategies using simultaneous generalized hill climbing algorithms

Optimal search strategies for conducting reconnaissance, surveillance or search and rescue operations with limited assets are of significant interest to military decision makers. Multiple search platforms with varying capabilities can be deployed individually or simultaneously for these operations (e.g., helicopters, fixed wing or satellite). Due to the timeliness required in these operations, efficient use of available search platforms is critical to the success of such missions. Designing optimal search strategies over multiple search platforms can be modeled and solved as a multiple traveling salesman problem (MTSP). This paper demonstrates how simultaneous generalized hill climbing algorithms (SGHC) can be used to determine optimal search strategies over multiple search platforms for the MTSP. Computational results with SGHC algorithms applied to the MTSP are reported. These results demonstrate that when limited computing budgets are available, optimal/near-optimal search strategies over multiple search platforms can be obtained more efficiently using SGHC algorithms compared to other generalized hill climbing algorithms. Applications and extensions of this research to other military applications are also discussed.     

Properties and Solution Methods for Large Location—Allocation Problems

Location-allocation with l _p distances is studied. It is shown that this structure can be expressed as a concave minimization programming problem. Since concave minimization algorithms are not yet well developed, five solution methods are developed which utilize the special properties of the location-allocation problem. Using the rectilinear distance measure, two of these algorithms achieved optimal solutions in all 102 test problems for which solutions were known. The algorithms can be applied to much larger problems than any existing exact methods.     

单体型装配问题及其算法

单核苷酸多态性(SNP)单体型装配问题就是从给定的来自某人染色体的SNP片段中去除错误,重构出尽可能与原来片段一致的单体型.这个问题有几个不同的模型最少片段去除(MFR)问题,最少SNP去除(MSR)问题以及最少错误纠正(MEC)问题.前两个问题的复杂性与算法已有一些学者研究过.第三个问题已被证明是NP完全问题,但这个问题的实际算法还没有.该文对MEC问题给出了一个分支定界算法,这个算法能得到问题的全局最优解.通过这个算法对实际数据的计算说明了MEC模型的合理性,即在一定条件下,通过修正最少的错误重构出的单体型确实是真实的单体型.由于分支定界算法对这样一个NP完全问题不能在可接受的时间内解规模较大的问题,文中又给出了求解MEC问题的两个基于动态聚类的算法,以便对规模较大的问题在可接受的时间内得到近似最优解.数值实际表明这两个算法很快,很有效.这两个算法总能得到与分支定界找到的全局最优解很接近的近似最优解.鉴于MEC问题是NP完全的,这两个算法是有效的、实际的算法.     

A hybrid GRASP/VND algorithm for two- and three-dimensional bin packing

The three-dimensional bin packing problem consists of packing a set of boxes into the minimum number of bins. In this paper we propose a new GRASP algorithm for solving three-dimensional bin packing problems which can also be directly applied to the two-dimensional case. The constructive phase is based on a maximal-space heuristic developed for the container loading problem. In the improvement phase, several new moves are designed and combined in a VND structure. The resulting hybrid GRASP/VND algorithm is simple and quite fast and the extensive computational results on test instances from the literature show that the quality of the solutions is equal to or better than that obtained by the best existing heuristic procedures.     

Finding all solutions of separable systems of piecewise-linear equations using integer programming

Finding all solutions of nonlinear or piecewise-linear equations is an important problem which is widely encountered in science and engineering. Various algorithms have been proposed for this problem. However, the implementation of these algorithms are generally difficult for non-experts or beginners. In this paper, an efficient method is proposed for finding all solutions of separable systems of piecewise-linear equations using integer programming. In this method, we formulate the problem of finding all solutions by a mixed integer programming problem, and solve it by a high-performance integer programming software such as GLPK, SCIP, or CPLEX. It is shown that the proposed method can be easily implemented without making complicated programs. It is also confirmed by numerical examples that the proposed method can find all solutions of medium-scale systems of piecewise-linear equations in practical computation time.     

A dynamic edge covering and scheduling problem: complexity results and approximation algorithms

We consider a new dynamic edge covering and scheduling problem that focuses on assigning resources to nodes in a network to minimize the amount of time required to process all edges in it. Resources need to be co-located at the endpoints of an edge for it to be processed and, therefore, this problem contains both edge covering and scheduling decisions. These new problems have motivating applications in traffic systems and military intelligence operations. We provide complexity results for the dynamic edge covering and scheduling problem over different types of networks. We then show that existing approximation algorithms for parallel machine scheduling problems can be leveraged to provide approximation algorithms for this new class of problems over certain types of networks.     

求解最小Steiner树的蚁群优化算法及其收敛性

最小Steiner树问题是NP难问题,它在通信网络等许多实际问题中有着广泛的应用．蚁群优化算法是最近提出的求解复杂组合优化问题的启发式算法．本文以无线传感器网络中的核心问题之一,路由问题为例,给出了求解最小Steiner树的蚁群优化算法的框架．把算法的迭代过程看作是离散时间的马尔科夫过程,证明了在一定的条件下,该算法所产生的解能以任意接近于1的概率收敛到路由问题的最优解．     

A branch-and-price algorithm to solve the integrated berth allocation and yard assignment problem in bulk ports

In this research, two crucial optimization problems of berth allocation and yard assignment in the context of bulk ports are studied. We discuss how these problems are interrelated and can be combined and solved as a single large scale optimization problem. More importantly we highlight the differences in operations between bulk ports and container terminals which highlights the need to devise specific solutions for bulk ports. The objective is to minimize the total service time of vessels berthing at the port. We propose an exact solution algorithm based on a branch and price framework to solve the integrated problem. In the proposed model, the master problem is formulated as a set-partitioning problem, and subproblems to identify columns with negative reduced costs are solved using mixed integer programming. To obtain sub-optimal solutions quickly, a metaheuristic approach based on critical-shaking neighborhood search is presented. The proposed algorithms are tested and validated through numerical experiments based on instances inspired from real bulk port data. The results indicate that the algorithms can be successfully used to solve instances containing up to 40 vessels within reasonable computational time.     

Distributed computation of Pareto solutions inn-player games

The problem of computing Pareto optimal solutions with distributed algorithms is considered inn-player games. We shall first formulate a new geometric problem for finding Pareto solutions. It involves solving joint tangents for the players' objective functions. This problem can then be solved with distributed iterative methods, and two such methods are presented. The principal results are related to the analysis of the geometric problem. We give conditions under which its solutions are Pareto optimal, characterize the solutions, and prove an existence theorem. There are two important reasons for the interest in distributed algorithms. First, they can carry computational advantages over centralized schemes. Second, they can be used in situations where the players do not know each others' objective functions.     

Decomposition based and branch and bound global optimization approaches for the phase equilibrium problem

An increasingly popular approach when solving the phase and chemical equilibrium problem is to pose it as an optimization problem. However, difficulties are encountered due to the highly nonlinear nature of the models used to represent the behavior of the fluids, and because of the existence of multiple local solutions. This work shows how it is possible to guarantee -global solutions for a certain important class of the phase and chemical equilibrium problem, namely when the liquid phase can be modeled using neither the Non-Random Two-Liquid (NRTL) equation, or the UNIversal QUAsi Chemical (UNIQUAC) equation. Ideal vapor phases are easily incorporated into the global optimization framework. A numberof interesting properties are described which drastically alter the structure of the respective problems. For the NRTL equation, it is shown that the formulation can be converted into a biconvex optimization problem. The GOP algorithm of Floudas and Visweswaran [8, 9] can then be used to obtain -global solutions in this case. For the UNIQUAC equation, the new properties show how the objective function can be transformed into the difference of two convex functions (i.e. a D.C. programming problem is obtained), where the concave portion is separable. A branch and bound algorithm based on that of Falk and Soland [6] is used to guarantee convergence to an -global solution. Examples are presented which demonstrate the performance of both algorithms.     

A proposal for a hybrid meta-strategy for combinatorial optimization problems

In this paper, we propose an algorithm named BDS (Bound-Driven Search) that combines features of exact and approximate methods. The proposed procedure may be seen as a local search algorithm that systematically explores (in a branch-and bound sense) the most promising nodes, thus preventing solutions from being reevaluated. Additionally, it can be regarded as an exact method as it may be able to guarantee that the solution found is optimal. We present the application of this new algorithm to a specific problem domain: the permutation flow shop scheduling problem with makespan objective. The subsequent computational experiments are encouraging, as the algorithm is able to yield exact or near exact solutions to most instances of the problem. Furthermore, the algorithm outperforms one of the best state-of-the-art algorithms for the problem.     

供给总量限定需求区间约束型运输问题——时限费用优化模型与算法

本文目的是为建立与运输问题有关的决策支持系统提供方便.本文建立了供给总量限定需求区间约束型运输问题的对时限与费用两个目标进行优化的多目标规划模型,给出了求解模型的算法,并举例说明了算法的应用.该算法能求得问题的最优解,并具有易于编程实现、收敛性好等优点.数值实验表明该算法有较高的计算效率,可用于求解某些类型的指派问题.     

Multi Colony Ant Algorithms

In multi colony ant algorithms several colonies of ants cooperate in finding good solutions for an optimization problem. At certain time steps the colonies exchange information about good solutions. If the amount of exchanged information is not too large multi colony ant algorithms can be easily parallelized in a natural way by placing the colonies on different processors. In this paper we study the behaviour of multi colony ant algorithms with different kinds of information exchange between the colonies. Moreover we compare the behaviour of different numbers of colonies with a multi start single colony ant algorithm. As test problems we use the Traveling Salesperson problem and the Quadratic Assignment problem.     

Multi-armed bandit-based hyper-heuristics for combinatorial optimization problems

There are significant research opportunities in the integration of Machine Learning (ML) methods and Combinatorial Optimization Problems (COPs). In this work, we focus on metaheuristics to solve COPs that have an important learning component. These algorithms must explore a solution space and learn from the information they obtain in order to find high-quality solutions. Among the metaheuristics, we study Hyper-Heuristics (HHs), algorithms that, given a number of low-level heuristics, iteratively select and apply heuristics to a solution. The HH we consider has a Markov model to produce sequences of low-level heuristics, which we combine with a Multi-Armed Bandit Problem (MAB)-based method to learn its parameters. This work proposes several improvements to the HH metaheuristic that yields a better learning for solving problem instances. Specifically, this is the first work in HHs to present Exponential Weights for Exploration and Exploitation (EXP3) as a learning method, an algorithm that is able to deal with adversarial settings. We also present a case study for the Vehicle Routing Problem with Time Windows (VRPTW), for which we include a list of low-level heuristics that have been proposed in the literature. We show that our algorithms can handle a large and diverse list of heuristics, illustrating that they can be easily configured to solve COPs of different nature. The computational results indicate that our algorithms are competitive methods for the VRPTW (2.16% gap on average with respect to the best known solutions), demonstrating the potential of these algorithms to solve COPs. Finally, we show how algorithms can even detect low-level heuristics that do not contribute to finding better solutions to the problem.