Search

In this paper, a multi-agent distributed continuous-time algorithm is proposed to solve a large-scale linear algebraic equation Ax = d o . Unlike many existing results assuming each agent knows a few rows of A, the algorithm proposed in this paper assumes each agent knows a few columns of A. To solve the linear algebraic equation, the problem is first converted to an optimization problem with a linear constraint. Then, a distributed continuous-time algorithm is designed based on the Lagrangian function of the optimization problem. The algorithm is proved to solve the linear algebraic equation with any initial condition via a Lyapunov approach. An example is presented to show the efficacy of the proposed algorithm.

In the previous work, a continuous-time Zhang neural network (CTZNN) has been proposed for online solution of time-varying linear matrix inequality (LMI). For completeness and also for the purposes of potential digital hardware implementation and numerical algorithm development, this paper further develops the discrete-time form of such a CTZNN, which is termed as the discrete-time ZNN (DTZNN). Specifically, in this paper, by utilizing the Taylor-type difference rule, the three-step DTZNN algorithm is proposed and investigated to solve the time-varying LMI. Then, for this DTZNN algorithm, theoretical results are also given to show its excellent computational property. Numerical results further substantiate the efficacy of the proposed three-step DTZNN algorithm for time-varying LMI solving.

The linear semidefinite programming problem is considered. The primal and dual simplex-like algorithms are proposed for its solution. Both algorithms are generalizations of well-known simplex methods for linear programming. Under assumption that strict complementarity of solutions of primal and dual problems holds, convergence of methods is proved.

The report is dedicated to the description of the algorithm for one of the methods for solving mixed-integer linear programming problems, which is based on binary cuttings. One of its algorithms, a hybrid algorithm based on binary cuts and branches, which combines the idea of the branch-and-bound method with the construction of cutting planes, is extended to milp problems.

A.N. Tikhonov's approximate system of linear algebraic equations solution approach is extended to find a stable solution of a linear programming problem with an approximation of the coefficient matrix. This approach is formalized as the special case of a linear programming problem. Necessary and sufficient conditions for the existence of the solution of specified problem and the form of this solution are studied. Numerical example of the improper linear programming problem with an approximation of the coefficient matrix solution is shown.

In this paper, we propose a general iterative algorithm for numerical solution of high dimension optimization problems. The specificity of the problems considered is that the number of variables involved in linear constraints dominate over those involved in nonlinear constraints.

In wireless sensor networks, maximizing the lifetime of a data gathering tree is known to be NP-hard, so various (exponential-time) exact algorithms are designed to find the best data gathering tree. The state-of-the-art exact algorithm recursively performs graph decomposition to reduce search space. However, it essentially enumerates all possibilities in adjacent graph decompositions, and cannot handle moderately large sensor networks. In this paper, we propose an exact algorithm using integer linear programming. The challenge is that some constraints are not linear in the optimization problem. To address this challenge, instead of the optimization problem, we formulate the decision problem, and solve each decision problem by integer linear programming. The optimal value is then found by binary search over all possible lifetimes. To reduce the running time, we preprocess the graph by decomposing it into bi- connected subnetworks, and propose various rules to reduce the number of candidate lifetimes. Numerical results on simulated networks show that, within two hours, our algorithm can solve more problem instances than previous algorithms.

Most of the hybrid algorithms are produced by combination of a global optimization algorithm with a local search algorithm. In this paper, the focus is on a simple and efficient hybrid algorithm by combining the differential evolution(DE) and the Nelder-Mead simplex(NM) variant for solving global optimization problem. The DE explores the whole search space to find some promising areas and then the NM is entered to exploit optimal solution as accurately as possible. To examine the efficiency of the proposed algorithm, Thenew algorithm are used to some benchmark problems and the results are compared with of other hybrid algorithms. The results show that the proposed algorithm has superior performance in solving global optimization problems.

This paper is concerned with optimal control problems of discrete-time nonlinear systems via a novel Q-learning algorithm. In the newly developed Q-learning algorithm, the iterative Q function in each iteration is required to update on the whole state and control spaces, instead of being updated by a single state and control pair. A new convergence criterion of the corresponding Q-learning algorithm is presented, where the traditional constraints for the learning rates of Q-learning algorithms is relaxed. Finally, simulation results are provided to exemplify the good performance of the developed algorithm.

