Two-Connected Networks with Rings of Bounded Cardinality

We study the problem of designing at minimum cost a two-connected network such that each edge belongs to a cycle using at most K edges. This problem is a particular case of the two-connected networks with bounded meshes problem studied by Fortz, Labbé and Maffioli (Operations Research, vol. 48, no. 6, pp. 866–877, 2000).In this paper, we compute a lower bound on the number of edges in a feasible solution, we show that the problem is strongly NP-complete for any fixed K, and we derive a new class of facet defining inequalities. Numerical results obtained with a branch-and-cut algorithm using these inequalities show their effectiveness for solving the problem.     

Designing Least-Cost Survivable Wireless Backhaul Networks

This paper presents a new heuristic algorithm for designing least-cost telecommunications networks to carry cell site traffic to wireless switches while meeting survivability, capacity, and technical compatibility constraints. This requires solving the following combinatorial optimization problems simultaneously: (1) Select a least-cost subset of locations (network nodes) as hubs where traffic is to be aggregated and switched, and choose the type of hub (high-capacity DS3 vs. lower-capacity DS1 hub) for each location; (2) Optimally assign traffic from other nodes to these hubs, so that the traffic entering the network at these nodes is routed to the assigned hubs while respecting capacity constraints on the links and routing-diversity constraints on the hubs to assure survivability; and (3) Optimally choose the types of links to be used in interconnecting the nodes and hubs based on the capacities and costs associated with each link type. Each of these optimization problems must be solved while accounting for its impacts on the other two. This paper introduces a short term Tabu Search (STTS) meta-heuristic, with embedded knapsack and network flow sub-problems, that has proved highly effective in designing such backhaul networks for carrying personal communications services (PCS) traffic. It solves problems that are challenging for conventional branch-and-bound solvers in minutes instead of hours and finds lower-cost solutions. Applied to real-world network design problems, the heuristic has successfully identified designs that save over 20% compared to the best previously known designs.     

A Mixed Integer Formulation for Multiple-Route Transit Network Design

We consider the design of multiple transit lines in a network and present a mixed integer formulation for this multiple-route transit network design problem (MRTNDP). With the introduction of node labels, the formulation can exploit the route structure and hence attains efficiency in obtaining a cost minimizing transit network design. This revised version was published online in July 2006 with corrections to the Cover Date.     

Neural Approach for Solving Several Types of Optimization Problems

Neural networks consist of highly interconnected and parallel nonlinear processing elements that are shown to be extremely effective in computation. This paper presents an architecture of recurrent neural net-works that can be used to solve several classes of optimization problems. More specifically, a modified Hopfield network is developed and its inter-nal parameters are computed explicitly using the valid-subspace technique. These parameters guarantee the convergence of the network to the equilibrium points, which represent a solution of the problem considered. The problems that can be treated by the proposed approach include combinatorial optimiza-tion problems, dynamic programming problems, and nonlinear optimization problems.Communicated by L. C. W. Dixon     

Solving Convex MINLP Optimization Problems Using a Sequential Cutting Plane Algorithm

In this article we look at a new algorithm for solving convex mixed integer nonlinear programming problems. The algorithm uses an integrated approach, where a branch and bound strategy is mixed with solving nonlinear programming problems at each node of the tree. The nonlinear programming problems, at each node, are not solved to optimality, rather one iteration step is taken at each node and then branching is applied. A Sequential Cutting Plane (SCP) algorithm is used for solving the nonlinear programming problems by solving a sequence of linear programming problems. The proposed algorithm generates explicit lower bounds for the nodes in the branch and bound tree, which is a significant improvement over previous algorithms based on QP techniques. Initial numerical results indicate that the described algorithm is a competitive alternative to other existing algorithms for these types of problems.     

Stochastic Survivable Network Design Problems

In this paper we introduce survivable network design problems under a two-stage stochastic model with fixed recourse and finitely many scenarios. We propose a new cut-based formulation based on orientation properties which is stronger than the undirected cut-based model. We use a two-stage branch&cut algorithm for solving the decomposed model to provable optimality. In order to accelerate the computations, we suggest a new cut strengthening technique for the decomposed L-shaped optimality cuts that is computationally fast and easy to implement.     

Reducing costs of backhaul networks for PCS networks using genetic algorithms

