A hybrid optimization method and its role in computer-aided design

The variable metric methods have been analyzed and exploited in the past to achieve a superlinear rate of convergence in unconstrained optimization. Recently, the update formulas used in these methods have been extended for constrained optimization. The update formulas construct approximate second order derivatives using first order information. These are referred to as constrained variable metric (CVM) methods. Higher order of convergence is often accompanied by a smaller domain of convergence. To overcome this limitation of CVM methods, a hybrid optimization algorithm is presented in this paper. It uses a cost function bounding concept initially and a CVM method in later stages of the search process. In addition, the algorithm uses an active set strategy and is globally convergent. An improved active set strategy is suggested. Besides developing a superlinear optimization algorithm, an efficient programming structure for computer-aided design of engineering systems is suggested and implemented. A number of mathematical programming problems, and small and large scale engineering design problems are solved to test numerical aspects of the algorithm. The algorithm has performed extremely well on the test problems.     

Compact representations of all members of an independence system

It is well known that (reduced, ordered) binary decision diagrams (BDDs) can sometimes be compact representations of the full solution set of Boolean optimization problems. Recently they have been suggested to be useful as discrete relaxations in integer and constraint programming (Hoda et al. 2010). We show that for every independence system there exists a top-down (i.e., single-pass) construction rule for the BDD. Furthermore, for packing and covering problems on n variables whose bandwidth is bounded by \(\mathcal {O}(\log n)\) the maximum width of the BDD is bounded by \(\mathcal {O}(n)\). We also characterize minimal widths of BDDs representing the set of all solutions to a stable set problem for various basic classes of graphs. Besides implicitly enumerating or counting all solutions and optimizing a class of nonlinear objective functions that includes separable functions, the results can be applied for effective evaluation of generating functions.     

Application of 0-1 integer programming to multitarget tracking problems

This paper presents a new approach to the solution of multi-target tracking problems. 0-1 integer programming methods are used to alleviate the combinatorial computing difficulties that accompany any but the smallest of such problems. Multitarget tracking is approached as an unsupervised pattern recognition problem. A multiple-hypothesis test is performed to determine which particular combination of the many feasible tracks is most likely to represent actual targets. This multiple hypothesis test is shown to have the computational structure of the set packing and set partitioning problems of 0-1 integer programming. Multitarget tracking problems that are translated into this form can be rapidly solved, using well-known discrete optimization techniques such as implicit enumeration.     

Simulation based optimization of stochastic systems with integer design variables by sequential multipoint linear approximation

Optimization problems are considered for which objective function and constraints are defined as expected values of stochastic functions that can only be evaluated at integer design variable levels via a computationally expensive computer simulation. Design sensitivities are assumed not to be available. An optimization approach is proposed based on a sequence of linear approximate optimization subproblems. Within each search subregion a linear approximate optimization subproblem is built using response surface model building. To this end, N simulation experiments are carried out in the search subregion according to a D-optimal experimental design. The linear approximate optimization problem is solved by integer linear programming using corrected constraint bounds to account for any uncertainty due to the stochasticity. Each approximate optimum is evaluated on the basis of M simulation replications with respect to objective function change and feasibility of the design. The performance of the optimization approach and the influence of parameters N and M is illustrated via two analytical test problems. A third example shows the application to a production flow line simulation model. Received April 28, 2000     

A sequential approximate programming strategy for reliability-based structural optimization

Although reliability-based structural optimization (RBSO) is recognized as a rational structural design philosophy that is more advantageous to deterministic optimization, most common RBSO is based on straightforward two-level approach connecting algorithms of reliability calculation and that of design optimization. This is achieved usually with an outer loop for optimization of design variables and an inner loop for reliability analysis. A number of algorithms have been proposed to reduce the computational cost of such optimizations, such as performance measure approach, semi-infinite programming, and mono-level approach. Herein the sequential approximate programming approach, which is well known in structural optimization, is extended as an efficient methodology to solve RBSO problems. In this approach, the optimum design is obtained by solving a sequence of sub-programming problems that usually consist of an approximate objective function subjected to a set of approximate constraint functions. In each sub-programming, rather than direct Taylor expansion of reliability constraints, a new formulation is introduced for approximate reliability constraints at the current design point and its linearization. The approximate reliability index and its sensitivity are obtained from a recurrence formula based on the optimality conditions for the most probable failure point (MPP). It is shown that the approximate MPP, a key component of RBSO problems, is concurrently improved during each sub-programming solution step. Through analytical models and comparative studies over complex examples, it is illustrated that our approach is efficient and that a linearized reliability index is a good approximation of the accurate reliability index. These unique features and the concurrent convergence of design optimization and reliability calculation are demonstrated with several numerical examples.     