The purpose of this article is to explain how a fuzzy linear programming model can be transformed into a fuzzy multi-objective linear programming model and then solved. An algorithm is developed to present our approach and fuzzy optimal solution is obtained. To demonstrate the efficiency and feasibility of the proposed approach, one numerical example has been solved.

Playing a fundamental role in mathematic optimization, linear programming (LP) problems have been widely encountered in various scientific disciplines and industrial applications. Although static LP problems have been investigated extensively and applied to abundant scientific fields through the last decades, researches concerning time-varying linear programming (TVLP) problem solving are in relatively small amount. In this paper, the TVLP problems are solved by a linear-variational-inequality based primal-dual neural network (LVI-PDNN), which is originally designed for static LP problem solving. Numerical examples and computer simulations further reveal that LVI-PDNN could approach the theoretical solution when solving TVLP problems subject to equality, inequality and bound constraints simultaneously.

On the basis of MOEA/D-DE algorithm, the introduction of the concept of a self-adaptive differential evolution algorithm, named self-adaptive multi-objective differential evolutionary algorithm based on decomposition (SAMODEA/D). This algorithm enhances the local search algorithm in the case of maintaining the diversity of the population, while effectively avoids “premature convergence” and the occurrence of “local optimum” situation, a good solution to keep balance between the global search and local development. The experimental results have illustrated the effectiveness of the proposed algorithm.

The FICO Xpress-Optimizer is a commercial optimization solver for linear programming (LP), mixed integer linear programming (MIP), convex quadratic programming (QP), convex quadratically constrained quadratic programming (QCQP), second-order cone programming (SOCP) and their mixed-integer counterparts. Xpress also includes a general purpose non-linear solver, Xpress-NonLinear, which features a successive linear programming algorithm (SLP, first-order method), interior point methods and Artelys Knitro (second-order methods). This work explores algorithms for mixed-integer nonlinear programming problems (MINLPs), which are NP-hard in general, then it presents applications in signal processing and capitalizes advances in solving these problems with Xpress and its comprehensive suite of high-performance nonlinear solvers. Computational results show that signal processing nonlinear problems can be solved quickly and accurately, taking advantage of the algebraic modeling and procedural programming language, Xpress-Mosel, that allows to interact with the Xpress solver engines in a easy-to-learn way, and its unified modeling interface for all solvers, from linear to general nonlinear solvers.

This work presents extensions of the general methodology of employing quadratic approximations of the objective function and constraints for handling non-linear equality constraints in single-objective optimization problems. The methodology does not require any extra function evaluation since the quadratic approximations are constructed using only information that would be already obtained in the course of the optimization algorithms. The methodology is coupled with the Real Biased Genetic Algorithm to tackle non-linear single-objective optimization problems with two equality constraints. The modified algorithm is tested with a set of analytical problems. The results show the modified algorithm finds the constrained optima with enhanced precision and faster convergence. Considering that the new technique does not impose any additional cost to the algorithms, it can be stated that the technique is also suitable for costly black-box problems.

Among the mathematical optimization algorithms, simplex algorithm is a popular and practical algorithm which was listed as one of the top 10 algorithms of the twentieth century by the journal Computing in Science and Engineering. Although simplex algorithm is efficient in the linear programming, the quality of convergence is unacceptable in practice as a numerical breakdown of the algorithm, even for smooth and well-behaved functions. On the other hand, full convergence might be seen in genetic algorithms (GA) using only crossover. So in this paper we combine the GA and simplex algorithm by initializing simplex from the final individual in GA and getting the converged result through simplex algorithm thereafter. A case study in estimating gas emission shows noteworthy improvement of efficiency and stability, compared with GA or simplex algorithm.

A linear bilevel programming problem can be reformulated as a single level mathematical program with complementarity constraints, which in turn is equivalent to a mixed integer (0-1) linear programming problem. A binary differential evolution algorithm with a linear programming solver is developed to solve the mixed integer (0-1) linear programming problem. The computational results show the efficiency of the proposed algorithm.

In engineering design processes, there are many cases where feasibility has to be checked. Some applications, such as radiation therapy, can be formulated as linear feasibility problems. In addition, a feasible point is required to start many other algorithms. In this paper, we propose an interior point method for linear feasibility problems. This algorithm is suitable for problems that are large and sparse. Convergence of the algorithm is proved. Numerical experiment results on a standard set of linear programming problems are reported. This set includes some large, hard, and highly degenerated cases. The numerical experiment shows that our proposed algorithm is efficient and robust.