Designing cost-effective telecommunications networks often involves solving several challenging, interdependent combinatorial optimization problems simultaneously. For example, it may be necessary to select a least-cost subset of locations (network nodes) to serve as hubs where traffic is to be aggregated and switched; optimally assign other nodes to these hubs, meaning that the traffic entering the network at these nodes will be routed to the assigned hubs while respecting capacity constraints on the links; and optimally choose the types of links to be used in interconnecting the nodes and hubs based on the capacities and costs associated with each link type. Each of these three combinatorial optimization problems must be solved while taking into account its impacts on the other two. This paper introduces a genetic algorithm (GA) approach that has proved effective in designing networks for carrying personal communications services (PCS) traffic. The key innovation is to represent information about hub locations and their interconnections as two parts of a chromosome, so that solutions to both aspects of the problem evolve in parallel toward a globally optimal solution. This approach allows realistic problems that take 4–10 hours to solve via a more conventional branch-and-bound heuristic to be solved in 30–35 seconds. Applied to a real network design problem provided as a test case by Cox California PCS, the heuristics successfully identified a design 10% less expensive than the best previously known design. Cox California PCS has adopted the heuristic results and plans to incorporate network optimization in its future network designs and requests for proposals.     

一种改进遗传算法在最大独立子集问题中的应用

最大独立子集问题是组合优化问题中的一个重要问题,该问题是一个NP难题,其目标是在一个环图中找到一个最大的独立子集.提出了一种改进的遗传算法来解决这个问题,用一种基于条件的遗传算子来代替通常的基于概率的遗传算子.实验结果表明提出的算法是有效的.     

Solving Planning and Design Problems in the Process Industry Using Mixed Integer and Global Optimization

This contribution gives an overview on the state-of-the-art and recent advances in mixed integer optimization to solve planning and design problems in the process industry. In some case studies specific aspects are stressed and the typical difficulties of real world problems are addressed. Mixed integer linear optimization is widely used to solve supply chain planning problems. Some of the complicating features such as origin tracing and shelf life constraints are discussed in more detail. If properly done the planning models can also be used to do product and customer portfolio analysis. We also stress the importance of multi-criteria optimization and correct modeling for optimization under uncertainty. Stochastic programming for continuous LP problems is now part of most optimization packages, and there is encouraging progress in the field of stochastic MILP and robust MILP. Process and network design problems often lead to nonconvex mixed integer nonlinear programming models. If the time to compute the solution is not bounded, there are already a commercial solvers available which can compute the global optima of such problems within hours. If time is more restricted, then tailored solution techniques are required.     

NSGA-II算法在农业水保措施配置优化中的应用

农业水保措施的配置要考虑其生态效益和经济效益.不同水保措施组合方案有其相应的生态和经济效益,如何配置使综合效益最佳是一个最优化问题.分析了农业水保措施配置最优化需要考虑的两个目标,并将其公式化,建立了水保措施配置优化模型,并应用NSGA-II多目标遗传算法求解该模型.最后,以甘肃天水市罗玉沟流域的水保措施配置为例,进行了初步应用.结果表明,采用NSGA-II算法在水保措施配置优化模型求解时,计算效率较高,优化结果稳定,具有一定的应用价值.     

带组约束可靠性网络最优化问题的精确算法

本文提出了一种求解带组约束串-并网络系统最优冗余问题的精确算法.该算法利用拉格朗日松驰和Dantzig-Wolfe分解法得到问题的上界,并结合动态规划求解子问题.算法采用一种有效的切割和剖分方法,以逐步缩小对偶间隙和保证收敛性.数值结果表明该算法对于求解带组约束可靠性最优化问题是很有效的.     

B&B Frameworks for the Capacity Expansion of High Speed Telecommunication Networks Under Uncertainty

The purpose of this paper is to investigate branch and bound strategies and the comparison of branch and cut with pure branch and bound approaches on high speed telecommunication network design under uncertainty. We model the problem as a two-stage stochastic program with discrete first-stage (investment) variables. Two formulations of the problem are used. The first one with general integer investment variables and the second one, a variant of the first model, with 0-1 investment variables. We present computational results for three solution approaches: the integer L-shaped (Benders) decomposition, a branch and bound framework and a disjunctive cutting plane method. This work was supported by France Telecom.     

基于遗传算法的割缝衬管防砂多目标优化

割缝衬管防砂是油田重要的防砂方式之一,过去的研究往往专注于一个目标来设计割缝衬管参数,从而在参数设计上不能使多个参数在整体上达到最优.基于遗传算法中的gamultiobj多目标优化算法,以衬管使用寿命、地层流动阻力、产能和衬管强度为目标,建立了割缝衬管防砂优化设计模型,得出了高产能,长使用寿命,低流动阻力的割缝参数防砂的最优组合.结果表明,制定多目标适应性分析,建立评价模型,在给定的取值范围内得到的工艺参数,该技术有助于优选和优化调整防砂方法,提高防砂成功率,增强油田寿命和降低开采成本.     