基于混合整数规划的智能车横纵向一体化滚动优化决策

本文针对智能车辆的行为决策问题, 设计了基于混合整数规划的智能车横纵向一体化滚动优化决策方法. 该方法首先将纵向车速表示为非整数, 将期望车道表示为整数控制量, 建立了混合整数智能车决策简化模型; 然后, 设计了横纵向一体化滚动优化决策方法, 决策出纵向车速和换道动作, 根据系统输出与非线性约束的时域关系证明 了优化问题的递归可行性并通过遗传算法求解非线性混合整数规划优化问题. 基于车辆动力学仿真软件veDYNA 和Simulink进行了联合仿真, 并在红旗E-HS3智能车上开展了实车试验, 结果表明, 本文提出的基于混合整数规划的 智能车横纵向一体化决策方法能够实现超车、避障、跟车、停车和弯道工况下的行为决策.     

Modeling and Visualization for a Production Planning Decision Support System

This paper describes the process of decision support systems development for the optimization of the aggregate production planning problem for an important manufacturer of applicances in Chile. This work is part of a more general research effort, whose purpose is to build a generator of software applications for logistic problems in industry, based on optimization models. We take advantage of powerful tools and approaches for the modeling stage, and for building systems with user friendly interfaces and good data management capabilities. The production planning problem is formulated as a mixed integer programming model, which is solved using CPLEX. The system is currently being used by the company for their decision processes in manufacturing.     

Evaluation of mixed integer programming formulations for non-preemptive parallel machine scheduling problems

Mixed integer programming (MIP) formulations for scheduling problems can be classified based on the decision variables upon which they rely. In this paper, four different MIP formulations based on four different types of decision variables are presented for various parallel machine scheduling problems. The goal of this research is to identify promising optimization formulation paradigms that can subsequently be used to either (1) solve larger practical scheduling problems of interest to optimality and/or (2) be used to establish tighter lower solution bounds for those under study. We present the computational results and discuss formulation efficacy for total weighted completion time and maximum completion time problems for the identical parallel machine case.     

An Integer Linear Programming Problem with Multi-Criteria and Multi-Constraint Levels: a Branch-and-Partition Algorithm

In this paper, we propose a branch-and-partition algorithm to solve the integer linear programming problem with multi-criteria and multi-constraint levels (MC-ILP). The procedure begins with the relaxation problem that is formed by ignoring the integer restrictions. In this branch-and-partition procedure, an MC linear programming problem is adopted by adding a restriction according to a basic decision variable that is not integer. Then the MC-simplex method is applied to locate the set of all potential solutions over possible changes of the objective coefficient parameter and the constraint parameter for a regular MC linear programming problem. We use parameter partition to divide the (λ, γ) space for integer solutions of MC problem. The branch-and-partition procedure terminates when every potential basis for the relaxation problem is a potential basis for the MC-ILP problem. A numerical example is used to demonstrate the proposed algorithm in solving the MC-ILP problems. The comparison study and discussion on the applicability of the proposed method are also provided.     

结束时间不确定的投资组合选择问题建模与模型求解方法

针对结束时间具有不确定性的投资问题,建立以区间风险值(PVaR)度量市场风险的收益最大化投资组合选择模型.PVaR计算的复杂性使得模型难以运用一般优化方法求解,因此提出并证明可以通过求解等效的混合整数规划模型来得到原模型的最优解.利用实际股价数据进行数值实验分析,结果表明,求解混合整数规划模型针对小规模短期投资问题可以快速给出最优投资决策方案.     

