An interactive approach based on a discrete differential evolution algorithm for a class of integer bilevel programming problems

This paper presents an interactive approach based on a discrete differential evolution algorithm to solve a class of integer bilevel programming problems, in which integer decision variables are controlled by an upper-level decision maker and real-value or continuous decision variables are controlled by a lower-level decision maker. Using the Karush--Kuhn–Tucker optimality conditions in the lower-level programming, the original discrete bilevel formulation can be converted into a discrete single-level nonlinear programming problem with the complementarity constraints, and then the smoothing technique is applied to deal with the complementarity constraints. Finally, a discrete single-level nonlinear programming problem is obtained, and solved by an interactive approach. In each iteration, for each given upper-level discrete variable, a system of nonlinear equations including the lower-level variables and Lagrange multipliers is solved first, and then a discrete nonlinear programming problem only with inequality constraints is handled by using a discrete differential evolution algorithm. Simulation results show the effectiveness of the proposed approach.     

Local stability of trusses in the context of topology optimization Part II: A numerical approach

The paper considers the problem of optimal truss topology design with respect to stress, slenderness, and local buckling constraints. An exact problem formulation is used dealing with the inherent difficulty that the local buckling constraints are discontinuous functions in the bar areas due to the topology aspect. This exact problem formulation has been derived in Part I. In this paper, a numerical approach to this nonconvex and largescale problem is proposed. First, discontinuity of constraints is erased by providing an equivalent formulation in standard form of nonlinear programming. Then a linearization concept is proposed partly preserving the given problem structure. It is proved that the resulting sequential linear programming algorithm is a descent method generating truss designs feasible for the original problem. A numerical test on a nontrivial example shows that the exact treatment of the problem leads to different designs than the usual local buckling constraints neglecting the difficulties induced by the topology aspect.     

A new approach for the solution of singular optima in truss topology optimization with stress and local buckling constraints

The present paper investigates problems of truss topology optimization under local buckling constraints. A new approach for the solution of singular problems caused by stress and local buckling constraints is proposed. At first, a second order smooth-extended technique is used to make the disjoint feasible domains connect, then the so-called ε-relaxed method is applied to eliminate the singular optima from problem formulation. By means of this approach, the singular optimum of the original problem caused by stress and local buckling constraints can be searched approximately by employing the algorithms developed for sizing optimization problems with high accuracy. Therefore, the numerical problem resulting from stress and local buckling constraints can be solved in an elegant way. The applications of the proposed approach and its effectiveness are illustrated with several numerical examples. Received May 2, 2000     

Contact shape optimization: a bilevel programming approach

We consider the problem of shape optimization of nonlinear elastic solids in contact. The equilibrium of the solid is defined by a constrained minimization problem, where the body energy functional is the objective and the constraints impose the nonpenetration condition. Then the optimization problem can be formulated in terms of a bilevel mathematical program. We describe new optimality conditions for bilevel programming and construct an algorithm to solve these conditions based on Herskovits’ feasible direction interior point method. With this approach we simultaneously carry out shape optimization and nonlinear contact analysis. That is, the present method is a “one shot” technique. We describe some numerical examples solved in a very efficient way. Received July 27, 1999     

Integrating linear physical programming within collaborative optimization for multiobjective multidisciplinary design optimization

Multidisciplinary design optimization (MDO) is a concurrent engineering design tool for large-scale, complex systems design that can be affected through the optimal design of several smaller functional units or subsystems. Due to the multiobjective nature of most MDO problems, recent work has focused on formulating the MDO problem to resolve tradeoffs between multiple, conflicting objectives. In this paper, we describe the novel integration of linear physical programming within the collaborative optimization framework, which enables designers to formulate multiple system-level objectives in terms of physically meaningful parameters. The proposed formulation extends our previous multiobjective formulation of collaborative optimization, which uses goal programming at the system and subsystem levels to enable multiple objectives to be considered at both levels during optimization. The proposed framework is demonstrated using a racecar design example that consists of two subsystem level analyses — force and aerodynamics — and incorporates two system-level objectives: (1) minimize lap time and (2) maximize normalized weight distribution. The aerodynamics subsystem also seeks to minimize rearwheel downforce as a secondary objective. The racecar design example is presented in detail to provide a benchmark problem for other researchers. It is solved using the proposed formulation and compared against a traditional formulation without collaborative optimization or linear physical programming. The proposed framework capitalizes on the disciplinary organization encountered during large-scale systems design.     