Design of Civil Engineering Frame Structures Using a Monomial/Newton Hybrid Method

This paper presents an application of a monomial approximation method for solving systems of nonlinear equations to the design of civil engineering frame structures. This is accomplished by solving a set of equations representing the state known as fully-stressed design, where each member of the structure is stressed to the maximum safe allowable level under at least one of the loading conditions acting on it. The monomial approximation method is based on the process of condensation, which has its origin in geometric programming theory. A monomial/Newton hybrid method is presented which permits some of the design variables to be free in sign, while others are strictly positive. This hybrid method is well suited to the structural design application since some variables are naturally positive and others are naturally free. The proposed method is compared to the most commonly used fully-stressed design method in practice. The hybrid method is shown to find solutions that the conventional method cannot find, while doing so with less computational effort. The impact of this approach on the activity of structural design is discussed.     

Enhanced formulations and branch-and-cut for the two level network design problem with transition facilities

We consider a new combinatorial optimization problem that combines network design and facility location aspects. Given a graph with two types of customers and two technologies that can be installed on the edges, the objective is to find a minimum cost subtree connecting all customers while the primary customers are served by a primary subtree that is embedded into the secondary subtree. In addition, besides fixed link installation costs, facility opening costs, associated to each node where primary and secondary subtree connect, have to be paid. The problem is called the Two Level Network Design Problem with Transition Facilities (TLNDF).     

“穿越沙漠”赛题评述

对2020年"高教社杯"全国大学生数学建模竞赛"穿越沙漠"一题作简要评述,介绍赛题的数学基础和求解思路,探讨答卷所用的方法和存在的问题.     

Extensive Testing of a Hybrid Genetic Algorithm for Solving Quadratic Assignment Problems

A robust search algorithm should ideally exhibit reasonable performance on a diverse and varied set of problems. In an earlier paper Lim et al. (Computational Optimization and Applications, vol. 15, no. 3, 2000), we outlined a class of hybrid genetic algorithms based on the k-gene exchange local search for solving the quadratic assignment problem (QAP). We follow up on our development of the algorithms by reporting in this paper the results of comprehensive testing of the hybrid genetic algorithms (GA) in solving QAP. Over a hundred instances of QAP benchmarks were tested using a standard set of parameters setting and the results are presented along with the results obtained using simple GA for comparisons. Results of our testing on all the benchmarks show that the hybrid GA can obtain good quality solutions of within 2.5% above the best-known solution for 98% of the instances of QAP benchmarks tested. The computation time is also reasonable. For all the instances tested, all except for one require computation time not exceeding one hour. The results will serve as a useful baseline for performance comparison against other algorithms using the QAP benchmarks as a basis for testing.     

A Branch-and-Bound Algorithm to Solve a Multi-level Network Optimization Problem

Multi-level network optimization problems arise in many contexts such as telecommunication, transportation, and electric power systems. A model for multi-level network design is formulated as a mixed-integer program. The approach is innovative because it integrates in the same model aspects of discrete facility location, topological network design, and dimensioning. We propose a branch-and-bound algorithm based on Lagrangian relaxation to solve the model. Computational results for randomly generated problems are presented showing the quality of our approach. We also present and discuss a real world problem of designing a two-level local access urban telecommunication network and solving it with the proposed methodology.     

Development of a new approach for deterministic supply chain network design

This paper proposes a mixed integer linear programming model and solution algorithm for solving supply chain network design problems in deterministic, multi-commodity, single-period contexts. The strategic level of supply chain planning and tactical level planning of supply chain are aggregated to propose an integrated model. The model integrates location and capacity choices for suppliers, plants and warehouses selection, product range assignment and production flows. The open-or-close decisions for the facilities are binary decision variables and the production and transportation flow decisions are continuous decision variables. Consequently, this problem is a binary mixed integer linear programming problem. In this paper, a modified version of Benders’ decomposition is proposed to solve the model. The most difficulty associated with the Benders’ decomposition is the solution of master problem, as in many real-life problems the model will be NP-hard and very time consuming. In the proposed procedure, the master problem will be developed using the surrogate constraints. We show that the main constraints of the master problem can be replaced by the strongest surrogate constraint. The generated problem with the strongest surrogate constraint is a valid relaxation of the main problem. Furthermore, a near-optimal initial solution is generated for a reduction in the number of iterations.