Constraint Propagation in Graph Coloring

In this paper we propose a method for integrating constraint propagation algorithms into an optimization procedure for vertex coloring with the goal of finding improved lower bounds. The key point we address is how to get instances of Constraint Satisfaction Problems (CSPs) from a graph coloring problem in order to give rise to new lower bounds outperforming the maximum clique bound. More precisely, the algorithms presented have the common goal of finding CSPs in the graph for which infeasibility can be proven. This is achieved by means of constraint propagation techniques which allow the algorithms to eliminate inconsistencies in the CSPs by updating domains dynamically and rendering such infeasibilities explicit. At the end of this process we use the largest CSP for which it has not been possible to prove infeasibility as an input for an algorithm which enlarges such CSP to get a feasible coloring. We experimented with a set of middle-high density graphs with quite a large difference between the maximum clique and the chromatic number.     

A Hybrid Algorithm for the Non-Guillotine Cutting Problem

In this article, a meta-heuristic method to solve the non-guillotine cutting stock problem is proposed. The method is based on a combination between the basic principles of the constructive and evolutive methods. With an adequate management of the parameters involved, the method allows regulation of the solution quality to computational effort relationship. This method is applied to a particular case of cutting problems, with which the computational behaviors is evaluated. In fact, 1000 instances of the problem have been classified according to their combinatorial degree and then the efficiency and robustness of the method have been tested. The final results conclude that the proposed method generates an average error close to 2.18% with respect to optimal solutions. It has also been verified that the method yields solutions for all of the instances examined; something that has not been achieved with an exact constructive method, which was also implemented. Comparison of the running times demonstrates the superiority of the proposed method as compared with the exact method.     

A scatter-search-based learning algorithm for neural network training

In this article, we propose a new scatter-search-based learning algorithm to train feed-forward neural networks. The algorithm also incorporates elements of tabu search. We describe the elements of the new approach and test the new learning algorithm on a series of classification problems. The test results demonstrate that the algorithm is significantly superior to several implementations of back-propagation.     

Multi-Path Approach for Reliability-Redundancy Allocation Using a Scaling Method

The reliability-redundancy allocation problem is an optimization problem that achieves better system reliability by determining levels of component redundancies and reliabilities simultaneously. The problem is classified with the hardest problems in the reliability optimization field because the decision variables are mixed-integer and the system reliability function is nonlinear, non-separable, and non-convex. Thus, iterative heuristics are highly recommended for solving the problem due to their reasonable solution quality and relatively short computation time. At present, most iterative heuristics use sensitivity factors to select an appropriate variable which significantly improves the system reliability. The sensitivity factor represents the impact amount of each variable to the system reliability at a designated iteration. However, these heuristics are inefficient in terms of solution quality and computation time because the sensitivity factor calculations are performed only at integer variables. It results in degradation of the exploration and growth in the number of subsequent continuous nonlinear programming (NLP) subproblems. To overcome the drawbacks of existing iterative heuristics, we propose a new scaling method based on the multi-path iterative heuristics introduced by Ha (2004). The scaling method is able to compute sensitivity factors for all decision variables and results in a decreased number of NLP subproblems. In addition, the approximation heuristic for NLP subproblems helps to avoid redundant computation of NLP subproblems caused by outlined solution candidates. Numerical experimental results show that the proposed heuristic is superior to the best existing heuristic in terms of solution quality and computation time.     

Using Lagrangian dual information to generate degree constrained spanning trees

In this paper, a Lagrangian-based heuristic is proposed for the degree constrained minimum spanning tree problem. The heuristic uses Lagrangian relaxation information to guide the construction of feasible solutions to the problem. The scheme operates, within a Lagrangian relaxation framework, with calls to a greedy construction heuristic, followed by a heuristic improvement procedure. A look ahead infeasibility prevention mechanism, introduced into the greedy heuristic, allowed us to solve instances of the problem where some of the vertices are restricted to having degrees 1 or 2. Furthermore, in order to cut down on CPU time, a restricted version of the original problem is formulated and used to generate feasible solutions. Extensive computational experiments were conducted and indicate that the proposed heuristic is competitive with the best heuristics and metaheuristics in the literature.     

空中加油问题的递推模型与调度策略

首先对空中加油问题进行了分析,提取了相关性质,在此基础上建立了问题的递推模型.根据该模型,提出了一种启发式搜索算法.该算法计算复杂度低,适用性好.对应于辅机是否可以多次起飞,该算法分为两子算法.对这两种不同情况下的具体问题,设计了相关的优化函数.所有算法都在计算机中运行,并得到了相应结果.值得指出的是,提出的启发式搜索算法十分高效.对于问题1和问题2,该算法所得解是约束条件下的最优调度策略.对于问题3,问题4,问题5,该算法所得解逼近最优调度策略.     

Multiplicative Programming Problems: Analysis and Efficient Point Search Heuristic

Multiplicative programming problems are difficult global optimization problems known to be NP-hard. At the same time, these problems have some important applications in engineering, finance, economics, and other fields. This article has two purposes. The first is to present an analysis that shows several relationships between concave multiplicative programs and concave minimization problems, and between concave multiplicative programs and certain multiple-objective mathematical programs. The second purpose is to propose and report computational results for a heuristic efficient-point search algorithm that we have designed for use on linear multiplicative programming problems. To our knowledge, this is the first heuristic algorithm of its type. The theoretical and algorithmic results given in the article offer some potentially important new avenues for analyzing and solving multiplicative programming problems of various types.     

地区超市有时间窗口的固定路线运输问题

文章为一家本地超市设计了一套行之有效的固定路线运输问题方案，它的目标是在载量能力、最大允许行程时间及各分店营业时间和机动车停车时间窗口限制下的行车趟数的最小化、车辆利用率的最大化。也将考虑生长点、载量、可变需求和时间窗口对路线生成的影响。     

Solving the 0–1 proportional knapsack problem by sampling

In this paper, we deal with the proportional knapsack problem that is a variation on the ordinary knapsack problem. In the proportional knapsack problem, we look at filling an urn with objects having two characteristics: color and weight. The colors of the objects in the urn should be proportional to the distribution of the colors in the object universe, and the total weight of the objects in the urn should be as close as possible to the capacity of the urn. The formulation of the problem was motivated by a real-life application from the area of finance, called a dollar roll. We show that the proportional knapsack problem is NP-hard, and then, using sampling, develop a heuristic procedure for solving the problem.Partial support from the Fund for the Promotion of Research and from the Alexander Goldberg Memorial Fund at Technion is gratefully acknowledged.     

A framework for the probabilistic analysis of hierarchical planning systems

As we have argued in previous papers, multi-level decision problems can often be modeled as multi-stage stochastic programs, and hierarchical planning systems designed for their solution, when viewed as stochastic programming heuristics, can be subjected to analytical performance evaluation. The present paper gives a general formulation of such stochastic programs and provides a framework for the design and analysis of heuristics for their solution. The various ways to measure the performance of such heuristics are reviewed, and some relations between these measures are derived. Our concepts are illustrated on a simple two-level planning problem of a general nature and on a more complicated two-level scheduling problem.