A programming approach for nonsmooth structural optimization

A two-level programming algorithm for some nonsmooth structural optimization problems is presented. When an optimization problem has both stress and unilateral displacement constraints, we combine the structural optimization with unilateral analysis to formulate a two-level model. Quadratic programming (QP) is used in analysis level, which is solved with dual interior-point method, and linear programming (LP) is used in optimization level. Several examples with unilateral or bilateral constraints are provided to verify the proposed algorithm.     

A study on the use of heuristics to solve a bilevel programming problem

The bilevel programming problem is characterized as an optimization problem that has another optimization problem in its constraints. The leader in the upper level and the follower in the lower level are hierarchically related where the leader's decisions affect both the follower's payoff function and allowable actions, and vice versa. One difficulty that arises in solving bilevel problems is that unless a solution is optimal for the lower level problem, it cannot be feasible for the overall problem. This suggests that approximate methods could not be used for solving the lower level problem, as they do not guarantee that the optimal solution is actually found. However, from the practical point of view near‐optimal solutions are often acceptable, especially when the lower level problem is too costly to be exactly solved thus rendering the use of exact methods impractical. In this paper, we study the impact of using an approximate method in the lower level problem, discussing how near‐optimal solutions on the lower level can affect the upper level objective function values. This study considers a bilevel production‐distribution planning problem that is solved by two intelligent heuristics hierarchically related: ant colony optimization for solving the upper level problem, and differential evolution method to solve the lower level problem.     

Minimization of squared deviation of completion times about a common due date

We discuss a non-preemptive single-machine job sequencing problem where the objective is to minimize the sum of squared deviation of completion times of jobs from a common due date. There are three versions of the problem—tightly restricted, restricted and unrestricted. Separate dynamic programming formulations have already been suggested for each of these versions, but no unified approach is available. We have proposed a pseudo-polynomial DP solution and a polynomial heuristic for general instance. Computational results show that tightly restricted instances of up to 600 jobs can be solved in less than 6 s. General instances of up to 80 jobs take less than 2 s.Statement of scope and purposeIn this paper, we have considered an NP-complete single-machine scheduling problem arising in JIT environment, a field of great importance in manufacturing industry. The objective of the problem is to schedule a set of given jobs to minimize the sum of squared deviation of their completion times from a common due date. This paper presents a number of precedence rules, a polynomial heuristic and more importantly a unified pseudo-polynomial dynamic programming formulation. Empirical results show that the dynamic programming formulation performs better than the existing approaches.     

Optimal truss design including plastic collapse constraints

A new algorithm is presented for size optimization of truss structures with any kind of smooth objectives and constraints, together with constraints on the collapse loading obtained by limit analysis, for several loading conditions. The main difficulty of this problem is the fact that the collapse loading is a nonsmooth function of the design variables. In this paper we avoid nonsmooth optimization techniques based on the fact that limit analysis constraints are linear by parts. Our approach is based on a feasible directions interior point algorithm for nonlinear constrained optimization. Three illustrative examples are discussed. The numerical results show that the calculation effort when limit analysis constraints are included is only slightly increased with respect to classic constraints.     

A Link-Node Discrete-Time Dynamic Second Best Toll Pricing Model with a Relaxation Solution Algorithm

Dynamic congestion pricing has become an important research topic because of its practical implications. In this paper, we formulate dynamic second-best toll pricing (DSBTP) on general networks as a bilevel problem: the upper level is to minimize the total weighted system travel time and the lower level is to capture motorists’ route choice behavior. Different from most of existing DSBTP models, our formulation is in discrete-time, which has very distinct properties comparing with its continuous-time counterpart. Solution existence condition of the proposed model is established independent of the actual formulation of the underlying dynamic user equilibrium (DUE). To solve the bilevel DSBTP model, we adopt a relaxation scheme. For this purpose, we convert the bilevel formulation into a single level nonlinear programming problem by applying a link-node based nonlinear complementarity formulation for DUE. The single level problem is solved iteratively by first relaxing the strick complementarity by a relaxation parameter, which is then progressively reduced. Numerical results are also provided in this paper to illustrate the proposed model and algorithm. In particular, we show that by varying travel time weights on different links, DSBTP can help traffic management agencies better achieve certain system objectives. Examples are given on how changes of the weights impact the optimal tolls and associated objective function values.

