XGRouter: high-quality global router in X-architecture with particle swarm optimization

This paper presents a high-quality very large scale integration (VLSI) global router in X-architecture, called XGRouter, that heavily relies on integer linear programming (ILP) techniques, partition strategy and particle swarm optimization (PSO). A new ILP formulation, which can achieve more uniform routing solution than other formulations and can be effectively solved by the proposed PSO is proposed. To effectively use the new ILP formulation, a partition strategy that decomposes a large-sized problem into some small-sized sub-problems is adopted and the routing region is extended progressively from the most congested region. In the post-processing stage of XGRouter, maze routing based on new routing edge cost is designed to further optimize the total wire length and mantain the congestion uniformity. To our best knowledge, XGRouter is the first work to use a concurrent algorithm to solve the global routing problem in X-architecture. Experimental results show that XGRouter can produce solutions of higher quality than other global routers. And, like several state-of-the-art global routers, XGRouter has no overflow.     

Arc-flow model for the two-dimensional guillotine cutting stock problem

We describe an exact model for the two-dimensional cutting stock problem with two stages and the guillotine constraint. It is an integer linear programming (ILP) arc-flow model, formulated as a minimum flow problem, which is an extension of a model proposed by Valério de Carvalho for the one dimensional case. In this paper, we explore the behavior of this model when it is solved with a commercial software, explicitly considering all its variables and constraints. We also derive a new family of cutting planes and a new lower bound, and consider some variants of the original problem. The model was tested on a set of real instances from the wood industry, with very good results. Furthermore the lower bounds provided by the linear programming relaxation of the model compare favorably with the lower bounds provided by models based on assignment variables.     

A note on “event-based MILP models for resource-constrained project scheduling problems”

Recently, new mixed integer linear programming formulations for the resource-constrained project scheduling problem were proposed by Koné et al. [3]. Unfortunately, the presentation of the first new model (called start/end-based formulation SEE) was not correct. More precisely, a set of necessary constraints representing the relative positioning of start and end events of activities was unintentionally omitted in the paper although it was present in the integer program used for the computational experiments. After presenting a counterexample showing the incorrectness, we provide a disaggregated and an aggregated variant of the set of necessary constraints, the disaggregated formulation yielding in theory a better linear programming relaxation. We present computational results showing that although the linear programming relaxations of both formulations yield equivalently poor lower bounds, the disaggregated formulation shows in average a better performance for integer solving of a well-known set of 30-activity instances.     

Solving an integrated employee timetabling and job-shop scheduling problem via hybrid branch-and-bound

We propose exact hybrid methods based on integer linear programming (ILP) and constraint programming (CP) for an integrated employee timetabling and job-shop scheduling problem. Each method we investigate uses a CP formulation associated with an LP relaxation. Under a CP framework, the LP relaxation is integrated into a global constraint using in addition reduced cost-based filtering techniques. We propose two CP formulations of the problem yielding two different LP relaxations. The first formulation is based on a direct representation of the problem. The second formulation is based on a decomposition in intervals of the possible operation starting times. We show the theoretical interest of the decomposition-based representation compared to the direct representation through the analysis of dominant schedules. Computational experiments on a set of randomly generated instances confirm the superiority of the decomposition-based representation. In both cases, the hybrid methods outperform pure CP for employee cost minimization while it is not the case for makespan minimization. The experiments also investigate the interest of the proposed integrated method compared to a sequential approach and show its potential for multiobjective optimization.     

Task allocation and trajectory planning for multiple agents in the presence of obstacle and connectivity constraints with mixed‐integer linear programming

This article addresses the problem of maneuvering multiple agents that must visit a number of target sets, while enforcing connectivity constraints and avoiding obstacle as well as interagent collisions. The tool to cope with the problem is a formulation of model predictive control including binary decision variables. In this regard, two mixed‐integer linear programming formulations are presented, considering a trade‐off between optimality and scalability between them. Simulation results are also shown to illustrate the main features of the proposed approaches.     

An integer programming formulation for the project scheduling problem with irregular time-cost tradeoffs