This article proposes to handle multi objective linear fractional programming (MOLFP) problems in fuzzy environment. As a generalized mean value theorem first order Taylor series approach is used to convert multi objective linear fractional programming to multi objective linear programming problem by introducing imprecise aspiration level to each objective. Then additive weighted method has been used to get its solution. It has been observed that optimality reached for different weight values of the membership function for the different objective functions. The method has been presented by an algorithm and sensitivity analysis for the fuzzy multi objective linear fractional programming (FMOLFP) problem with respect to aspiration level and tolerance limit are also presented. The present approach is demonstrated with one numerical example.

Linear matching (LM) is a simple and effective method for solving image matching problems. In many cases, image matching problems are nonlinear due to involvement of the geometric transformations; therefore, an essential step for utilizing linear models for image matching is to linearize the geometric transformation matrices that introduce nonlinear terms into image matching problems. Existing LM methods usually use low-order transformations to artificially initialize a linear model. In this paper, we propose a residual-consensus driven LM algorithm that generalizes existing LM methods by allowing higher order transformations to automatically initialize a linear model. Based on the observation that transformation models generated from inlier subsets exhibit correlated behaviors (termed residual consensus hereafter), we develop a residual-consensus robust estimation algorithm to project the nontrivial linear transformation problem into a much smaller subspace, and thus enable efficient optimizations through linear programming. The experimental results on synthetic and real databases demonstrate the effectiveness and robustness of the proposed algorithm.

This paper studies an online adaptive dynamic programming (ADP) algorithm for linear fixed-time impulse systems. The ADP algorithm follows the value iteration method, updating the value approximation and the control law iteratively. In the algorithm, a single network structure is adopted. The single critic network approximates the objective value function. Online training of the value function and the control laws are implemented at each iteration. The network approximated value function converges to the optimal one of the impulse system. Simulations are also presented for the validity of the presented algorithm.

In this paper it is proposed a hybrid algorithm, so-called HGVPRLB, for solving generic binary problems. The algorithm HGVPRLB combines the heuristic procedures GRASP, Variable Neighborhood Descent, Constraint Propagation and Local Branching Cuts. It was tested in a set of binary problems from MIPLIB 2010 in order to check both its ability to obtain feasible solutions as its ability to improve the value of these solutions varying the processing time. Computational experiments showed that when the processing time increases the algorithm can increase the number of feasible solutions found in the set as well the quality of the solutions. Besides it, the proposed algorithm outperforms another algorithm of literature, as well as two other open source solvers.

Evolutionary algorithms are typically run several times in design optimization problems and the best solution taken. We propose a novel online algorithm selection framework that learns to use the best algorithm based on previous runs, hence in effect using different and better algorithms as the search progresses. First, a set of algorithms are run on a benchmark problem suite. Given a new problem, a default algorithm is run and its convergence characteristics are recorded. This is used to map to the problem database to find the most similar problem. In turn, the database returns the best algorithm for this problem and this algorithm is run in the second iteration and so on, aiming to home onto the most suitable algorithm for the problem. The resulting algorithm, named Sequential Learnable Evolutionary algorithm (SLEA), outperforms Covariance Matrix Adaptation Evolution Strategy (CMA-ES) with multi-restarts. SLEA is also applied to a new problem, a real world application, and learns its characteristics. Experimental results show that it can correctly select the best algorithm for the problem. Finally, this paper proposes a new research program which learns the algorithm-problem mapping through solving real world problems accessed through the web and worldwide cooperation through Wikipedia.

This study proposes a novel technique for solving linear programming problems in a fully fuzzy environment. A modified version of the well-known dual simplex method is used for solving fuzzy linear programming problems. The use of a ranking function together with the Gaussian elimination process helps in solving linear programming problems in a fully uncertain environment. The proposed algorithm is flexible, easy and reasonable.

A multi-objective linear programming problem with a system of max-arithmetic mean relational inequalities as its constraints is considered. For each of the objective functions, the decision maker has a fuzzy goal. Treating each fuzzy goal, two kind of membership functions are considered: linear and hyperbolic as a nonlinear one. Then, using membership functions and Bellman-Zadeh decision, the multi-objective linear programming problem is converted to a conventional linear programming problem. Two examples are given to illustrate the procedure and compare the two different membership functions.

