Stochastic user equilibrium model with a tradable credit scheme and application in maximizing network reserve capacity

The tradable credit scheme (TCS) outperforms congestion pricing in terms of social equity and revenue neutrality, apart from the same perfect performance on congestion mitigation. This article investigates the effectiveness and efficiency of TCS on enhancing transportation network capacity in a stochastic user equilibrium (SUE) modelling framework. First, the SUE and credit market equilibrium conditions are presented; then an equivalent general SUE model with TCS is established by virtue of two constructed functions, which can be further simplified under a specific probability distribution. To enhance the network capacity by utilizing TCS, a bi-level mathematical programming model is established for the optimal TCS design problem, with the upper level optimization objective maximizing network reserve capacity and lower level being the proposed SUE model. The heuristic sensitivity analysis-based algorithm is developed to solve the bi-level model. Three numerical examples are provided to illustrate the improvement effect of TCS on the network in different scenarios.     

Coordinated optimisation of platform-driven product line planning by bilevel programming

Product line planning (PLP) aims at an optimal combination of product feature offerings, suggesting itself to be a determinant decision for a company to satisfy diverse customer needs and gain competitive advantages. Fulfilment of planned product lines must make trade-offs between product variety and production costs. To balance the costs of product lines, manufacturers often adopt a product platform configuration (PPC) approach to redesign product and process platforms by adding new modules to the legacy platforms. The PPC is an effective means of providing product variety while controlling the manufacturing costs. The PLP and PPC problems have traditionally been investigated separately in the marketing research and engineering design fields. It is important to coordinate PLP and PPC decisions within a coherent optimisation framework. This paper proposes a bilevel mixed 0–1 nonlinear programming model to formulate coordinated optimisation for platform-driven product line planning. The upper level deals with the PLP problem by maximising the profit of an entire product line, whilst the lower level copes with the multiple product platforms optimisation for the optimal PPC in accordance with the upper level decisions of product line structure. To solve this bilevel programming model, a bilevel genetic algorithm is developed to find the optimal solution. A case study of coordinated optimisation between an automobile line and its product platforms is presented to demonstrate the feasibility and effectiveness of the proposed bilevel programming in comparison with a typical ‘all-in-one’ approach and a non-joint optimisation programming.     

Co-evolutionary algorithm: An efficient approach for bilevel programming problems

The bilevel programming problem involves two optimization problems, which is hierarchical, strongly NP-hard and very challenging for most existing optimization approaches. An efficient universal co-evolutionary algorithm is developed in this article to deal with various bilevel programming problems. In the proposed algorithm, evolutionary algorithms are used to explore the leader's and the follower's decision-making spaces interactively. Unlike other existing approaches, in the suggested procedure the follower's problem is solved in two phases. First, an evolutionary algorithm is run for a few generations to obtain an approximation of lower level solutions. In the second phase, from all approximate solutions obtained above, only a small number of good points are selected and evolved again by a newly designed multi-criteria evolutionary algorithm. The technique refines some candidate solutions and can efficiently reduce the computational cost of obtaining feasible solutions. Proof-of-principle experiments demonstrate the efficiency of the proposed approach.     

On the convergence of stationary sequences in topology optimization

We consider structural topology optimization problems including unilateral constraints arising from non‐penetration conditions in contact mechanics. The resulting non‐convex non‐smooth problems are instances of mathematical programs with equilibrium constraints (MPEC), or bi‐level programs. Applying nested (implicit programming) algorithms to this class of problems is problematic owing to the singularity of the feasible set. We propose a perturbation strategy combining the relaxation of the equilibrium constraint with the restriction of the design domain to its regular part only. This strategy allows us to attack the problem numerically using standard non‐linear programming algorithms. We rigorously study the optimality conditions for the original singular problem as well as the convergence of stationary points and globally optimal solutions to approximating problems towards respective stationary points and globally optimal solutions to the original problem. A limited numerical benchmarking of the algorithm is performed. Copyright © 2005 John Wiley & Sons, Ltd.     

Improved network based algorithms for the assembly line balancing problem

