Definition of the feasible solution set in multicriteria optimization problems with continuous, discrete, and mixed design variables

Engineering optimization problems are multicriteria with continuous, discrete, and mixed design variables. Correct definition of the feasible solution set is of fundamental importance in these problems. It is quite difficult for the expert to define this set. For this reason, the results of searching for optimal solutions frequently have no practical meaning. Furthermore, correct definition of this set makes it possible to significantly reduce the time of searching for optimal solutions. This paper describes construction of the feasible solution set with continuous, discrete, and mixed design variables on the basis of Parameter Space Investigation (PSI) method.     

多变量、多约束连续或离散的非线性规划的一个通用算法

利用目标函数对约束函数关于设计变量的一阶微分或差分之比,给出了一个求解非线性规划的通用算法．不论变量和约束有多少,也不论变量是连续的还是离散的,这一算法都比较有效,尤其对离散非线性规划更有效．该方法是一种搜索法,勿需解任何数学方程,只需要计算函数值以及函数对变量的偏微分或差分值．许多数值例题和运筹学中一些经典问题,如1) 一、二维的背包问题;2) 一、二维资源分配问题;3) 复合系统工作可靠性问题;4) 机器负荷问题等,经用此法求解验证均较传统方法更有效和可靠．该方法的主要优点是:1) 不受问题的规模限制;2) 只要在可行域（集）内存在目标函数和约束函数及其一阶导数或差分的值,肯定可以搜索到最优的解,没有不收敛和不稳定的问题．     

Implicitly and densely discrete black-box optimization problems

This paper addresses derivative-free optimization problems where the variables lie implicitly in an unknown discrete closed set. The evaluation of the objective function follows a projection onto the discrete set, which is assumed dense (and not sparse as in integer programming). Such a mathematical setting is a rough representation of what is common in many real-life applications where, despite the continuous nature of the underlying models, a number of practical issues dictate rounding of values or projection to nearby feasible figures. We discuss a definition of minimization for these implicitly discrete problems and outline a direct-search algorithm framework for its solution. The main asymptotic properties of the algorithm are analyzed and numerically illustrated.     

New simulation-based frameworks for multi-objective reliability-based design optimization of structures

In the present study, two new simulation-based frameworks are proposed for multi-objective reliability-based design optimization (MORBDO). The first is based on hybrid non-dominated sorting weighted simulation method (NSWSM) in conjunction with iterative local searches that is efficient for continuous MORBDO problems. According to NSWSM, uniform samples are generated within the design space and, then, the set of feasible samples are separated. Thereafter, the non-dominated sorting operator is employed to extract the approximated Pareto front. The iterative local sample generation is then performed in order to enhance the accuracy, diversity, and increase the extent of non-dominated solutions. In the second framework, a pseudo-double loop algorithm is presented based on hybrid weighted simulation method (WSM) and the Non-dominated Sorting Genetic Algorithm II (NSGA-II) that is efficient for problems including both discrete and continuous variables. According to hybrid WSM-NSGA-II, proper non-dominated solutions are produced in each generation of NSGA-II and, subsequently, WSM evaluates the reliability level of each candidate solution until the algorithm converges to the true Pareto solutions. The valuable characteristic of presented approaches is that only one simulation run is required for WSM during entire optimization process, even if solutions for different levels of reliability be desired. Illustrative examples indicate that NSWSM with the proposed local search strategy is more efficient for small dimension continuous problems. However, WSM-NSGA-II outperforms NSWSM in terms of solutions quality and computational efficiency, specifically for discrete MORBDOs. Employing global optimizer in WSM-NSGA-II provided more accurate results with lower samples than NSWSM.     

An exact penalty function method for nonlinear mixed discrete programming problems