In this article, we extend kernel-based interior point algorithms for linear programming to convex quadratic programming overs second-order cones. By means of Jordan algebras, we establish the iteration complexity for long- and short-step interior-point methods, namely, equation and equation, respectively. These results coincide with the ones obtained in the linear programming case.

An efficient algorithm is proposed for finding all DC solutions of nonlinear circuits using linear programming. This algorithm is based on a simple test (termed the LP test) for nonexistence of a solution to a system of nonlinear equations in a given region. In the conventional LP test, a system of nonlinear equations is transformed into a linear programming problem by surrounding component nonlinear functions by rectangles. Then, the emptiness or nonemptiness of the feasible region is checked by the dual simplex method. In this paper, we propose a new LP test algorithm using both rectangles and parallelograms, and shows that the proposed algorithm is more efficient than the conventional algorithms using rectangles only or parallelograms only.

It could be a very challenging task to globally optimize large-scale mixed-integer fractional programs (MIFP) with separable concave and fractional terms in the objective function. To address this computational challenge, we propose a novel and efficient global optimization algorithm, which integrates an inexact parametric algorithm based on Newton's method and a successive piecewise linear approximation algorithm. To demonstrate the efficiency of this algorithm, we use it to optimize the economic and environmental performance of a manufacturing process for biodiesel and bioproducts from microalgae. The problem is solved with several global optimization methods. Computational results show that the proposed global optimization algorithm is more efficient than general-purpose MINLP solvers when solving the special type of MIFP problems.

We present three tailored algorithms for solving large-scale mixed-integer linear fractional programming (MILFP) problems. The first one combines Branch-and-Bound method with Charnes-Cooper transformation. The other two tailored MILFP solution methods are the parametric algorithm and the reformulation-linearization algorithm. Extensive computational studies are performed to demonstrate the efficiency of these algorithms and to compare them with some general-purpose mixed-integer nonlinear programming methods. A performance profile is given based on the algorithm performance analysis and benchmarking methods. The applications of these algorithms are further illustrated through an application on water supply chain optimization for shale gas production. Computational results show that the parametric algorithm and the reformulation-linearization algorithm have the highest efficiency among all the tested solution methods.

Several well-known algorithms in the field of combinatorial optimization can be interpreted in terms of the primal-dual method for solving linear programs. For example, Dijkstra's algorithm, the Ford-Fulkerson algorithm, and the Hungarian algorithm can all be viewed as the primal-dual method applied to the linear programming formulations of their respective optimization problems. Roughly speaking, successfully applying the primal-dual method to an optimization problem that can be posed as a linear program relies on the ability to find a simple characterization of the optimal solutions to a related linear program, called the ‘dual of the restricted primal’ (DRP). This paper is motivated by the following question: What is the algorithm we obtain if we apply the primal-dual method to a linear programming formulation of a discounted cost Markov decision process? We will first show that a widely-used variant of the value iteration algorithm for Markov decision processes can be interpreted in terms of the primal-dual method, where the value function is updated with suboptimal solutions to the DRP in each iteration. We then provide the optimal solution to the DRP in closed-form, and present the algorithm that results when using this solution to update the value function in each iteration. Unlike the algorithms obtained from suboptimal DRP updates, this algorithm is guaranteed to yield the optimal value function in a finite number of iterations. Finally, we show that the iterations of the primal-dual algorithm can be interpreted as repeated application of the policy iteration algorithm to a special class of Markov decision processes. When considered alongside recent results characterizing the computational complexity of the policy iteration algorithm, this observation could provide new insights into the computational complexity of solving discounted-cost Markov decision processes.

We propose an algorithm for solving quadratic programming (QP) problems with inequality and equality constraints arising from linear MPC. The proposed algorithm is based on the ‘alternating direction method of multipliers’ (ADMM), with the introduction of slack variables. In comparison with algorithms available in the literature, our proposed algorithm can handle the so-called sparse MPC formulation with general inequality constraints. Moreover, our proposed algorithm is suitable for implementation on embedded platforms where computational resources are limited. In some cases, our algorithm is division-free when certain fixed matrices are computed offline. This enables our algorithm to be implemented in fixed-point arithmetic on a FPGA. In this paper, we also propose heuristic rules to select the step size of ADMM for a good convergence rate.