In this paper, we present two network based algorithms for solving Type 1 assembly line balancing problems. These algorithms are based on the generation of the network of feasible subsets; the shortest path through this network corresponds to the minimum cost solution. While the methods presented here may require the generation of all feasible subsets, they use upper and lower bounds and dominance to eliminate many of these subsets. The first method (which we call the Frontscan algorithm) evaluates nodes in a manner similar to a procedure originally suggested by Mansoor (1967); the second procedure (which we call the Backscan algorithm) evaluates nodes by proceeding backwards through the network. Both procedures are quite versatile and are easily adapted to the line balancing problem with stochastic task times, duplicate parallel work stations, zoning restrictions, etc. Computational tests indicate that these algorithms are more efficient than previous network based methods (including dynamic programming methods) and favourably compare with branch and bound methods. A numerical example illustrates the algorithms.     

An interior point technique for solving bilevel programming problems

This paper deals with bilevel programs with strictly convex lower level problems. We present the theoretical basis of a kind of necessary and sufficient optimality conditions that involve a single-level mathematical program satisfying the linear independence constraint qualification. These conditions are obtained by replacing the inner problem by their optimality conditions and relaxing their inequality constraints. An algorithm for the bilevel program, based on a well known technique for classical smooth constrained optimization, is also studied. The algorithm obtains a solution of this problem with an effort similar to that required by a classical well-behaved nonlinear constrained optimization problem. Several illustrative problems which include linear, quadratic and general nonlinear functions and constraints are solved, and very good results are obtained for all cases.     

Automatic sizing functions for unstructured surface mesh generation

Accurate sizing functions are crucial for efficient generation of high‐quality meshes, but to define the sizing function is often the bottleneck in complicated mesh generation tasks because of the tedious user interaction involved. We present a novel algorithm to automatically create high‐quality sizing functions for surface mesh generation. First, the tessellation of a Computer Aided Design (CAD) model is taken as the background mesh, in which an initial sizing function is defined by considering geometrical factors and user‐specified parameters. Then, a convex nonlinear programming problem is formulated and solved efficiently to obtain a smoothed sizing function that corresponds to a mesh satisfying necessary gradient constraint conditions and containing a significantly reduced element number. Finally, this sizing function is applied in an advancing front mesher. With the aid of a walk‐through algorithm, an efficient sizing‐value query scheme is developed. Meshing experiments of some very complicated geometry models are presented to demonstrate that the proposed sizing‐function approach enables accurate and fully automatic surface mesh generation. Copyright © 2016 John Wiley & Sons, Ltd.     

An extension of the directed search domain algorithm to bilevel optimization

A method is developed for generating a well-distributed Pareto set for the upper level in bilevel multiobjective optimization. The approach is based on the Directed Search Domain (DSD) algorithm, which is a classical approach for generation of a quasi-evenly distributed Pareto set in multiobjective optimization. The approach contains a double-layer optimizer designed in a specific way under the framework of the DSD method. The double-layer optimizer is based on bilevel single-objective optimization and aims to find a unique optimal Pareto solution rather than generate the whole Pareto frontier on the lower level in order to improve the optimization efficiency. The proposed bilevel DSD approach is verified on several test cases, and a relevant comparison against another classical approach is made. It is shown that the approach can generate a quasi-evenly distributed Pareto set for the upper level with relatively low time consumption.     

Optimization‐based stability analysis of structures under unilateral constraints

This paper discusses an optimization‐based technique for determining the stability of a given equilibrium point of the unilaterally constrained structural system, which is subjected to the static load. We deal with the three problems in mechanics sharing the common mathematical properties: (i) structures containing no‐compression cables; (ii) frictionless contacts; and (iii) elastic–plastic trusses with non‐negative hardening. It is shown that the stability of a given equilibrium point of these structures can be determined by solving a maximization problem of a convex function over a convex set. On the basis of the difference of convex functions optimization, we propose an algorithm to solve the stability determination problem, at each iteration of which a second‐order cone programming problem is to be solved. The problems presented are solved for various structures to determine the stability of given equilibrium points. Copyright © 2008 John Wiley & Sons, Ltd.     

Bilevel programming applied to power system vulnerability analysis under multiple contingencies

