Symmetric constraints in classification problems that permit replacement by functional constraints

Translated from Kibernetika i Sistemnyi Analiz, No. 4, pp. 72–80, July–August, 1993.     

基于蚁群算法的带平衡约束矩形布局问题的启发式求解

以卫星舱布局问题作为研究背景,求解了带平衡约束的矩形布局问题。采用启发式策略设计了分区域分步布局法,该策略将圆形卫星舱承重板分成4个区域,分区域同步进行布局。当所布矩形和区域都确定时,采用最左最底填充策略进行布局。该方法通过不干涉约束,使布局紧凑,通过控制系统质心的位置,使系统保持平衡。在启发式策略的基础上,设计了蚁群算法搜索优化定位次序,从而得到优化的布局。数值仿真结果表明,该布局方法具有优良的计算性能。     

Constructive heuristic algorithms for the open shop problem

In this paper we consider constructive heuristic algorithms for the open shop problem with minimization of the schedule length. By means of investigations of the structure of a feasible solution two types of heuristic algorithms are developed: construction of a rank-minimal schedule by solving successively weighted maximum cardinality matching problems and construction of an approximate schedule by applying insertion techniques combined with beam search. All presented algorithms are tested on benchmark problems from the literature. Our computational results demonstrate the excellent solution quality of our insertion algorithm, especially for greater job and machine numbers. For 29 of 30 benchmark problems with at least 10 jobs and 10 machines we improve the best known values obtained by tabu search.     

New heuristic algorithms for solving the planar p-median problem

In this paper we propose effective heuristics for the solution of the planar p-median problem. We develop a new distribution based variable neighborhood search and a new genetic algorithm, and also test a hybrid algorithm that combines these two approaches. The best results were obtained by the hybrid approach. The best known solution was found in 466 out of 470 runs, and the average solution was only 0.000016% above the best known solution on 47 well explored test instances of 654 and 1060 demand points and up to 150 facilities.     

Efficient heuristic algorithms for the weighted set covering problem

In this paper two heuristic algorithms are presented for the weighted set covering problem. The first algorithm uses a simple, polynomial procedure to construct feasible covering solutions. The procedure is shown to possess a worst case performance bound that is a function of the size of the problem. The second algorithm is a solution improvement procedure that attempts to form reduced cost composite solutions from available feasible covering solutions. Computational results are presented for both algorithms on several large set covering problems generated from airline crew scheduling data.     

New heuristic algorithms for the windy rural postman problem

In this paper we deal with the windy rural postman problem. This problem generalizes several important arc routing problems and has interesting real-life applications. Here, we present several heuristics whose study has lead to the design of a scatter search algorithm for the windy rural postman problem. Extensive computational experiments over different sets of instances, with sizes up to 988 nodes and 3952 edges, are also presented.     

Application of universal constraints in the analysis of classification algorithms

Translated from Kibernetika, No. 1, pp. 1–5, January–February, 1988.     

Exact and heuristic algorithms for the interval data robust assignment problem

We consider the Assignment Problem with interval data, where it is assumed that only upper and lower bounds are known for each cost coefficient. It is required to find a minmax regret assignment. The problem is known to be strongly NP-hard. We present and compare computationally several exact and heuristic methods, including Benders decomposition, using CPLEX, a variable depth neighborhood local search, and two hybrid population-based heuristics. We report results of extensive computational experiments.     

HEART: Unrelated parallel machines problem with precedence constraints for task scheduling in cloud computing using heuristic and meta-heuristic algorithms

Cloud computing is becoming a profitable technology because of it offers cost-effective IT solutions globally. A well-designed task scheduling algorithm ensures the optimal utilization of clouds resources and reducing execution time dynamically. This research article deals with the task scheduling of inter-dependent subtasks on unrelated parallel computing machines in a cloud computing environment. This article considers two variants of the problem-based on two different objective function values. The first variant considers the minimization of the total completion time objective function while the second variant considers the minimization of the makespan objective function. Heuristic and meta-heuristic (HEART) based algorithms are proposed to solve the task scheduling problems. These algorithms utilize the property of list scheduling algorithm of unrelated parallel machine scheduling problem. A mixed integer linear programming (MILP) formulation has been provided for the two variants of the problem. The optimal solution is obtained by solving MILP formulation using A Mathematical Programming Language (AMPL) software. Extensive numerical experiments have been performed to evaluate the performance of proposed algorithms. The solutions obtained by the proposed algorithms are found to out-perform the existing algorithms. The proposed algorithms can be used by cloud computing service providers (CCSPs) for enhancing their resources utilization to reduce their operating cost.     

Experimental evaluation of approximation and heuristic algorithms for the dominating paths problem

Monitoring flows on networks is a research area for which a number of applications are waiting for models and algorithms to face new problems emerging with a very high pace. In this paper we analyze a particular optimization problem, namely the Dominating Paths Problem (DPP), that has application in this field especially for urban transportation networks. Given an undirected graph G=(V,E) and a subset B⊆V of bound vertices, we look for a set of vertices M of minimum size such that each element of M is the origin of one or more paths, and, the set of all these paths dominates B. For this NP-hard problem, we present an approximation algorithm and new heuristic procedures extensively evaluated on a set of test instances. We defined two different sets of benchmarks: grid graphs and random graphs. Moreover, we included two test cases taken from real traffic networks. Computational results, discussed in the paper, give insights both on problem and on algorithms’ performance.     

Implementation analysis of efficient heuristic algorithms for the traveling salesman problem

