A Primal-dual Steepest-edge Method for Even-flow Harvest Scheduling Problems

The even-flow harvest scheduling problem arises when the forestry agency has evolved into a rigid non-declining even-flow policy. In this paper, we investigate model formulation and solution strategies for the even-flow harvest scheduling problem. A multiple-objective linear programming problem is formulated for even-flow harvest scheduling problems with multiple-site classes and multiple periods. The aim of this problem is to simultaneously maximize a desired harvest-volume per hectare for each period of planning horizon and the total economic return. A block diagonal constraint structure, with many sets of network sub-problems and a set of coupling constraints, is identified in this linear programming problem. A longest path method for each of network sub-problems and a primal-dual steepest-edge algorithm for the entire problem are developed. The developed algorithm has been coded in Borland C++ and implemented on a personal computer. An illustrative example is used to display the detailed procedure for the developed algorithm and a real-world case study is used to show the trade-off between desired even-flow harvest volume policy and total economic return. Results show the potential benefits of this approach.     

Hose workload based exact algorithm for the optimal design of virtual private networks

The Virtual Private Networks (VPN) optimal bandwidth allocation problem with tree topology has been widely discussed in the literature. Most of the algorithms proposed by researchers to solve this problem use approximation schemes. In this paper, we propose an exact and efficient Branch-and-Cut algorithm for the problem in the context of a hose workload model. In particular, we consider the case when the ingress and egress traffic at VPN endpoints are asymmetric and the links of the network have unbounded capacities. The algorithm proposed here is based on a linear integer programming formulation for the problem introduced by Kumar et al. (2002) [2]. Using this and a deep investigation of the polyhedral structure of that formulation, our algorithm permits to solve large instances of the problem having up to 120 nodes and 10 terminals.     

An exact approach to the problem of extracting an embedded network matrix

We study the problem of detecting a maximum embedded network submatrix in a {−1,0,+1}-matrix. Our aim is to solve the problem to optimality. We introduce a 0–1 integer linear programming formulation for this problem based on its representation over a signed graph. A polyhedral study is presented and a branch-and-cut algorithm is described for finding an optimal solution to the problem. Some computational experiments are carried out over a set of instances available in the literature as well as over a set of random instances.     

A hub location problem with fully interconnected backbone and access networks

This paper considers the design of two-layered fully interconnected networks. A two-layered network consists of clusters of nodes, each defining an access network and a backbone network. We consider the integrated problem of determining the access networks and the backbone network simultaneously. A mathematical formulation is presented, but as the linear programming relaxation of the mathematical formulation is weak, a formulation based on the set partitioning model and column generation approach is also developed. The column generation subproblems are solved by solving a series of quadratic knapsack problems. We obtain superior bounds using the column generation approach than with the linear programming relaxation. The column generation method is therefore developed into an exact approach using the branch-and-price framework. With this approach we are able to solve problems consisting of up to 25 nodes in reasonable time. Given the difficulty of the problem, the results are encouraging.     

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.     

求解线性约束的二次规划神经网络学习新算法

提出了一种基于0.618法求解具有线性约束的二次规划问题的神经网络学习新算法。与已有的求解线性约束的二次规划问题的神经网络学习算法相比,该算法的适用范围更广,计算精度更高。其目的是为具有线性约束的二次规划问题的求解提供一种新方法。仿真实验验证了新算法的有效性。     

A Pareto-based hybrid multiobjective evolutionary approach for constrained multipath traffic engineering optimization in MPLS/GMPLS networks

This paper proposes a hybrid evolutionary algorithm for solving the constrained multipath traffic engineering problem in MPLS (Multi-Protocol Label Switching) network and its extended architecture GMPLS (Generalized MPLS). Multipath traffic engineering is gaining more importance in contemporary networks. It aims to satisfy the requirements of emerging network applications while optimizing the network performance and the utilization of the available resources within the network. A formulation of this problem as a multiobjective constrained mixed-integer program, which is known to be NP-hard, is first extended. Then, we develop a hybrid heuristic algorithm based on combining linear programming with a devised Pareto-based genetic algorithm for approximating the optimal Pareto curve. A numerical example is adopted from the literature to evaluate and compare the performance of six variations of the proposed heuristic. We study the statistical significance of the results using Kruskal–Wallis nonparametric test. We also compare the results of the heuristic approach with the lexicographic weighted Chebyshev method using a variety of performance metrics.     