Research on Web service selection based on cooperative evolution

Web service selection, as an important part of Web service composition, has direct influence on the quality of composite service. Therefore, it has attracted many researchers to focus on the research of quality of service (QoS) driven Web service selection in the past years, and many algorithms based on integer programming (IP), mixed integer linear programming (MILP), multi-dimension multi-choice 0–1 knapsack problem (MMKP), Markov decision programming (MDP), genetic algorithm (GA), and particle swarm optimization (PSO) and so on, have been presented to solve it, respectively. However, these results have not been satisfied at all yet. In this paper, a new cooperative evolution (Co-evolution) algorithm consists of stochastic particle swarm optimization (SPSO) and simulated annealing (SA) is presented to solve the Web service selection problem (WSSP). Furthermore, in view of the practical Web service composition requirements, an algorithm used to resolve the service selection with multi-objective and QoS global optimization is presented based on SPSO and the intelligent optimization theory of multi-objective PSO, which can produce a set of Pareto optimal composite services with constraint principles by means of optimizing various objective functions simultaneously. Experimental results show that Co-evolution algorithm owns better global convergence ability with faster convergence speed. Meanwhile, multi-objective SPSO is both feasible and efficient.     

Size optimization for hybrid photovoltaic–wind energy system using ant colony optimization for continuous domains based integer programming

In this paper, ant colony optimization for continuous domains (ACO_R) based integer programming is employed for size optimization in a hybrid photovoltaic (PV)–wind energy system. ACO_R is a direct extension of ant colony optimization (ACO). Also, it is the significant ant-based algorithm for continuous optimization. In this setting, the variables are first considered as real then rounded in each step of iteration. The number of solar panels, wind turbines and batteries are selected as decision variables of integer programming problem. The objective function of the PV–wind system design is the total design cost which is the sum of total capital cost and total maintenance cost that should be minimized. The optimization is separately performed for three renewable energy systems including hybrid systems, solar stand alone and wind stand alone. A complete data set, a regular optimization formulation and ACO_R based integer programming are the main features of this paper. The optimization results showed that this method gives the best results just in few seconds. Also, the results are compared with other artificial intelligent (AI) approaches and a conventional optimization method. Moreover, the results are very promising and prove that the authors’ proposed approach outperforms them in terms of reaching an optimal solution and speed.     

Solving Irregular Econometric and Mathematical Optimization Problems with a Genetic Hybrid Algorithm

In the present paper we apply a new Genetic Hybrid Algorithm (GHA) to globally minimize a representative set of ill-conditioned econometric/mathematical functions. The genetic algorithm was specifically designed for nonconvex mixed integer nonlinear programming problems and it can be successfully applied to both global and constrained optimization. In previous studies, we have demonstrated the efficiency of the GHA in solving complicated NLP, INLP and MINLP problems. The present study is a continuation of this research, now focusing on a set of highly irregular optimization problems. In this paper we discuss the genetic hybrid algorithm, the nonlinear problems to be solved and present the results of the empirical tests.     

Applying software engineering techniques in the development and management of linear and integer programming applications

This work addresses characteristics of software environments for mathematical modeling and proposes a system for developing and managing models of linear and integer programming (IP) problems. The main features of this modeling environment are: version control of models and data; client‐server architecture, which allows the interaction among modelers and decision makers; the use of a database to store information about the models and data scenarios; and the use of remote servers of optimization, which allows the optimization problems to be solved on different machines. The modeling environment proposed in this work was validated using mathematical programming models that exploit different characteristics, such as the treatment of conditions for generating variables and constraints, the use of calculated parameters derived from other parameters, and the use of integer and continuous variables in mixed IP models among others. This validation showed that the proposed environment is able to treat models found in various application areas of operations research and to solve problems with tens of thousands of variables and constraints.     

Global optimization of mixed-integer nonlinear (polynomial) programming problems: the Bernstein polynomial approach