Four integer programming formulations are studied for the irregular costs project scheduling problem with time/cost trade-offs (PSIC). Three formulations using standard assignment type variables are tested against a more novel integer programming formulation. Empirical tests show that in many instances the new formulation performs best and can solve problems with up to 90 activities in a reasonable amount of time. This is explained by a reduced number of binary variables, a tighter linear programming (LP) relaxation, and the sparsity and embedded network structure of the constraint matrix of the new formulation.     

A pure proactive scheduling algorithm for multiple earth observation satellites under uncertainties of clouds

Most earth observation satellites (EOSs) are equipped with optical sensors, which cannot see through clouds. Hence, observations are significantly affected and blocked by clouds. In this work, with the inspiration of the notion of a forbidden sequence, we propose a novel assignment formulation for EOS scheduling. Considering the uncertainties of clouds, we formulate the cloud coverage for observations as stochastic events, and extend the assignment formulation to a chance constraint programming (CCP) model. To solve the problem, we suggest a sample approximation (SA) method, which transforms the CCP model into an integer linear programming (ILP) model. Subsequently, a branch and cut (B&C) algorithm based on lazy constraint generation is developed to solve the ILP model. Finally, we conduct a lot of simulation experiments to verify the effectiveness and efficiency of our proposed formulation and algorithm.     

Solving diameter‐constrained minimum spanning tree problems by constraint programming

The diameter‐constrained minimum spanning tree problem consists in finding a minimum spanning tree of a given graph, subject to the constraint that the maximum number of edges between any two vertices in the tree is bounded from above by a given constant. This problem typically models network design applications where all vertices communicate with each other at a minimum cost, subject to a given quality requirement. We propose alternative formulations using constraint programming that circumvent weak lower bounds yielded by most mixed‐integer programming formulations. Computational results show that the proposed formulation, combined with an appropriate search procedure, solves larger instances and is faster than other approaches in the literature.     

Local search heuristics for the mobile facility location problem

In the mobile facility location problem (MFLP), one seeks to relocate (or move) a set of existing facilities and assign clients to these facilities so that the sum of facility movement costs and the client travel costs (each to its assigned facility) is minimized. This paper studies formulations and develops local search heuristics for the MFLP. First, we develop an integer programming (IP) formulation for the MFLP by observing that for a given set of facility destinations the problem may be decomposed into two polynomially solvable subproblems. This IP formulation is quite compact in terms of the number of nonzero coefficients in the constraint matrix and the number of integer variables; and allows for the solution of large-scale MFLP instances. Using the decomposition observation, we propose two local search neighborhoods for the MFLP. We report on extensive computational tests of the new IP formulation and local search heuristics on a large range of instances. These tests demonstrate that the proposed formulation and local search heuristics significantly outperform the existing formulation and a previously developed local search heuristic for the problem.     

The multi-weighted Steiner tree problem: A reformulation by intersection

We propose a new formulation for the multi-weighted Steiner tree (MWST) problem. This formulation is based on the fact that a previously proposed formulation for the problem is non-symmetric in the sense that the corresponding linear programming relaxation bounds depend on the node selected as a root of the tree. The new formulation (the reformulation by intersection) is obtained by intersecting the feasible sets of the models corresponding to each possible root selection for the underlying directed problem. Theoretical results will show that the linear programming relaxation of the new formulation dominates the linear programming relaxation of each of the rooted formulations and is comparable with the linear programming bounds of the best formulation known for the problem. A Lagrangean relaxation scheme derived from the new formulation is also proposed and tested, with quite favourable results, on instances with up to 500 nodes and 5000 edges.     

Solving the bi‐objective capacitated p‐median problem with multilevel capacities using compromise programming and VNS

A bi‐objective optimisation using a compromise programming (CP) approach is proposed for the capacitated p‐median problem (CPMP) in the presence of the fixed cost of opening facility and several possible capacities that can be used by potential facilities. As the sum of distances between customers and their facilities and the total fixed cost for opening facilities are important aspects, the model is proposed to deal with those conflicting objectives. We develop a mathematical model using integer linear programming (ILP) to determine the optimal location of open facilities with their optimal capacity. Two approaches are designed to deal with the bi‐objective CPMP, namely CP with an exact method and with a variable neighbourhood search (VNS) based matheuristic. New sets of generated instances are used to evaluate the performance of the proposed approaches. The computational experiments show that the proposed approaches produce interesting results.     