A 99 line code for discretized Michell truss optimization written in Mathematica

The main purpose of the paper is to provide an easy-to-use code for topological optimization of the least weight trusses, written in the Mathematica programming language. The main idea of the presented approach consists in using a fixed ground structure and the linear programming formulation of the optimization problem. The solver is based on the fast interior point method. The strong effort is done to create the effective generator of the computational model utilizing the high regularity of the ground structure and the high sparsity of the geometric matrix. The efficiency and reliability of the algorithm is confirmed in several numerical tests. Due to a linear programming formulation of the optimization problem the method presented in the paper assures finding the global optimum, hence it may be considered as the useful tool for verification of results obtained in other ways. The appended complete Mathematica code of the program developed will be supplied by the Publisher on SpringerLink.     

Sequence of linear programming for transmission of fine-scalable coded content in bandwidth-limited environments

In this paper, we propose an optimal peer assignment algorithm on peer-to-peer networks. This algorithm is designed to maximize the quality of transmitting fine-scalable coded content by exploiting the embedding property of scalable coding. To be more realistic, we assume that the requesting peer has a delay constraint to display the content within a certain delay bound, and it also has limited incoming bandwidth. We first use a simple example to illustrate the peer assignment problem, and then formulate this problem as a linear programming problem, followed by a nonlinear programming problem. To efficiently solve the second nonlinear problem, we transform it into a sequence of linear programming problems. Finally, we apply our proposed algorithm to both image and video transmissions in bandwidth-limited environments. Extensive experiments have been carried out to evaluate the complexity and performance of our approach by comparing it with both nonlinear formulation and two heuristic schemes. The results have verified the superior performance of our proposed algorithm.     

A fast algorithm for the optimal design of high accuracy windows in signal processing

This paper presents a new optimal window design method with a general window design specification for the passband and stopband. The design problem is formulated as a semi-infinite linear programming problem. With suitable discretizations, an exchange algorithm is employed. The convergence of the proposed algorithm is established. In the formulation, since the stopband is minimized, the method can be employed for the design of very highly optimized windows.     

A new formulation and approach for the black and white traveling salesman problem

This paper proposes a new formulation and a column generation approach for the black and white traveling salesman problem. This problem is an extension of the traveling salesman problem in which the vertex set is divided into black vertices and white vertices. The number of white vertices visited and the length of the path between two consecutive black vertices are constrained. The objective of this problem is to find the shortest Hamiltonian cycle that covers all vertices satisfying the cardinality and the length constraints. We present a new formulation for the undirected version of this problem, which is amenable to the Dantzig–Wolfe decomposition. The decomposed problem which is defined on a multigraph becomes the traveling salesman problem with an extra constraint set in which the variable set is the feasible paths between pairs of black vertices. In this paper, a column generation algorithm is designed to solve the linear programming relaxation of this problem. The resulting pricing subproblem is an elementary shortest path problem with resource constraints, and we employ acceleration strategies to solve this subproblem effectively. The linear programming relaxation bound is strengthened by a cutting plane procedure, and then column generation is embedded within a branch-and-bound algorithm to compute optimal integer solutions. The proposed algorithm is used to solve randomly generated instances with up to 80 vertices.     

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.     

Gamma deployment problem in grids: hardness and new integer linear programming formulation

Vehicular networks are mobile networks designed for the domain of vehicles and pedestrians. These networks are an essential component of intelligent transportation systems and have the potential to ease traffic management, lower accident rates, and offer other solutions to smart cities. One of the most challenging aspects in the design of a vehicular network is the distribution of its infrastructure units, which are called roadside units (RSUs). In this work, we tackle the gamma deployment problem that consists of deploying the minimum number of RSUs in a vehicular network in accordance with a quality of service metric called gamma deployment. This metric defines a vehicle as covered if it connects to some RSUs at least once in a given time interval during its whole trip. Then, the metric parameterizes the minimum percentage of covered vehicles necessary to make a deployment acceptable or feasible. In this paper, we prove that the decision version of the gamma deployment problem in grids is NP‐complete. Moreover, we correct the multiflow integer linear programming formulation present in the literature and introduce a new formulation based on set covering that is at least as strong as the multiflow formulation. In experiments with a commercial solver, the set covering formulation widely outperforms the multiflow formulation with respect to running time and linear programming relaxation gap.     