Topology optimization of continuum structures with local and global stress constraints

Topology structural optimization problems have been usually stated in terms of a maximum stiffness (minimum compliance) approach. The objective of this type of approach is to distribute a given amount of material in a certain domain, so that the stiffness of the resulting structure is maximized (that is, the compliance, or energy of deformation, is minimized) for a given load case. Thus, the material mass is restricted to a predefined percentage of the maximum possible mass, while no stress or displacement constraints are taken into account. This paper presents a different strategy to deal with topology optimization: a minimum weight with stress constraints Finite Element formulation for the topology optimization of continuum structures. We propose two different approaches in order to take into account stress constraints in the optimization formulation. The local approach of the stress constraints imposes stress constraints at predefined points of the domain (i.e. at the central point of each element). On the contrary, the global approach only imposes one global constraint that gathers the effect of all the local constraints by means of a certain so-called aggregation function. Finally, some application examples are solved with both formulations in order to compare the obtained solutions.     

Topology optimization of trusses with stress and local constraints on nodal stability and member intersection

A truss topology optimization problem under stress constraints is formulated as a Mixed Integer Programming (MIP) problem with variables indicating the existence of nodes and members. The local constraints on nodal stability and intersection of members are considered, and a moderately large lower bound is given for the cross-sectional area of an existing member. A lower-bound objective value is found by neglecting the compatibility conditions, where linear programming problems are successively solved based on a branch-and-bound method. An upper-bound solution is obtained as a solution of a Nonlinear Programming (NLP) problem for the topology satisfying the local constraints. It is shown in the examples that upper- and lower-bound solutions with a small gap in the objective value can be found by the branch-and-bound method, and the computational cost can be reduced by using the local constraints.     

Truss topology optimization with discrete design variables—Guaranteed global optimality and benchmark examples

This paper considers the problem of optimal truss topology design subject to multiple loading conditions. We minimize a weighted average of the compliances subject to a volume constraint. Based on the ground structure approach, the cross-sectional areas are chosen as the design variables. While this problem is well-studied for continuous bar areas, we consider in this study the case of discrete areas. This problem is of major practical relevance if the truss must be built from pre-produced bars with given areas. As a special case, we consider the design problem for a single available bar area, i.e., a 0/1 problem. In contrast to the heuristic methods considered in many other approaches, our goal is to compute guaranteed globally optimal structures. This is done by a branch-and-bound method for which convergence can be proven. In this branch-and-bound framework, lower bounds of the optimal objective function values are calculated by treating a sequence of continuous but non-convex relaxations of the original mixed-integer problem. The main effect of using this approach lies in the fact that these relaxed problems can be equivalently reformulated as convex problems and, thus, can be solved to global optimality. In addition, these convex problems can be further relaxed to quadratic programs for which very efficient numerical solution procedures exist. By exploiting this special problem structure, much larger problem instances can be solved to global optimality compared to similar mixed-integer problems. The main intention of this paper is to provide optimal solutions for single and multiple load benchmark examples, which can be used for testing and validating other methods or heuristics for the treatment of this discrete topology design problem.     

Topology optimization of softening structures under displacement constraints as an MPEC

This paper presents a mathematical programming based technique for the minimum weight (volume) topology optimization of truss-like structures such that strain softening material properties, that can lead to severe physical instability, can be accommodated. In addition, satisfaction of such serviceability criteria as limited displacements at some specific points is ensured. The problem is formulated in terms of truss member cross-sectional areas. This leads to a challenging nonconvex and nonsmooth optimization problem, known as a mathematical program with equilibrium constraints (MPEC). A two-step optimization algorithm is proposed to overcome the problems typically associated with nondefiniteness of some key matrices and at the same time nondifferentiability of the mathematical system. Each step involves updating the ground structure and solving the MPEC using a penalized nonlinear programming (NLP) approach. Some numerical examples are provided to illustrate application, robustness and efficiency of the proposed scheme. The safety and integrity of the designed topologically optimal structures are validated using appropriate stepwise holonomic elastoplastic analyses.     

Block aggregation of stress constraints in topology optimization of structures