In this paper, an algorithm for finding an e-globally optimal solution of the linear bilevel programming problem (LBP) is considered. We call this algorithm the improved equilibrium point algorithm. It is based on the notion of the basic equilibrium point algorithm. We propose the algorithm by adding a new cutting plan in the constraint conditions, and combining with the bilinear programming problem. Compared with the basic equilibrium point algorithm, the calculation burden is reduced when the improved equilibrium point algorithm is used in solving the LBP. At last a numerical example is given to illustrate how the algorithm works.

The mathematical programming problem investigated is: max z(x) = C1x1 + C2x2 +...+ Cnxn where x ∈ Ω = {x ∈ Rn: Ax = b,x ⩾ 0} and Ω is a feasible region of x, and the coefficients Ci are closed and bounded intervals.

This paper presents a decomposition algorithm for solving the optimal control problem (OCP) that arises in Mean-Variance Economic Model Predictive Control of stochastic linear systems. The algorithm applies the alternating direction method of multipliers to a reformulation of the OCP that decomposes into small independent subproblems. We test the decomposition algorithm using a simple power management case study, in which the OCP is formulated as a convex quadratic program. Simulations show that the decomposition algorithm scales linearly in the number of uncertainty scenarios. Moreover, a parallel implementation of the algorithm is several orders of magnitude faster than state-of-the-art convex quadratic programming algorithms, provided that the number of uncertainty scenarios is large.

The genetic algorithm with greedy heuristic, initially developed for solving location problems on networks, can be adapted for solving continuous problems such as k-means. However, the efficiency of such algorithm in case of continuous problems does not allow to use it for solving the large-scale problems. In this paper, authors propose a modification to this algorithm which allows such algorithm to work faster.

Binary quadratic programming (BQP) is a typical integer programming problem widely applied in the field of signal processing, economy, management and engineering. However, it's NP-hard and lacks efficient algorithms. Due to this reason, in this paper, a novel polynomial algorithm to linearly constrained binary quadratic programming problems with Q being a five-diagonal matrix is focused by combining the basic algorithm proposed in [1], [2], [3] and the dynamic programming method. We first briefly deduce the basic algorithm. Then, the algorithm is proposed to solve this special problem. In addition, a specific example is presented to illustrate the new algorithm. Lastly, we demonstrate its polynomial feature as well as its high efficiency.

In this paper, we study the rank-one binary matrix factorization problem, which plays a key role in analyzing the high dimensional discrete-attributed datasets. We first transform this problem into an equivalent binary quadratic programming, and then a mixed-integer linear formulation is obtained using linearization technique. A characterization on the extreme points is given for the polyhedron of the linearized formulation. To the best of our knowledge, this is the first time to study the extreme points property of the rank-one binary matrix factorization. Based on this property, a LP rounding based 2-approximation algorithm is designed for this problem. Numerical results illustrate the efficiency of the proposed approximation algorithm.

In this paper, mathematical programming problems involving (0, Q) in vex functions with respect to eta are considered. Lagrange, Fenchel and Fenchel-Lagrange dual optimization problems are derived by means of distinct perturbations of the primal problem and studied. For the various dual problems, equality and inequality relations between the optimal values are verified under appropriate assumptions.

In this paper, we consider a class of linear bi-level programming with random fuzzy coefficients, which has no mathematical meaning because of the uncertain factors. In order to make it solvable, we introduced the linear bi-level model with expected objectives and chance constraints, and propose some theorems to obtain the equivalent models. Then we employ the interactive programming technique to deal with the bi-level equivalent model. And finally we present an illustrative example to show the efficiency of the models and approaches.

In order to raise solving speed of the two-dimensional open dimension optimization algorithm, an improved parallel algorithm based on BSBIS algorithm is proposed, namely p-BSBIS. To overcome the defect of BSBIS algorithm which spends long time for complexity of the algorithm, p-BSBIS can shorten the packing time to a certain extent by using multiple nodes for parallel computing. Furthermore, the improved algorithm not only increases the operation speed but also retains accurate optimization of the original BSBIS. Simulated in the platform, the results demonstrated that p-BSBIS is better than the original algorithm for solving speed.

We discuss a multiplicative update quadratic programming algorithm with applications to model predictive control for constrained linear systems. The algorithm, named PQP, is very simple to implement and thus verify, does not require projection, offers a linear rate of convergence, and can be completely parallelized. The PQP algorithm is equipped with conditions that guarantee the desired bound on suboptimality and with an acceleration step based on projection-free line search. We also show how PQP can take advantage of the parametric structure of the MPC problem, thus moving offline several calculations and avoiding large input/output dataflows. The algorithm is evaluated on two benchmark problems, where it is shown to compete with, and possibly outperform, other open source and commercial packages.

