A Branch and Bound-Based Algorithm for the Weak Linear Bilevel Programming Problems

最真实世界的优化问题是层次的包含非合作的目的。许多能这些问题被提出以(上面的水平) 首先，客观功能在印射的答案集合上正在被最小化第二(底层) 优化问题。经常上面的水平决定制造者是风险反对的。问题的产生的类被称为弱上下两层的编程问题。这篇论文论述把一个惩罚功能方法嵌进一个分支的一个新算法和界限算法处理一个弱线性上下两层的编程问题。一个例子说明建议算法的可行性。

Multi-objective optimization in a finite time thermodynamic method for dish-Stirling by branch and bound method and MOPSO algorithm

There are various analyses for a solar system with the dish-Stirling technology.One of those analyses is the finite time thermodynamic analysis by which the total power of the system can be obtained by calculating the process time.In this study,the convection and radiation heat transfer losses from collector surface,the conduction heat transfer between hot and cold cylinders,and cold side heat exchanger have been considered.During this investigation,four objective functions have been optimized simultaneously,including power,efficiency,entropy,and economic factors.In addition to the fourobjective optimization,three-objective,two-objective,and single-objective optimizations have been done on the dish-Stirling model.The algorithm of multi-objective particle swarm optimization(MO P S O)with post-expression of preferences is used for multi-objective optimizations while the branch and bound algorithm with pre-expression of preferences is used for single-objective and multi-objective optimizations.In the case of multi-objective optimizations with post-expression of preferences,Pareto optimal front are obtained,afterward by implementing the fuzzy,LINMAP,and TOPSIS decision making algorithms,the single optimum results can be achieved.The comparison of the results shows the benefits of MOPSO in optimizing dish Stirling finite time thermodynamic equations.

Algorithms for Multicriteria Scheduling Problems to Minimize Maximum Late Work, Tardy, and Early

This study examines the multicriteria scheduling problem on a single machine to minimize three criteria: the maximum cost function, denoted by maximum late work (Vmax), maximum tardy job, denoted by (Tmax), and maximum earliness (Emax). We propose several algorithms based on types of objectives function to be optimized when dealing with simultaneous minimization problems with and without weight and hierarchical minimization problems. The proposed Algorithm (3) is to find the set of efficient solutions for 1//F (Vmax, Tmax, Emax) and 1//(Vmax + Tmax + Emax). The Local Search Heuristic Methods (Descent Method (DM), Simulated Annealing (SA), Genetic Algorithm (GA), and the Tree Type Heuristics Method (TTHM) are applied to solve all suggested problems. Finally, the experimental results of Algorithm (3) are compared with the results of the Branch and Bound (BAB) method for optimal and Pareto optimal solutions for smaller instance sizes and compared to the Local Search Heuristic Methods for large instance sizes. These results ensure the efficiency of Algorithm (3) in a reasonable time.

On the “Onion Husk” Algorithm for Approximate Solution of the Traveling Salesman Problem

The paper describes some implementation aspects of an algorithm for approximate solution of the traveling salesman problem based on the construction of convex closed contours on the initial set of points (“cities”) and their subsequent combination into a closed path (the so-called contour algorithm or “onion husk” algorithm). A number of heuristics related to the different stages of the algorithm are considered, and various variants of the algorithm based on these heuristics are analyzed. Sets of randomly generated points of different sizes (from 4 to 90 and from 500 to 10,000) were used to test the algorithms. The numerical results obtained are compared with the results of two well-known combinatorial optimization algorithms, namely the algorithm based on the branch and bound method and the simulated annealing algorithm. .

Exact Algorithm to Solve the Minimum Cost Multi-Constrained Multicast Routing Problem

The optimal solution of the multi-constrained QoS multicast routing problem is a tree-like hierarchical structure in the topology graph. This multicast route contains a feasible path from the source node to each of the destinations with respect to a set of QoS constraints while minimizing a cost function. Often, it is a tree. In other cases, the hierarchies can return several times to nodes and links of the topology graph. Similarly to Steiner problem, finding such a structure is an NP-hard problem. The usual tree and topology enumeration algorithms applied for the Steiner problem cannot be used to solve the addressed problem. In this paper, we propose an exact algorithm based on the Branch and Bound principle and improved by the Lookahead technique. We show relevant properties of the optimum hierarchy permitting efficient pruning of the search space. To our knowledge, our paper is the first to propose an exact algorithm for this non-trivial multi-constrained optimal multicast route computation. Simulations illustrate the efficiency of the proposed pruning operations. The analysis of the execution time shows that in simple topologies and with tight QoS constraints the exact algorithm requires relatively little execution time. With loose constraints the computation time cannot be tolerated even for off-line route computation. In these cases, the solution is close to a Steiner tree and heuristics can be applied. These results can serve as basis for the design of efficient, polynomial-time routing algorithms.