The state-of-the-art of local search heuristics for the traveling salesman problem (TSP) is chiefly based on algorithms using the classical Lin–Kernighan (LK) procedure and the stem-and-cycle (S&C) ejection chain method. Critical aspects of implementing these algorithms efficiently and effectively rely on taking advantage of special data structures and on maintaining appropriate candidate lists to store and update potentially available moves. We report the outcomes of an extensive series of tests on problems ranging from 1000 to 1,000,000 nodes, showing that by intelligently exploiting elements of data structures and candidate lists routinely included in state-of-the-art TSP solution software, the S&C algorithm clearly outperforms all implementations of the LK procedure. Moreover, these outcomes are achieved without the use of special tuning and implementation tricks that are incorporated into the leading versions of the LK procedure to enhance their computational efficiency.     

Relationship between homogeneity and independence constraints for classification algorithms

We describe a set of functional universal constraints for classification algorithms that correspond to particular systems of symmetric universal constraints.Translated from Kibernetika, No. 2, pp. 108–112, March–April, 1991.     

Simple and integrated heuristic algorithms for scheduling tasks with time and resource constraints

We consider the problem of scheduling a set of n tasks in a system having r resources. Each task has an arbitrary, but known, processing time and a deadline, and may request use of a number of resources. A resource can be used either in shared mode or exclusive mode. In this article, we study algorithms used for determining whether or not a set of tasks is schedulable in such a system, and if so, determining a schedule for it. This scheduling problem is known to be NP-complete and hence we methodically study a set of heuristics that can be used by such an algorithm. Due to the complexity of the problem, simple heuristics do not perform satisfactorily. However, an algorithm that uses combinations of these simple heuristics works very well compared to an optimal algorithm that takes exponential time complexity. For the combination that performs the best, we also determine the scheduling costs as a function of the size of the task set scheduled.     

Exact and heuristic algorithms for the just-in-time scheduling problem in a batch processing system

Batch processing systems are commonly used in many different environments such as chemical and semiconductor industries. In this research, a just-in-time scheduling problem in a batch processing system is investigated. Minimization of total earliness and tardiness of the jobs with respect to a common due date is considered as the objective function. First, the research problem is formulated as a mixed integer linear programming model. Then, to find the optimal schedule for a predetermined set of batches, a dynamic programming algorithm is proposed. Based on the proposed dynamic programming algorithm, several heuristics are also developed. A lower bounding method is presented, and then a branch and bound algorithm is proposed to solve the problem optimally. To demonstrate the performance of the proposed algorithms, several computational experiments are conducted.     

A new heuristic algorithm for the circular packing problem with equilibrium constraints

The circular packing problem with equilibrium constraints is an optimization problem about simplified satellite module layout design.A heuristic algorithm based on tabu search is put forward for solving this problem.The algorithm begins from a random initial configuration and applies the gradient method with an adaptive step length to search for the minimum energy configuration.To jump out of the local minima and avoid the search doing repeated work,the algorithm adopts the strategy of tabu search.In the pr...     

Some algorithms solving the unilateral dirichlet problem with two constraints

We consider the Dirichlet problem with two obstacles in the theory of variational inequalities and a finite-dimensional discretization related with a matrix belonging to the class (P)∩(Z). We construct some algorithms which produce monotone sequences. These sequences converge to the solution of the discrete problem starting from lower or upper obstacle.

---

Sommario Consideriamo il problema di Dirichlet dei due ostacoli, ben conosciuto nella teoria delle disequazioni variazionali ed una sua discretizzazione relative ad una matrice della classe (P)∩(Z). In questo conteto costruiamo alcuni algoritmi atti a produrre successioni approssimanti, monotone non decrescenti e non crescenti, convergenti alla soluzione del problema discreto a partire rispettivamente dall’ostacolo inferiore e superiore.

---

---

This paper has been partially supported by GNAFA-CNR.     

Exact and heuristic algorithms for the vehicle routing problem with multiple interdependent time windows

In this paper a model and several solution procedures for a novel type of vehicle routing problems where time windows for the pickup of perishable goods depend on the dispatching policy used in the solution process are presented. This problem is referred to as Vehicle Routing Problem with multiple interdependent time windows (VRPmiTW) and is motivated by a project carried out with the Austrian Red Cross blood program to assist their logistics department. Several variants of a heuristic constructive procedure as well as a branch-and-bound based algorithm for this problem were developed and implemented. Besides finding the expected reduction in costs when compared with the current procedures of the Austrian Red Cross, the results show that the heuristic algorithms find solutions reasonably close to the optimum in fractions of a second. Another important finding is that increasing the number of pickups at selected customers beyond the theoretical minimum number of pickups yields significantly greater potential for cost reductions.     

A new heuristic branching scheme for the crew pairing problem with base constraints

Airline crew scheduling is typically performed in two steps : crew pairing followed by crew assignment. The crew pairing problem (CPP) finds a set of pairings (sequences of flights separated by connections or rests starting and ending at the same crew base) that covers a set of flights at minimum cost. The crew assignment problem consists of assigning the crew members to these pairings to create their individual schedules. The main downside of this sequential approach is that the pairings generated in the first step are not all suitable for the crew assignment step, yielding poor-quality solutions. This paper studies an extension of the CPP that includes additional constraints limiting the total worked time at each crew base. This problem, called the CPP with base constraints (CPPBC), is designed to improve the coupling of the two scheduling steps. To solve the CPPBC, we develop four branch-and-price heuristics: three of them rely on known heuristic branching schemes, the other introduces a new branching method, called retrospective branching. This branching scheme is designed to detect and revise poor branching decisions made earlier in the search tree, without backtracking. We tested and compared these four heuristics on real-world datasets. Our results show that the algorithm with retrospective branching yields, most of the times, better-quality solutions than the other tested methods.