This study examines the use of bilevel programming to analyse the vulnerability of power systems under multiple contingencies. One of the main purposes of this study is to explain the state of the art of the subject matter. A minimum vulnerability model and a maximum vulnerability model are presented and discussed. In both models, the upper-level optimisation determines a set of simultaneous outages in the transmission network whereas the lower-level optimisation models the reaction of the system operator against the outages identified in the upper level. The system operator reacts by minimising the system load shed through an optimal operation of the power system. Two solution approaches for the resulting mixedinteger non-linear bilevel programs are analysed and compared. Both methodologies are based on the equivalent transformation of the lower-level problem into a set of constraints, so that the original bilevel programs, respectively, become a single-level optimisation problem. The first approach is based on the application of Karush--Kuhn--Tucker optimality conditions whereas the second procedure relies on duality theory. This study shows that both approaches are essentially equivalent from a rigorous mathematical viewpoint; however, the second method is more suitable for off-the-shell branch-and-cut software as corroborated by numerical simulations.     

考虑顾客延误损失的配送中心选址双层规划问题研究

配送网络中存在潜在的延误风险。针对延误情景下配送中心选址问题,提出双层规划模型。上层是企业选址的0-1规划问题,下层是顾客对设施目标选择的0-1规划问题,并考虑配送距离、时间延误造成的损失等因素对顾客选择的影响。通过层次遗传算法,对具体案例进行分析。结果表明,选址成本与顾客损失效用之间的反比关系,有效选址可以缩短物资配送距离和配送时间,从而降低选址成本和减轻顾客损失。     

凸组合投影算法中的组合因子对算法效率的影响

在求解生产生活中各类实际问题的优化模型的算法研究中,投影梯度算法在解决凸约束最优化问题上一直被学者所重视．本文考虑凸组合投影算法求解凸约束最优化问题,在此凸组合投影算法中,由投影梯度法得到的点与上一步迭代点的凸组合得到新的迭代点．此算法不仅利用投影算法得到的点的信息而且也利用了前一步点的信息．进一步,通过数值实验分析凸组合算法的效率及凸组合因子对算法的影响．数值试验结果表明,这种凸组合算法总体比原来投影梯度法更稳定,而且这种凸组合算法在适当的凸组合因子下较投影梯度法收敛更快．     

A fast first-order optimization approach to elastoplastic analysis of skeletal structures

It is classical that, when the small deformation is assumed, the incremental analysis problem of an elastoplastic structure with a piecewise-linear yield condition and a linear strain hardening model can be formulated as a convex quadratic programming problem. Alternatively, this paper presents a different formulation, an unconstrained nonsmooth convex optimization problem, and proposes to solve it with an accelerated gradient-like method. Specifically, we adopt an accelerated proximal gradient method, that has been developed for a regularized least squares problem. Numerical experiments show that the presented algorithm is effective for large-scale elastoplastic analysis. Also, a simple warm-start strategy can speed up the algorithm when the path-dependent incremental analysis is carried out.     

Multi-product continuous plant scheduling: combination of decomposition,genetic algorithm,and constructive heuristic

We propose a polylithic method for medium-term scheduling of a large-scale industrial plant operating in a continuous mode. The method combines a decomposition approach, a genetic algorithm (GA) and a constructive MILP-based heuristic. In the decomposition, decisions are made at two levels, using the rolling horizon approach. At the upper level, a reduced set of products and the time period is chosen to be considered in the lower level. At the lower level, a short-term scheduling MILP-model with event-based representation is used. A heuristic solution to the lower level problem is found using a constructive Moving Window heuristic guided by a genetic algorithm. The GA is applied for finding efficient utilisation of critical units in the lower level problem. For solving the one unit scheduling problem, a parallel dynamic programming algorithm is proposed. Implementation of the dynamic programming algorithm for a graphics processing unit (GPU) is incorporated in the GA for improving its performance. The experimental study of the proposed method on a real case of a large-scale plant shows a significant improvement of the solution quality and the solving time comparing to the pure decomposition algorithm proposed in the earlier study, and confirmed suitability of the proposed approach for the real-life production scheduling. In particular, the reduction of the number of changeovers and their duration in the obtained solution as well as the CPU time of solving the problem was about 60% using the new approach.     

基于贪心遗传的地下物流节点选择规划研究

