Dispersion for the point-feature cartographic label placement problem

The point-feature cartographic label placement problem (PFCLP) is a NP-Hard problem arising in design of maps and other graphic objects. For the sake of a better map legibility it is important to avoid overlaps in the process of labeling. This paper examines the PFCLP in the legibility context and proposes a dispersion approach for the problem. It is considered that when all points must to be labeled and overlaps are inevitable, the map can be more readable if overlapping labels are placed more distant from each other. The PFCLP is modeled as a dispersion problem on two mathematical formulations based on binary integer linear programming. Computational tests have provided good results on several generated instances.     

Lagrangean relaxation with clusters and column generation for the manufacturer's pallet loading problem

We consider in this paper a new lagrangean relaxation with clusters for the Manufacturer's Pallet Loading Problem (MPLP). The relaxation is based on the MPLP formulated as a Maximum Independent Set Problem (MISP) and represented in a conflict graph that can be partitioned in clusters. The edges inter clusters are relaxed in a lagrangean fashion. Computational tests attain the optimality for some instances considered difficult for a lagrangean relaxation. Our results show that this relaxation can be a successful approach for hard combinatorial problems modeled in conflict graphs. Moreover, we propose a column generation approach for the MPLP derived from the idea behind the lagrangean relaxation proposed.     

A new mathematical model and a Lagrangean decomposition for the point-feature cartographic label placement problem

This paper proposes a 0-1 integer linear programming model for the point-feature cartographic label placement problem based on labeling of the largest number of free labels. In addition, one non-trivial valid inequality is presented to strengthen this proposed model. Even with the strengthened model, a commercial solver was not able to solve a representative sample of known instances presented in the literature. Thus, we also present a Lagrangean decomposition technique based on graph partitioning. Our added approaches established optimal solutions for practically all the used instances and the results significantly improved the ones presented in recent studies concerning the problem.     

Lagrangean relaxation heuristics for the p-cable-trench problem

We address the p-cable-trench problem. In this problem, p facilities are located, a trench network is dug and cables are laid in the trenches, so that every customer - or demand - in the region is connected to a facility through a cable. The digging cost of the trenches, as well as the sum of the cable lengths between the customers and their assigned facilities, are minimized. We formulate an integer programming model of the problem using multicommodity flows that allows finding the solution for instances of up to 200 nodes. We also propose two Lagrangean Relaxation-based heuristics to solve larger instances of the problem. Computational experience is provided for instances of up to 300 nodes.     

Heuristics for cartographic label placement problems

The cartographic label placement problem is an important task in automated cartography and Geographical Information Systems. Positioning the texts requires that overlap among texts should be avoided, that cartographic conventions and preference should be obeyed. This paper examines the point-feature cartographic label placement problem (PFCLP) as an optimization problem. We formulate the PFCLP considering the minimization of existing overlaps and labeling of all points on a map. This objective improves legibility when all points must be placed even if overlaps are inevitable. A new mathematical formulation of binary integer linear programming that allows labeling of all points is presented, followed by some Lagrangean relaxation heuristics. The computational tests considered instances proposed in the literature up to 1000 points, and the relaxations provided good lower and upper bounds.     

A Lagrangean relaxation approach for the mixed-model flow line sequencing problem

In this study, a mixed-model flow line sequencing problem is considered. A mixed-model flow line is a special case of production line where products are transported on a conveyor belt, and different models of the same product are intermixed on the same line. We have focused on product-fixed, rate-synchronous lines with variable launching. Our objective function is minimizing makespan. A heuristic algorithm based on Lagrangean relaxation is developed for the problem, and tested in terms of solution quality and computational efficiency.     

A greedy randomized adaptive search procedure for the point-feature cartographic label placement

The point-feature cartographic label placement problem (PFCLP) is an NP-hard problem, which appears during the production of maps. The labels must be placed in predefined places avoiding overlaps and considering cartographic preferences. Owing to its high complexity, several heuristics have been presented searching for approximated solutions. This paper proposes a greedy randomized adaptive search procedure (GRASP) for the PFCLP that is based on its associated conflict graph. The computational results show that this metaheuristic is a good strategy for PFCLP, generating better solutions than all those reported in the literature in reasonable computational times.     