OPTIMIZATION OF MULTIPLE-CHANNEL COOPERATIVE SPECTRUM SENSING WITH DATA FUSION RULE IN COGNITIVE RADIO NETWORKS

This paper focuses on multi-channel Cooperative Spectrum Sensing (CSS) where Secondary Users (SUs) are assigned to cooperatively sense multiple channels simultaneously. A multi-channel CSS optimization problem of joint spectrum sensing and SU assignment based on data fusion rule is formulated, which maximizes the total throughput of the Cognitive Radio Network (CRN) subject to the constraints of probabilities of detection and false alarm. To address the optimization problem, a Branch and Bound (BnB) algorithm and a greedy algorithm are proposed to obtain the optimal solutions. Simulation results are presented to demonstrate the effectiveness of our proposed algorithms and show that the throughput improvement is achieved through the joint design. It is also shown that the greedy algorithm with a low complexity achieves the comparable performance to the exhaustive algorithm.

Optimization of observing sequence based on nominal trajectories of symmetric observing con guration

This paper presents the crucial method for obtaining our team's results in the 8th Global Trajectory Optimization Competition(GTOC8).Because the positions and velocities of spacecraft cannot be completely determined by one observation on one radio source,the branch and bound method for sequence optimization of multi-asteroid exploration cannot be directly applied here.To overcome this diculty,an optimization method for searching the observing sequence based on nominal low-thrust trajectories of the symmetric observing con guration is proposed.With the symmetric observing con guration,the normal vector of the triangle plane formed by the three spacecraft rotates in the ecliptic plane periodically and approximately points to the radio sources which are close to the ecliptic plane.All possible observing opportunities are selected and ranked according to the nominal trajectories designed by the symmetric observing con guration.First,the branch and bound method is employed to nd the optimal sequence of the radio source with thrice observations.Second,this method is also used to nd the optimal sequence of the left radio sources.The nominal trajectories are then corrected for accurate observations.The performance index of our result is 128,286,317.0 km which ranks the second place in GTOC8.

Economic optimization of resource-constrained project scheduling:a two-phase metaheuristic approach

This paper deals with the problem of project scheduling subject to multiple execution modes with non-renewable resources, and a model that handles some of monetary issues in real world applications.The objective is to schedule the activities to maximize the expected net present value(NPV) of the project, taking into account the activity costs, the activity durations, and the cash flows generated by successfully completing an activity.Owing to the combinatorial nature of this problem, the current study develops a hybrid of branch-and-bound procedure and memetic algorithm to enhance both mode assignment and activity scheduling.Modifications for the makespan minimization problem have been made through a set of benchmark problem instances.Algorithmic performance is rated on the maximization of the project NPV and computational results show that the two-phase hybrid metaheuristic performs competitively for all instances of different problem sizes.

Optimal planning of high voltage distribution substations

Aimed at solving the problem of optimal planning for high voltage distribution substations,an efficient method is put forward.The method divides the problem into two sub-problems:source locating and combina tional optimization.The algorithm of allocating and locating alternatively(ALA)is widely used to deal with the source lo cating problem,but it is dependent on the initial location to a large degree.Thus,some modifications were made to the ALA algorithm,which could greatly improve the quality of solutions.In addition,considering the non-convex and nonconcave nature of the sub-problem of combinational optimization,the branch-and-bound technique was adopted to obtain or approximate a global optimal solution.To improve the efficiency of the branch-and-bound technique,some heuristic principles were proposed to cut those branches that may generate a global optimization solution with low probability.Examples show that the proposed algorithm meets the requirement of engineering and it is an effective approach to rapidly solve the problem of optimal planning for high voltage distribution substations.

A NEW GLOBAL OPTIMIZATION ALGORITHM FOR MIXED-INTEGER QUADRATICALLY CONSTRAINED QUADRATIC FRACTIONAL PROGRAMMING PROBLEM

The mixed-integer quadratically constrained quadratic fractional programming(MIQCQFP)problem often appears in various fields such as engineering practice,management science and network communication.However,most of the solutions to such problems are often designed for their unique circumstances.This paper puts forward a new global optimization algorithm for solving the problem MIQCQFP.We first convert the MIQCQFP into an equivalent generalized bilinear fractional programming(EIGBFP)problem with integer variables.Secondly,we linearly underestimate and linearly overestimate the quadratic functions in the numerator and the denominator respectively,and then give a linear fractional relaxation technique for EIGBFP on the basis of non-negative numerator.After that,combining rectangular adjustment-segmentation technique and midpointsampling strategy with the branch-and-bound procedure,an efficient algorithm for solving MIQCQFP globally is proposed.Finally,a series of test problems are given to illustrate the effectiveness,feasibility and other performance of this algorithm.