In this paper, we consider a general class of nonlinear mixed discrete programming problems. By introducing continuous variables to replace the discrete variables, the problem is first transformed into an equivalent nonlinear continuous optimization problem subject to original constraints and additional linear and quadratic constraints. Then, an exact penalty function is employed to construct a sequence of unconstrained optimization problems, each of which can be solved effectively by unconstrained optimization techniques, such as conjugate gradient or quasi-Newton methods. It is shown that any local optimal solution of the unconstrained optimization problem is a local optimal solution of the transformed nonlinear constrained continuous optimization problem when the penalty parameter is sufficiently large. Numerical experiments are carried out to test the efficiency of the proposed method.     

离散优化问题最优值函数的连续性质

对优化问题的最优值研究是有意义的, 尽管有时并不知道怎样寻求最优值. 研究了几个重要的组合最优化问题的目标值随着输入值变化的连续化性质, 重点研究几个经典的、有代表性的离散优化问题：极小化最大完工时间的排序问题、背包问题、旅行商问题等, 以连续的数学分析思维模式审视离散问题. 最后, 研究了一些近似算法对应的目标函数的性质.     

Robustness analysis in Multi-Objective Mathematical Programming using Monte Carlo simulation

In most multi-objective optimization problems we aim at selecting the most preferred among the generated Pareto optimal solutions (a subjective selection among objectively determined solutions). In this paper we consider the robustness of the selected Pareto optimal solution in relation to perturbations within weights of the objective functions. For this task we design an integrated approach that can be used in multi-objective discrete and continuous problems using a combination of Monte Carlo simulation and optimization. In the proposed method we introduce measures of robustness for Pareto optimal solutions. In this way we can compare them according to their robustness, introducing one more characteristic for the Pareto optimal solution quality. In addition, especially in multi-objective discrete problems, we can detect the most robust Pareto optimal solution among neighboring ones. A computational experiment is designed in order to illustrate the method and its advantages. It is noteworthy that the Augmented Weighted Tchebycheff proved to be much more reliable than the conventional weighted sum method in discrete problems, due to the existence of unsupported Pareto optimal solutions.     

Discrete linear bilevel programming problem

In this paper, we analyze some properties of the discrete linear bilevel program for different discretizations of the set of variables. We study the geometry of the feasible set and discuss the existence of an optimal solution. We also establish equivalences between different classes of discrete linear bilevel programs and particular linear multilevel programming problems. These equivalences are based on concave penalty functions and can be used to design penalty function methods for the solution of discrete linear bilevel programs.Support of this work has been provided by the INIC (Portugal) under Contract 89/EXA/5, by INVOTAN, FLAD, and CCLA (Portugal), and by FCAR (Québec), NSERC, and DND-ARP (Canada).     

Interactive Polyhedral Outer Approximation (IPOA) strategy for general multiobjective optimization problems

We propose an interactive polyhedral outer approximation (IPOA) method to solve a broad class of multiobjective optimization problems (MOP) with, possibly, nonlinear and nondifferentiable objective and constraint functions, and with continuous or discrete decision variables. During the interactive optimization phase, the method progressively constructs a polyhedral approximation of the decision-maker’s (DM’s) unknown preference structure and a polyhedral outer-approximation of the feasible set of MOP. The piecewise linear approximation of the DM’s preferences also provides a mechanism for testing the consistency of the DM’s assessments and removing inconsistencies; it also allows post-optimality analysis. All the feasible trial solutions are non-dominated (efficient, or Pareto-optimal) so preference assessments are made in the context of non-dominated alternatives only. Upper and lower bounds on the yet unknown optimal value are produced at every iteration, allowing terminating the search prematurely at a good-enough solution and providing information about the closeness of this solution to the optimal solution. The IPOA method includes a preliminary phase in which a limited probe of the efficient set is conducted in order to find a good initial trial solution for the interactive phase. The computational requirements of the algorithm are relatively simple. The results of an extensive computational study are reported.     

Design of a motorcycle frame using neuroacceleration strategies in MOEAs