This paper deals with a class of interval linear bilevel programming problems, in which some or all of the leader's and follower's objective function coefficients are specified in terms of intervals. The focus of solving this class of problems is on determining the optimal value range when different coefficients of objectives are taken in intervals given. In order to obtain the best and the worst optimal solutions to this class of problems, an efficient genetic algorithm is developed. Firstly, the objective coefficients of the lower level are encoded as individuals using real coding scheme, and the relative intervals are taken as the search space of the genetic algorithm. Secondly, for each encoded individual, a simplified interval linear bilevel program is obtained, in which interval coefficients are simply in the upper level objective function. Finally, the simplified problem is further divided into two linear bilevel programs without interval coefficients and solved by using the optimality theory of linear programming. The optimal values are taken as fitness values, by which the best and the worst optimal solutions can be obtained. In order to illustrate the efficiency of the proposed algorithm, two examples are solved and the results show that the algorithm is feasible and robust.

This paper proposes an improved differential evolution algorithm, named I-DE, for constrained nonlinear mixed integer programming problems. The new population initialization technology and dynamic non-linear scaling factor are applied to enhance optimization capability of algorithm. We strengthen influence of constraint matrix to deal with constraint of problems. Introduction of special truncation procedure to handle integer restrictions and selection operator based on Deb constraint rules update the population. The test results show that the I-DE algorithm possess higher success rate and precision than MI-LXPM algorithm and has found solutions which are better than the known optimal solution in five problems.

Optimization of a discrete event systems including (non)linear cost in local states is mainly solved either by heuristic search methods or mathematical programming. In this paper the second approach is further elaborated, including guarantees on both optimal performance and logical correctness. An integrated algorithm is developed utilizing both Operations Research (OR) and Constraint Programming (CP). The majority of integrated approaches have up till now focused on solving linear problems. In this paper we use our integrated algorithm to optimize discrete event systems with nonlinear cost and logical constraints. We present a straightforward method to incorporate OR functionality into an existing CP algorithm such that it can process nonlinear expressions, otherwise too complex for the CP algorithm to handle. Evaluation of the algorithm's performance is done by comparison to that of state of the art Mixed Integer Nonlinear Programming (MINLP) methods. The benchmark shows that our integrated approach finds the optimal solution in roughly the same time as existing MINLP methods. However, when also proof of optimality is required, the integrated algorithm outperforms the best MINLP algorithm by roughly a factor of ten.

This paper describes a new algorithm for solving nonlinear programming problems with inequality constraints. The proposed approach first solves a sequence of quadratic programming sub problems with a trust region framework and to induce global convergence, it establishes a new step acceptance mechanism that is neither a penalty function or a filter. Nonmonotone technique from the unconstraint optimization is used to accelerate the algorithm. Under some reasonable assumptions, the method can be proved to be globally convergent to a KT point. Preliminary numerical experiments are presented that show the potential efficiency of the new approach.

In this paper, we aim to solve nonlinear complementarity problems(NCP), NCP can be reformulated as a nonlinear programming. A search direction is obtained by linearization of the feasible set at a trial point, by making use of this method, a new filter-SSLE Algorithm is presented. It only needs to solve two linear equations at each iteration, fewer computations are required. Global convergence results of the proposed algorithm are established under some suitable conditions.

In this paper a novel Branch and Bound (B&B) algorithm to solve the transmission expansion planning which is a non-convex mixed integer nonlinear programming problem (MINLP) is presented. Based on defining the options of the separating variables and makes a search in breadth, we call this algorithm a B&BML algorithm. The proposed algorithm is implemented in AMPL and an open source Ipopt solver is used to solve the nonlinear programming (NLP) problems of all candidates in the B&B tree. Strategies have been developed to address the problem of non-linearity and non-convexity of the search region. The proposed algorithm is applied to the problem of long-term transmission expansion planning modeled as an MINLP problem. The proposed algorithm has carried out on five commonly used test systems such as Garver 6-Bus, IEEE 24-Bus, 46-Bus South Brazilian test systems, Bolivian 57-Bus, and Colombian 93-Bus. Results show that the proposed methodology not only can find the best known solution but it also yields a large reduction between 24% to 77.6% in the number of NLP problems regarding to the size of the systems.