软件定义网络中基于网络切片和ILP模型的路由方案

针对软件定义网络(SDN)中数据层的路由优化问题,提出一种基于网络切片和 整数线性规划(ILP) 多约束优化的路由方案。首先,根据多租户业务的链路需求,基于Kruskal算法对数据层中的链路资源进行网络切片,尽可能形成相互隔离的租户子网络。然后,在考虑链路约束和租户业务的服务质量(QoS)约束下, 以最小化传输延迟为目标, 构建一个ILP整数线性规划(ILP)路由优化模型,并获得最佳的路由方案。仿真结果表明,所获得的路由方案具有较少的共享链路,有效降低了链路拥塞和传输延迟。     

Hybrid techniques based on solving reduced problem instances for a longest common subsequence problem

Finding the longest common subsequence of a given set of input strings is a relevant problem arising in various practical settings. One of these problems is the so-called longest arc-preserving common subsequence problem. This NP-hard combinatorial optimization problem was introduced for the comparison of arc-annotated ribonucleic acid (RNA) sequences. In this work we present an integer linear programming (ILP) formulation of the problem. As even in the context of rather small problem instances the application of a general purpose ILP solver is not viable due to the size of the model, we study alternative ways based on model reduction in order to take profit from this ILP model. First, we present a heuristic way for reducing the model, with the subsequent application of an ILP solver. Second, we propose the application of an iterative hybrid algorithm that makes use of an ILP solver for generating high quality solutions at each iteration. Experimental results concerning artificial and real problem instances show that the proposed techniques outperform an available technique from the literature.     

Hybrid greedy heuristics based on linear programming for the three‐dimensional single bin‐size bin packing problem

In this paper, we propose to solve the three‐dimensional single bin‐size bin packing problem (3D‐SBSBPP) using a simple strategy based on integer linear programming (ILP) heuristics, without using any improvement based on metaheuristics. We first propose an ILP that is converted into a series of three‐dimensional single knapsack problems (3D‐SKP). Then, the first tailored heuristic can be viewed as a hybrid approach in which both “selection” and “positioning” phases are combined. The first phase serves to select a subset of items where each of these items is susceptible to belonging to an active container. The positioning phase serves to pack a subset of items already preselected by the selection phase. Then, both phases cooperate till packing all items into their corresponding containers. The second heuristic can be viewed as an extended version of the first one. Indeed, before deciding whether the current container is closed or a new container is activated, “a local reoptimization phase” is considered. Finally, both proposed heuristics are evaluated on a set of random instances obtained by using the standard generator scheme of the literature. The provided results show that both proposed heuristics remain competitive when compared to the results obtained by one of the best methods of the literature.     

Exact procedures for solving the discrete ordered median problem

The discrete ordered median problem (DOMP) integrates classical discrete location problems, such as the N-median, N-center and Uncapacitated Facility Location problems. It was introduced by Nickel (In: Fleischmann B, Lasch R, Derigs U, Domschke W, Rieder U, editors. Operations Research Proceedings 2000, Berlin: Springer, 2001. p. 71–76), who formulated it as both a nonlinear and a linear integer program. We propose an alternative integer linear programming formulation for the DOMP, discuss relationships between both integer linear programming formulations, and show how properties of optimal solutions can be used to strengthen these formulations. Moreover, we present a specific branch and bound procedure to solve the DOMP more efficiently. We test the integer linear programming formulations and this branch and bound method computationally on randomly generated test problems.     

Lot-sizing on a single imperfect machine: ILP models and FPTAS extensions

A single-machine multi-product lot-sizing and sequencing problem is studied. In this problem, items of n different products are manufactured in lots. Demands for products as well as per item processing times are known. There are losses of productivity because of non perfect production. There is also a sequence dependent set-up time between lots of different products. Machine yields and product lead times are assumed to be known deterministic functions. The objective is to minimize the cost of the demand dissatisfaction provided that the total processing time does not exceed a given time limit. We propose two integer linear programming (ILP) models for the NP-hard “fraction defective” case of this problem and compare effectiveness of their ILOG CPLEX realizations with a dynamic programming algorithm in a computer experiment. We also show how an earlier developed fully polynomial time approximation scheme (FPTAS) and one of the ILP models can be extended for a more complex case.     