Designing a low-budget lightweight motorcycle frame with superior dynamic and mechanical properties is a complex engineering problem. This complexity is due in part to the presence of multiple design objectives—mass, structural stress and rigidity—, the high computational cost of the finite element (FE) simulations used to evaluate the objectives, and the nature of the design variables in the frame’s geometry (discrete and continuous). Therefore, this paper presents a neuroacceleration strategy for multiobjective evolutionary algorithms (MOEAs) based on the combined use of real (FE simulations) and approximate fitness function evaluations. The proposed approach accelerates convergence to the Pareto optimal front (POF) comprised of nondominated frame designs. The proposed MOEA uses a mixed genotype to encode discrete and continuous design variables, and a set of genetic operators applied according to the type of variable. The results show that the proposed neuro-accelerated MOEAs, NN-NSGA II and NN-MicroGA, improve upon the performance of their original counterparts, NSGA II and MicroGA. Thus, this neuroacceleration strategy is shown to be effective and probably applicable to other FE-based engineering design problems.     

Stochastic nuclear outages semidefinite relaxations

This paper deals with stochastic scheduling of nuclear power plant outages. Focusing on the main constraints of the problem, we propose a stochastic formulation with a discrete distribution for random variables, that leads to a mixed 0/1 quadratically constrained quadratic program. Then we investigate semidefinite relaxations for solving this hard problem. Numerical results on several instances of the problem show the efficiency of this approach, i.e., the gap between the optimal solution and the continuous relaxation is on average equal to 53.35 % whereas the semidefinite relaxation yields an average gap of 2.76 %. A feasible solution is then obtained with a randomized rounding procedure.     

An algorithm for nonlinear optimization problems with binary variables

One of the challenging optimization problems is determining the minimizer of a nonlinear programming problem that has binary variables. A vexing difficulty is the rate the work to solve such problems increases as the number of discrete variables increases. Any such problem with bounded discrete variables, especially binary variables, may be transformed to that of finding a global optimum of a problem in continuous variables. However, the transformed problems usually have astronomically large numbers of local minimizers, making them harder to solve than typical global optimization problems. Despite this apparent disadvantage, we show that the approach is not futile if we use smoothing techniques. The method we advocate first convexifies the problem and then solves a sequence of subproblems, whose solutions form a trajectory that leads to the solution. To illustrate how well the algorithm performs we show the computational results of applying it to problems taken from the literature and new test problems with known optimal solutions.     

A modification of the stochastic ruler method for discrete stochastic optimization

We propose a modified stochastic ruler method for finding a global optimal solution to a discrete optimization problem in which the objective function cannot be evaluated analytically but has to be estimated or measured. Our method generates a Markov chain sequence taking values in the feasible set of the underlying discrete optimization problem; it uses the number of visits this sequence makes to the different states to estimate the optimal solution. We show that our method is guaranteed to converge almost surely (a.s.) to the set of global optimal solutions. Then, we show how our method can be used for solving discrete optimization problems where the objective function values are estimated using either transient or steady-state simulation. Finally, we provide some numerical results to check the validity of our method and compare its performance with that of the original stochastic ruler method.     

An evolutionary programming approach to mixed-variable optimization problems

Many engineering optimization problems frequently encounter discrete variables as well as continuous variables and the presence of nonlinear discrete variables considerably adds to the solution complexity. Very few of the existing methods can find a globally optimal solution when the objective functions are non-convex and non-differentiable. In this paper, we present a mixed-variable evolutionary programming (MVEP) technique for solving these nonlinear optimization problems which contain integer, discrete, zero-one and continuous variables. The MVEP provides an improvement in global search reliability in a mixed-variable space and converges steadily to a good solution. An approach to handle various kinds of variables and constraints is discussed. Some examples of mixed-variable optimization problems in the literature are tested, which demonstrate that the proposed approach is superior to current methods for finding the best solution, in terms of both solution quality and algorithm robustness.     

Generalized Benders’ Decomposition for topology optimization problems