Structural topology optimization problems have been traditionally stated and solved by means of maximum stiffness formulations. On the other hand, some effort has been devoted to stating and solving this kind of problems by means of minimum weight formulations with stress (and/or displacement) constraints. It seems clear that the latter approach is closer to the engineering point of view, but it also leads to more complicated optimization problems, since a large number of highly non-linear (local) constraints must be taken into account to limit the maximum stress (and/or displacement) at the element level. In this paper, we explore the feasibility of defining a so-called global constraint, which basic aim is to limit the maximum stress (and/or displacement) simultaneously within all the structure by means of one single inequality. Should this global constraint perform adequately, the complexity of the underlying mathematical programming problem would be drastically reduced. However, a certain weakening of the feasibility conditions is expected to occur when a large number of local constraints are lumped into one single inequality. With the aim of mitigating this undesirable collateral effect, we group the elements into blocks. Then, the local constraints corresponding to all the elements within each block can be combined to produce a single aggregated constraint per block. Finally, we compare the performance of these three approaches (local, global and block aggregated constraints) by solving several topology optimization problems.     

Optimization of geometry in truss design

In this paper a method is presented which attempts to minimize the weight of a 3-dimensional truss structure subject to displacement-, stress- and buckling constraints under multiple load conditions. Both the cross section areas of the bars and the geometry (but not the topology) of the structure are permitted to vary during the optimization.The method generates a sequence of subproblems which are solved by a dual method of convex programming. The convergence of the overall algorithm is in evidence on some test problems.     

A lower-bound formulation for the geometry and topology optimization of truss structures under multiple loading

In this contribution, we propose an effective formulation to address the stress-based minimum volume problem of truss structures. Starting from the lower-bound formulation in topology optimization, the problem is further expanded to geometry optimization and multiple loading scenarios, and systematically reformulated to alleviate numerical difficulties related to the melting node effect and stress singularities. The subsequent simultaneous analysis and design (SAND) formulation is well suited for a direct treatment by introducing a barrier function. Using exact second derivatives, this difficult class of problem is solved by sequential quadratic programming with trust regions. These building blocks result into an integrated design process. Two examples–including a large-scale application–illustrate the robustness of the proposed formulation.     

Fuzzy multiobjective optimization of truss-structures using genetic algorithm

In this paper, a method for solving fuzzy multiobjective optimization of space truss with a genetic algorithm is proposed. This method enables a flexible method for optimal system design by applying fuzzy objectives and fuzzy constraints. The displacement, tensile stress, fuzzy sets, membership functions and minimum size constraints are considered in formulation of the design problem. An algorithm was developed by using MATLAB programming. The algorithm is illustrated on 56-bar space truss system design problem and the results are discussed.     

灰色二层多目标线性规划问题及其解法

针对二层多目标线性规划问题,结合灰色系统的特性,提出了一般灰色二层多目标线性规划问题,并给出了模型的相关定义和定理.针对漂移型灰色二层多目标线性规划问题,提出一种具有全局收敛性质的求解算法.首先通过线性加权模理想点法把多目标转化为单目标;然后当可行域为非空紧集时,利用库恩塔克条件把双层转化为单层,再利用粒子群算法搜索单目标单层线性规划即可得到原问题的解;最后通过算例表明了该算法的有效性.     

Some aspects of truss topology optimization

The present paper studies some aspects of formulations of truss topology optimization problems. The ground structure approach-based formulations of three types of truss topology optimization problems, namely the problems of minimum weight design for a given compliance, of minimum weight design with stress constraints and of minimum weight design with stress constraints and local buckling constraints are examined. The common difficulties with the formulations of the three problems are discussed. Since the continuity of the constraint or/and objective function is an important factor for the determination of the mathematical structure of optimization problems, the issue of the continuity of stress, displacement and compliance functions in terms of the cross-sectional areas at zero area is studied. It is shown that the bar stress function has discontinuity at zero crosssectional area, and the structural displacement and compliance are continuous functions of the cross-sectional area. Based on the discontinuity of the stress function we point out the features of the feasible domain and global optimum for optimization problems with stress and/or local buckling constraints, and conclude that they are mathematical programming with discontinuous constraint functions and that they are essentially discrete optimization problems. The difference between topology optimization with global constraints such as structural compliance and that with local constraints on stress or/and local buckling is notable and has important consequences for the solution approach.