以国内某地区物流概况为研究背景,结合国内外地下物流系统研究成果,将集合覆盖的思想引入地下物流网络节点选址规划,建立以物流节点数量最少及物流节点转运率最低为优化目标的双层多目标规划模型,并结合贪心算法和遗传算法进行优化求解。研究表明：通过将集合覆盖的思想对城市地下物流系统节点规划进行初步探讨是可行有效的;基于贪心遗传算法进行优化求解,使得该地区地下物流网络节点选择达到全局最优,有效控制了物流节点的数量及节点转运率的大小;地下物流网络节点表现出明显的区域集中性,即服务节点均集中在物流需求点附近,且二级节点服务区域总是邻近某个一级节点。     

Variations and extension of the convex–concave procedure

We investigate the convex–concave procedure, a local heuristic that utilizes the tools of convex optimization to find local optima of difference of convex (DC) programming problems. The class of DC problems includes many difficult problems such as the traveling salesman problem. We extend the standard procedure in two major ways and describe several variations. First, we allow for the algorithm to be initialized without a feasible point. Second, we generalize the algorithm to include vector inequalities. We then present several examples to demonstrate these algorithms.     

Resource Allocation for Throughput Maximization in Cognitive Radio Network with NOMA

Spectrum resources are the precious and limited natural resources. In order to improve the utilization of spectrum resources and maximize the network throughput, this paper studies the resource allocation of the downlink cognitive radio network with non-orthogonal multiple access (CRN-NOMA). NOMA, as the key technology of the fifth-generation communication (5G), can effectively increase the capacity of 5G networks. The optimization problem proposed in this paper aims to maximize the number of secondary users (SUs) accessing the system and the total throughput in the CRN-NOMA. Under the constraints of total power, minimum rate, interference and SINR, CRN-NOMA throughput is maximized by allocating optimal transmission power. First, for the situation of multiple sub-users, an adaptive optimization method is proposed to reduce the complexity of the optimization solution. Secondly, for the optimization problem of nonlinear programming, a maximization throughput optimization algorithm based on Chebyshev and convex (MTCC) for CRN-NOMA is proposed, which converts multi-objective optimization problem into single-objective optimization problem to solve. At the same time, the convergence and time complexity of the algorithm are verified. Theoretical analysis and simulation results show that the algorithm can effectively improve the system throughput. In terms of interference and throughput, the performance of the sub-optimal solution is better than that of orthogonal-frequency-division-multiple-access (OFDMA). This paper provides important insights for the research and application of NOMA in future communications.     

Distributed algorithm for optimal sequence and power allocation in uplink code division multiple access systems

An alternative approach is presented for centralised algorithms that design optimal sequences and powers under quality of service constraints in the uplink of a code division multiple access systems. The authors propose a distributed algorithm, where each user designs its optimal codeword in such a way to transmit minimum power, based on certain feedback information sent from the base station. The authors define the user cost function, which is the user power written as a convex function of user codewords for a defined signal-to-interference plus noise ratio target. For the constrained optimisation problem, optimal codewords are designed based on feasible direction method and the optimal user powers are the minimum values of the user cost functions. For the optimal configuration, the matched filter employed at receiver will have the same performance as the minimum mean squared error filter. Even if the optimal user powers are unique, the optimal codewords do not correspond to a unique allocation, but rather to an entire class of codewords that can be related by unitary transformations. The algorithm works properly in the presence of multiple access interference with white or coloured additive noise and requires no ordering. The proposed algorithm is analysed and illustrated with numerical examples obtained from simulations.     

An interior‐point algorithm for elastoplasticity

The problem of small‐deformation, rate‐independent elastoplasticity is treated using convex programming theory and algorithms. A finite‐step variational formulation is first derived after which the relevant potential is discretized in space and subsequently viewed as the Lagrangian associated with a convex mathematical program. Next, an algorithm, based on the classical primal–dual interior point method, is developed. Several key modifications to the conventional implementation of this algorithm are made to fully exploit the nature of the common elastoplastic boundary value problem. The resulting method is compared to state‐of‐the‐art elastoplastic procedures for which both similarities and differences are found. Finally, a number of examples are solved, demonstrating the capabilities of the algorithm when applied to standard perfect plasticity, hardening multisurface plasticity, and problems involving softening. Copyright © 2006 John Wiley & Sons, Ltd.