Lagrangean decompositions for the unconstrained binary quadratic programming problem

The unconstrained binary quadratic programming problem (QP) is a classical non‐linear problem of optimizing a quadratic objective by a suitable choice of binary decision variables. This paper proposes new Lagrangean decompositions to find bounds for QP. The methods presented treat a mixed binary linear version (LQP) of QP with constraints represented by a graph. This graph is partitioned into clusters of vertices forming a dual problem that is solved by a subgradient algorithm. The subproblems formed by the generated subgraphs are solved by CPLEX. Computational experiments consider a data set formed by several difficult instances with different features. The results show the efficiency of the proposed methods over traditional Lagrangean relaxations and other methods found in the literature.     

Automatic structural identification and relaxation for integer programming

This research investigates the automatic identification of typical embedded structures in the Integer Programming (IP) models and automatic transformation of the problem to an adequate Lagrangian problem which can provide tight bounds within the acceptable run time. For this purpose, the structural distinctivenesses of variables, constants, blocks of terms, and constraint chunks are identified to specify the structure of the IP model. To assist the identification of the structural distinctiveness, the representation by the knowledge based IP model formulator, UNIK-IP, is adopted. To reason for the structural identification, the hybrid of bottom-up, top-down, and case-based approaches are proposed. A system UNIK-RELAX is developed to implement the approaches proposed in this research.     

A hybrid data mining heuristic to solve the point‐feature cartographic label placement problem

A clean map visualization requires the fewest possible overlaps and depends on how labels are attached to point features. In this paper, we address the cartographic label placement variant problem whose objective is to label a set of points maximizing the number of conflict‐free points. Thus, we propose a hybrid data mining heuristic to solve the point‐feature cartographic label placement problem based on a clustering search (CS) heuristic, a state‐of‐the‐art method for this problem. Although several works have investigated the combination of data mining and multistart metaheuristics, this is the first time data mining has been used to improve CS and simulated annealing based heuristics. Computational experiments showed that the proposed hybrid heuristic was able to reach better cost solutions than the original strategy, with the same time effort. The proposed heuristic also could find almost all known optimal solutions and improved most of the best results for the set of large instances reported so far in the literature.     

An efficient Lagrangean heuristic for rental vehicle scheduling

In this article we present a heuristic based on Lagrangean relaxation for scheduling rental vehicles. The scheduling problem can be formulated as a set of large assignment problems with linking constraints. We discuss the theory behind the heuristic, including the ability to obtain lower bounds. The heuristic is based on ideas first introduced by D. Wedelin.     

A hybrid Lagrangean heuristic with GRASP and path-relinking for set k-covering

The set multicovering or set k-covering problem is an extension of the classical set covering problem, in which each object is required to be covered at least k times. The problem finds applications in the design of communication networks and in computational biology. We describe a GRASP with path-relinking heuristic for the set k-covering problem, as well as the template of a family of Lagrangean heuristics. The hybrid GRASP Lagrangean heuristic employs the GRASP with path-relinking heuristic using modified costs to obtain approximate solutions for the original problem. Computational experiments carried out on 135 test instances show experimentally that the Lagrangean heuristics performed consistently better than GRASP as well as GRASP with path-relinking. By properly tuning the parameters of the GRASP Lagrangean heuristic, it is possible to obtain a good trade-off between solution quality and running times. Furthermore, the GRASP Lagrangean heuristic makes better use of the dual information provided by subgradient optimization and is able to discover better solutions and to escape from locally optimal solutions even after the stabilization of the lower bounds, when other Lagrangean strategies fail to find new improving solutions.     

模态试验传感器优化布置的松弛序列法

合理选择传感器的数目和位置是模态试验是否成功的关键步骤.将松弛思想融入传感器优化布置的序列优化方法,提出了模态试验传感器优化布置的松弛序列法.选取模态保证准则矩阵的最大非对角元素为目标函数,在积累序列法的基础上融入松弛的思想,使其求解的结果得到进一步优化.首先,积累序列法产生初始解集;然后,对解集的元素进行多次松弛操作,直至所有元素无法继续松弛.提出的松弛序列法被应用于某桥梁的模态试验传感器优化布置问题,传统的序列法作为对比算法.结果表明:松弛序列法优于传统的序列法.     