In this paper, we propose an algorithm for constrained global optimization of mixed-integer nonlinear programming (MINLP) problems. The proposed algorithm uses the Bernstein polynomial form in a branch-and-bound framework. Ingredients such as continuous relaxation, branching for integer decision variables, and fathoming for each subproblem in the branch-and-bound tree are used. The performance of the proposed algorithm is tested and compared with several state-of-the-art MINLP solvers, on two sets of test problems. The results of the tests show the superiority of the proposed algorithm over the state-of-the-art solvers in terms of the chosen performance metrics.     

基于战略对应的IT项目组合选择模型

把信息技术项目当作组合来管理可以通过平衡风险和收益来促进企业目标和IT应用的结合,但由于决策信息的不确定性和IT项目目标与企业战略的难以对应,企业面临IT项目组合选择的挑战。构建基于战略对应的IT项目组合选择模型,其中模糊集和模糊层次分析法用来刻画不确定信息和评估IT项目风险、成本及收益,关键成功因素法用来提高IT项目与企业战略的对应,并建立模糊0－1整数规划。利用定性可能性理论把模糊组合选择模型转化为一般可求解的整数规划形式,最后用一个案例说明模型的用法。     

用优选法解系统可靠性最优化问题的一个简捷算法

冗余系统可靠性最优化问题在本质上属于非线性整数规划.现有的严格解法和近似解法 要求浩繁的计算,因而较简单的直接寻查法引起了重视.本文提出,用优选法解可靠性最优化 问题是值得探讨的;在一定范围内灵活掌握工程性约束条件,有可能简化可靠性最优化问题的 求解,具有实际意义. 本文采用优选法的分批试验法,对文献[8]的算法作了进一步的简化,从而提出一个更简 捷的算法.文中举例说明这种算法的应用,并和文献结果进行了比较.     

An algorithm based on ant colony optimization for the minimum connected dominating set problem

Ant colony optimization is a well established metaheuristic from the swarm intelligence field for solving difficult optimization problems. In this work we present an application of ant colony optimization to the minimum connected dominating set problem, which is an NP-hard combinatorial optimization problem. Given an input graph, valid solutions are connected subgraphs of the given input graph. Due to the involved connectivity constraints, out-of-the-box integer linear programming solvers do not perform well for this problem. The developed ant colony optimization algorithm uses reduced variable neighborhood search as a sub-routine. Moreover, it can be applied to the weighted and to the non-weighted problem variants. An extensive experimental evaluation presents the comparison of our algorithm with the respective state-of-the-art techniques from the literature. It is shown that the proposed algorithm outperforms the current state of the art for both problem variants. For comparison purposes we also develop a constraint programming approach based on graph variables. Even though its performance deteriorates with growing instance size, it performs surprisingly well, solving 315 out of 481 considered problem instances to optimality.     

基于单纯形法和局部枚举解混合整数线性规划问题

提出了一种基于单纯形法和局部枚举求解整数线性规划问题的新方法。它通过单纯形法得到松弛问题的最优解并确定变量以及目标函数取值范围,然后基于目标函数,进行局部枚举,从而得到其整数线性规划问题的最优解,与现有方法比较,新解法简单,计算量少,尤其是对于大规模整数线性规划问题,计算量少体现地更明显。     

Interactive intuitionistic fuzzy methods for multilevel programming problems

Multilevel programming problems model a decision-making process with a hierarchy structure. Traditional solution methods including vertex enumeration algorithms and penalty function methods are not only inefficient to obtain the solution of the multilevel programming problems, but also lead to a paradox that the follower’s decision power dominates the leader’s. In this paper, both multilevel programming and intuitionistic fuzzy set are used to model problems in hierarchy expert and intelligent systems. We first present a score function to objectively depict the satisfactory degrees of decision makers by virtue of the intuitionistic fuzzy set for solving multilevel programming problems. Then we develop three optimization models and three interactive intuitionistic fuzzy methods to consider different satisfactory solutions for the requirements of expert decision makers. Furthermore, a new distance function is proposed to measure the merits of a satisfactory solution. Finally, a case study for cloud computing pricing problems and several numerical examples are given to verify the applicability and the effectiveness of the proposed models and methods.