This article considers the non-linear mixed 0–1 optimization problems that appear in topology optimization of load carrying structures. The main objective is to present a Generalized Benders’ Decomposition (GBD) method for solving single and multiple load minimum compliance (maximum stiffness) problems with discrete design variables to global optimality. We present the theoretical aspects of the method, including a proof of finite convergence and conditions for obtaining global optimal solutions. The method is also linked to, and compared with, an Outer-Approximation approach and a mixed 0–1 semi definite programming formulation of the considered problem. Several ways to accelerate the method are suggested and an implementation is described. Finally, a set of truss topology optimization problems are numerically solved to global optimality.     

Stochastic Methods for Practical Global Optimization

Engineering design problems often involve global optimization of functions that are supplied as black box functions. These functions may be nonconvex, nondifferentiable and even discontinuous. In addition, the decision variables may be a combination of discrete and continuous variables. The functions are usually computationally expensive, and may involve finite element methods. An engineering example of this type of problem is to minimize the weight of a structure, while limiting strain to be below a certain threshold. This type of global optimization problem is very difficult to solve, yet design engineers must find some solution to their problem – even if it is a suboptimal one. Sometimes the most difficult part of the problem is finding any feasible solution. Stochastic methods, including sequential random search and simulated annealing, are finding many applications to this type of practical global optimization problem. Improving Hit-and-Run (IHR) is a sequential random search method that has been successfully used in several engineering design applications, such as the optimal design of composite structures. A motivation to IHR is discussed as well as several enhancements. The enhancements include allowing both continuous and discrete variables in the problem formulation. This has many practical advantages, because design variables often involve a mixture of continuous and discrete values. IHR and several variations have been applied to the composites design problem. Some of this practical experience is discussed.     

Study of multiscale global optimization based on parameter space partition

Inverse problems in geophysics are usually described as data misfit minimization problems, which are difficult to solve because of various mathematical features, such as multi-parameters, nonlinearity and ill-posedness. Local optimization based on function gradient can not guarantee to find out globally optimal solutions, unless a starting point is sufficiently close to the solution. Some global optimization methods based on stochastic searching mechanisms converge in the limit to a globally optimal solution with probability 1. However, finding the global optimum of a complex function is still a great challenge and practically impossible for some problems so far. This work develops a multiscale deterministic global optimization method which divides definition space into sub-domains. Each of these sub-domains contains the same local optimal solution. Local optimization methods and attraction field searching algorithms are combined to determine the attraction basin near the local solution at different function smoothness scales. With Multiscale Parameter Space Partition method, all attraction fields are to be determined after finite steps of parameter space partition, which can prevent redundant searching near the known local solutions. Numerical examples demonstrate the efficiency, global searching ability and stability of this method.     

Parametric Integer Programming Algorithm for Bilevel Mixed Integer Programs

We consider discrete bilevel optimization problems where the follower solves an integer program with a fixed number of variables. Using recent results in parametric integer programming, we present polynomial time algorithms for pure and mixed integer bilevel problems. For the mixed integer case where the leader’s variables are continuous, our algorithm also detects whether the infimum cost fails to be attained, a difficulty that has been identified but not directly addressed in the literature. In this case, it yields a “better than fully polynomial time” approximation scheme with running time polynomial in the logarithm of the absolute precision. For the pure integer case where the leader’s variables are integer, and hence optimal solutions are guaranteed to exist, we present an algorithm which runs in polynomial time when the total number of variables is fixed.     

Vector Optimization Problems with Generalized Functional Constraints in Variable Ordering Structure Setting

This paper connects discrete optimal transport to a certain class of multi-objective optimization problems. In both settings, the decision variables can be organized into a matrix. In the multi-objective problem, the notion of Pareto efficiency is defined in terms of the objectives together with nonnegativity constraints and with equality constraints that are specified in terms of column sums. A second set of equality constraints, defined in terms of row sums, is used to single out particular points in the Pareto-efficient set which are referred to as “balanced solutions.” Examples from several fields are shown in which this solution concept appears naturally. Balanced solutions are shown to be in one-to-one correspondence with solutions of optimal transport problems. As an example of the use of alternative interpretations, the computation of solutions via regularization is discussed.