Models for a traveling purchaser problem with additional side-constraints

The traveling purchaser problem (TPP) is the problem of determining a tour of a purchaser that needs to buy several items in different shops such that the total amount of travel and purchase costs is minimized. Motivated by an application in machine scheduling, we study a variant of the problem with additional constraints, namely, a limit on the maximum number of markets to be visited, a limit on the number of items bought per market and where only one copy per item needs to be bought. We present an integer linear programming (ILP) model which is adequate for obtaining optimal integer solutions for instances with up to 100 markets. We also present and test several variations of a Lagrangian relaxation combined with a subgradient optimization procedure. The relaxed problem can be solved by dynamic programming and can also be viewed as resulting from applying a state space relaxation technique to a dynamic programming formulation. The Lagrangian based method is combined with a heuristic that attempts to transform relaxed solutions into feasible solutions. Computational results for instances with up to 300 markets show that with the exception of a few cases, the reported differences between best upper bound and lower bound values on the optimal solutions are reasonably small.     

Lower bounds and exact algorithms for the quadratic minimum spanning tree problem

We address the quadratic minimum spanning tree problem (QMSTP), the problem of finding a spanning tree of a connected and undirected graph such that a quadratic cost function is minimized. We first propose an integer programming formulation based on the reformulation–linearization technique (RLT). We then use the idea of partitioning spanning trees into forests of a given fixed size and obtain a QMSTP reformulation that generalizes the RLT model. The reformulation is such that the larger the size of the forests, the stronger lower bounds provided. Thus, a hierarchy of formulations is obtained. At the lowest hierarchy level, one has precisely the RLT formulation, which is already stronger than previous formulations in the literature. The highest hierarchy level provides the convex hull of integer feasible solutions for the problem. The formulations introduced here are not compact, so the direct evaluation of their linear programming relaxation bounds is not practical. To overcome that, we introduce two lower bounding procedures based on Lagrangian relaxation. These procedures are embedded into two parallel branch-and-bound algorithms. As a result of our study, several instances in the literature were solved to optimality for the first time.     

高层次综合中基于整数线性规划模型的多目标功耗优化算法

考虑峰值周期功耗和峰值模块功耗的同时优化,并尽可能地降低电路的功耗时延乘积指标.利用参数化功能单元库中各个功能模块的具体物理信息,在多供电电压、多调度周期模式下,建立了整数线性规划模型及其相应的6组约束条件,并将高层次综合中的调度过程和功能单元的绑定过程统一起来进行了模型化.文中算法已经成功地应用到自行开发的高层次综合工具之中,算法中得到的数据结果可以直接用于下一步的布图规划.对测试用例的实验进一步说明:同时优化峰值周期功耗和峰值模块功耗可以取得更好的综合结果,并且改善功耗时延乘积项的值(平均降低了30%),提高电路的可靠性和稳定性.     

OPTIMIZATION OF SPARE CAPACITY IN WDM NETWORKS FOR REAL-TIME SERVICE RESTORATION

In the case of network malfunction a network with restoration capability requires spare capacity to be used. Optimization of the spare capacity in this case is to find the minimum amount of spare capacity for the network to survive from network component failures. In this paper, the optimization of the spare capacity problem is investigated for the wavelength division multiplexing (WDM) mesh networks without wavelength conversion. To minimize the spare capacity, we will optimize both the routing and the wavelength assignment. This combinatorial problem is usually called the routing and wavelength assignment (RWA) problem and it is well known to be NP-hard. We give an integer linear programming (ILP) formulation for the problem. Due to the excessive run-times of the ILP, we propose a hybrid genetic algorithm approach (GA) for the problem. For benchmarking purpose, simulated annealing (SA) and Tabu search (TS) are also applied to this problem. To validate the effectiveness of the proposed method, the approach is applied to the China network, which has a more complicated network topology. Simulation results are very favorable to the GA approach.