Models for the two‐dimensional rectangular single large placement problem with guillotine cuts and constrained pattern

In this paper, we address the constrained two‐dimensional rectangular guillotine single large placement problem (2D_R_CG_SLOPP). This problem involves cutting a rectangular object to produce smaller rectangular items from orthogonal guillotine cuts. In addition, there is an upper limit on the number of copies that can be produced of each item type. To model this problem, we propose a new pseudopolynomial integer nonlinear programming (INLP) formulation and obtain an equivalent integer linear programming (ILP) formulation from it. Additionally, we developed a procedure to reduce the numbers of variables and constraints of the integer linear programming (ILP) formulation, without loss of optimality. From the ILP formulation, we derive two new pseudopolynomial models for particular cases of the 2D_R_CG_SLOPP, which consider only two‐staged or one‐group patterns. Finally, as a specific solution method for the 2D_R_CG_SLOPP, we apply Benders decomposition to the proposed ILP formulation and develop a branch‐and‐Benders‐cut algorithm. All proposed approaches are evaluated through computational experiments using benchmark instances and compared with other formulations available in the literature. The results show that the new formulations are appropriate in scenarios characterized by few item types that are large with respect to the object's dimensions.     

Flows in dynamic networks with aggregate arc capacities

Dynamic networks are characterized by transit times on edges. Dynamic flow problems consider transshipment problems in dynamic networks. We introduce a new version of dynamic flow problems, called bridge problem. The bridge problem has practical importance and raises interesting theoretical issues. We show that the bridge problem is NP-complete. Traditional static flow techniques for solving dynamic flow problems do not extend to the new problem. We give a linear programming formulation for the bridge problem which is based on the time-expanded network of the original dynamic network.     

基于原始对偶方法求解网络流量监测集算法

考虑网络节点的流守恒特性,网络流量的有效监测问题可抽象为求给定图G(V,E)的最小弱顶点覆盖集的问题和基于流划分的最小弱顶点覆盖集的问题,这是NP难的问题.首先分析了弱顶点覆盖集的约束关系,并给出了问题的整数规划形式.然后利用原始对偶方法构造了求解最小弱顶点覆盖集的近似算法,并分析了算法的比界为2.进一步分析了求解基于最大流划分的最小弱顶点覆盖集的近似算法.     

一种分布式系统中最优复制的策略分析

在网络中定位最优复制以最小化通讯代价。假定网络采用read-one-write-all策略来保证网络数据一致性,那么存在一个决定复制定位的最优化问题。提出了研究复制问题中读、写比率以确定最优化通讯代价。问题可转换成一个0- 1线性规划问题,并将此问题扩展为一个P中值问题,可以证明这个问题是NP-complete的问题,并提出了一种多项式时间内的此问题求解算法。     

基于异步时间段的原油混输调度连续时间建模研究

采用严格的数学规划方法对沿海炼厂的原油混输调度问题进行了建模和求解,提出了一个基于异步时间段的连续时间混合整数非线性规划(MINLP)数学模型。该模型具有整型变量少,求解快的优点。采用求解一系列MILP来近似求解非凸的MINLP,避免了原油混输MILP模型产生的浓度不一致问题。文中采用提出的新模型和算法对文献中的9个实例进行了计算,相同计算条件的4个实例比离散时间模型效率提高86％-1011％。     

Optimal Routing Designs in Self-healing Communications Networks

Self-healing communication networks that allow re-routing of demands through switching processes at designated nodes are studied. It is shown how network utilization, demand throughput and reliability of such networks can be studied simultaneously to achieve an optimal design for all three. This is done through a max–min–max multi-commodity network flow formulation of the routing problem in which it is ensured that maximum network throughput is achieved with minimum loss of demands that are blocked due to single switching node failures. It is shown that a node-path linear programming approximation to the multi-commodity network flow formulation solves the problem for medium and large network sizes in moderate computational times.     

Scheduling of thermal units with a nonlinear load flow network model

We describe a formulation of the thermal unit commitment problem that includes AC network constraints, which allows taking into account VAr production as a criterion for generator commitment for the first time. The formulation makes it possible to use the Lagrangian Relaxation technique as a solution algorithm even though the network constraints are not linear. Although the solution method is computationally intensive, the problem exhibits a separation structure and a price coordination schedule that suggest several ways of improving the performance. Preliminary test results are reported.