A heuristic for the label printing problem

Label printing finds many applications in industry. However, this task is still labor intensive in many printing factories. Since each template can only accommodate a fixed number of labels, an important task is to work out the compositions of templates by allocating suitable labels to each template in order to fulfill the order requirements effectively. The template design could be rather arbitrary, which usually ends up with a lot of excessive printed labels. Enhancing the template design will significantly improve the efficiency of the printing process, and, at the same time, reduce the waste of resources. This motivates the study of more automatic design methods. In this paper, the problem is first formulated as a nonlinear integer programming problem. The main variables in the formulation are the compositions and the printing frequencies of templates. For practical purpose, each type of label is confined to one template only which allows automated packing and handling. The structure of the problems is carefully analyzed and a new algorithm is proposed. Numerical results show that the proposed method is a simple but effective way of generating good template designs.     

可重入混合流水车间调度的拉格朗日松弛算法

为了有效提升多重入车间的生产效率,考虑了实际生产中检查和修复过程对于逐层制造的可重入生产系统的重要性,提出了基于拉格朗日松弛算法的可重入混合流水车间的调度方法.首先进行了问题域的描述,并在此基础上以最小化加权完成时间为调度目标,建立数学规划模型.针对该调度问题提出了基于松弛机器能力约束的拉格朗日松弛算法,使松弛问题分解成工件级子问题,并使用动态规划方法建立递归公式,求解工件级子问题.随后,使用次梯度算法求解拉格朗日对偶问题.最后,对各种不同问题规模进行了仿真实验,结果表明,所提出的调度算法能够在合理的时间内获得满意的近优解.     

Lagrangian relaxation with cut generation for hybrid flowshop scheduling problems to minimize the total weighted tardiness

In this paper, we address a new Lagrangian relaxation (LR) method for solving the hybrid flowshop scheduling problem to minimize the total weighted tardiness. For the conventional LR, the problem relaxing machine capacity constraints can be decomposed into individual job-level subproblems which can be solved by dynamic programming. The Lagrangian dual problem is solved by the subgradient method. In this paper, a Lagrangian relaxation with cut generation is proposed to improve the Lagrangian bounds for the conventional LR. The lower bound is strengthened by imposing additional constraints for the relaxed problem. The state space reductions for dynamic programming for subproblems are also incorporated. Computational results demonstrate that the proposed method outperforms the conventional LR method without significantly increasing the total computing time.     

Lagrangean-based solution approaches for the generalized problem of locating capacitated warehouses

The traditional capacitated warehouse location problem consists of determining the number and the location of capacitated warehouses on a predefined set of potential sites such that the demands of a set of customers are met. A very common assumption made in modeling this problem in almost all of the existing research is that the total capacity of all potential warehouses is sufficient to meet the total demand. Whereas this assumption facilitates to define a well‐structured problem from the mathematical modeling perspective, it is in fact restrictive, not realistic, and hence rarely held in practice. The modeling approach presented in this paper breaks away from the existing research in relaxing this very restrictive assumption. This paper therefore investigates the generalized problem of locating warehouses in a supply chain setting with multiple commodities with no restriction on the total capacity and the demand. A new integer programming formulation for this problem is presented, and an algorithm based on Lagrangean relaxation and decomposition is described for its solution. Three Lagrangean heuristics are proposed. Computational results indicate that reasonably good solutions can be obtained with the proposed algorithms, without having to use a general purpose optimizer.     

完备ARRs集的生成方法及传感器优化配置应用

广泛应用于故障诊断和传感器优化、分析、证实的解析冗余关系(Analytical redundancy relations,ARRs)缺乏系统、有效的方法来产生完备ARRs集,为此,提出了一种逐次消元法。该方法以系统元关系(Primary relations,PRs)为基础,通过若干次循环消元过程,生成了完备ARRs集,同时生成了对应的假定特征矩阵(Hypothetical signature matrix,HSM);基于HSM,把传感器优化配置问题映射为一个特殊的0-1整数规划模型,并用分支定界法求解该模型。应用表明,该方法能在不降低故障检测率、隔离率的前提下减少传感器数目,降低了测试代价,对故障诊断中的传感器配置问题有借鉴意义。