Solution for integer linear bilevel programming problems using orthogonal genetic algorithm

An integer linear bilevel programming problem is firstly transformed into a binary linear bilevel programming problem, and then converted into a single-level binary implicit programming. An orthogonal genetic algorithm is developed for solving the binary linear implicit programming problem based on the orthogonal design. The orthogonal design with the factor analysis, an experimental design method is applied to the genetic algorithm to make the algorithm more robust, statistical y sound and quickly convergent. A crossover operator formed by the orthogonal array and the factor analysis is presented. First, this crossover operator can generate a smal but representative sample of points as offspring. After al of the better genes of these offspring are selected, a best combination among these offspring is then generated. The simulation results show the effectiveness of the proposed algorithm.

An Exact Virtual Network Embedding Algorithm Based on Integer Linear Programming for Virtual Network Request with Location Constraint

Network virtualization is known as a promising technology to tackle the ossification of current Internet and will play an important role in the future network area. Virtual network embedding(VNE) is a key issue in network virtualization. VNE is NP-hard and former VNE algorithms are mostly heuristic in the literature.VNE exact algorithms have been developed in recent years. However, the constraints of exact VNE are only node capacity and link bandwidth.Based on these, this paper presents an exact VNE algorithm, ILP-LC, which is based on Integer Linear Programming(ILP), for embedding virtual network request with location constraints. This novel algorithm is aiming at mapping virtual network request(VNR) successfully as many as possible and consuming less substrate resources.The topology of each VNR is randomly generated by Waxman model. Simulation results show that the proposed ILP-LC algorithm outperforms the typical heuristic algorithms in terms of the VNR acceptance ratio, at least 15%.

Primal-Dual Interior-Point Algorithms with Dynamic Step-Size Based on Kernel Functions for Linear Programming

In this paper, primal-dual interior-point algorithm with dynamic step size is implemented for linear programming （LP） problems. The algorithms are based on a few kernel functions, including both serf-regular functions and non-serf-regular ones. The dynamic step size is compared with fixed step size for the algorithms in inner iteration of Newton step. Numerical tests show that the algorithms with dynaraic step size are more efficient than those with fixed step size.

Smoothing Newton Algorithm for Linear Programming over Symmetric Cones

By using the theory of Euclidean Jordan algebras,based on a new class of smoothing functions,the QiSun-Zhou's smoothing Newton algorithm is extended to solve linear programming over symmetric cones(SCLP).The algorithm is globally convergent under suitable assumptions.

A Primal-Dual Simplex Algorithm for Solving Linear Programming Problems with Symmetric Trapezoidal Fuzzy Numbers

Two existing methods for solving a class of fuzzy linear programming (FLP) problems involving symmetric trapezoidal fuzzy numbers without converting them to crisp linear programming problems are the fuzzy primal simplex method proposed by Ganesan and Veeramani [1] and the fuzzy dual simplex method proposed by Ebrahimnejad and Nasseri [2]. The former method is not applicable when a primal basic feasible solution is not easily at hand and the later method needs to an initial dual basic feasible solution. In this paper, we develop a novel approach namely the primal-dual simplex algorithm to overcome mentioned shortcomings. A numerical example is given to illustrate the proposed approach.

A new heuristic algorithm for general integer linear programming problems

A new heuristic algorithm is proposed for solving general integer linear programming problems. In the algorithm, the objective function hyperplane is used as a cutting plane, and then by introducing a special set of assistant sets, an efficient heuristic search for the solution to the integer linear program is carried out in the sets on the objective function hyperplane. A simple numerical example shows that the algorithm is efficient for some problems, and therefore, of practical interest.

An Improved Affine-Scaling Interior Point Algorithm for Linear Programming

In this paper, an Improved Affine-Scaling Interior Point Algorithm for Linear Programming has been proposed. Computational results of selected practical problems affirming the proposed algorithm have been provided. The proposed algorithm is accurate, faster and therefore reduces the number of iterations required to obtain an optimal solution of a given Linear Programming problem as compared to the already existing Affine-Scaling Interior Point Algorithm. The algorithm can be very useful for development of faster software packages for solving linear programming problems using the interior-point methods.

A Glorious Literature on Linear Goal Programming Algorithms

In the last several years, there has been a marked improvement in the development of new algorithms for solving Linear Goal programming (LGP). This paper presents a survey of current methods for LGP.

Discrete differential evolution algorithm for integer linear bilevel programming problems

A discrete differential evolution algorithm combined with the branch and bound method is developed to solve the integer linear bilevel programming problems, in which both upper level and lower level variables are forced to be integer. An integer coding for upper level variables is adopted, and then a discrete differential evolution algorithm with an improved feasibility-based comparison is developed to directly explore the integer solution at the upper level. For a given upper level integer variable, the lower level integer programming problem is solved by the existing branch and bound algorithm to obtain the optimal integer solution at the lower level. In the same framework of the algorithm, two other constraint handling methods, i.e. the penalty function method and the feasibility-based comparison method are also tested. The experimental results demonstrate that the discrete differential evolution algorithm with different constraint handling methods is effective in finding the global optimal integer solutions, but the improved constraint handling method performs better than two compared constraint handling methods.

An adaptive genetic algorithm for solving bilevel linear programming problem

Bilevel linear programming, which consists of the objective functions of the upper level and lower level, is a useful tool for modeling decentralized decision problems. Various methods are proposed for solving this problem. Of all the algorithms, the ge- netic algorithm is an alternative to conventional approaches to find the solution of the bilevel linear programming. In this paper, we describe an adaptive genetic algorithm for solving the bilevel linear programming problem to overcome the difficulty of determining the probabilities of crossover and mutation. In addition, some techniques are adopted not only to deal with the difficulty that most of the chromosomes maybe infeasible in solving constrained optimization problem with genetic algorithm but also to improve the efficiency of the algorithm. The performance of this proposed algorithm is illustrated by the examples from references.

A Primal-Dual Infeasible-Interior-Point Algorithm for Multiple Objective Linear Programming Problems

A primal-dual infeasible interior point algorithm for multiple objective linear programming (MOLP) problems was presented. In contrast to the current MOLP algorithm. moving through the interior of polytope but not confining the iterates within the feasible region in our proposed algorithm result in a solution approach that is quite different and less sensitive to problem size, so providing the potential to dramatically improve the practical computation effectiveness.

Polynomial Complexity Bounds of Mehrotra-type Predictor-corrector Algorithms for Linear Programming over Symmetric Cones

We establish polynomial complexity corrector algorithms for linear programming over bounds of the Mehrotra-type predictor- symmetric cones. We first slightly modify the maximum step size in the predictor step of the safeguard based Mehrotra-type algorithm for linear programming, that was proposed by Salahi et al. Then, using the machinery of Euclidean Jordan algebras, we extend the modified algorithm to symmetric cones. Based on the Nesterov-Todd direction, we obtain O（r log ε1） iteration complexity bound of this algorithm, where r is the rank of the Jordan algebras and ε is the required precision. We also present a new variant of Mehrotra-type algorithm using a new adaptive updating scheme of centering parameter and show that this algorithm enjoys the same order of complexity bound as the safeguard algorithm. We illustrate the numerical behaviour of the methods on some small examples.

An Innovative Genetic Algorithms-Based Inexact Non-Linear Programming Problem Solving Method

In this paper, an innovative Genetic Algorithms (GA)-based inexact non-linear programming (GAINLP) problem solving approach has been proposed for solving non-linear programming optimization problems with inexact information (inexact non-linear operation programming). GAINLP was developed based on a GA-based inexact quadratic solving method. The Genetic Algorithm Solver of the Global Optimization Toolbox (GASGOT) developed by MATLABTM was adopted as the implementation environment of this study. GAINLP was applied to a municipality solid waste management case. The results from different scenarios indicated that the proposed GA-based heuristic optimization approach was able to generate a solution for a complicated nonlinear problem, which also involved uncertainty.

Improved Balas and Mazzola Linearization for Quadratic 0-1 Programs with Application in a New CuttingPlane Algorithm

Balas and Mazzola linearization (BML) is widely used in devising cutting plane algorithms for quadratic 0-1 programs. In this article, we improve BML by first strengthening the primal formulation of BML and then considering the dual formulation. Additionally, a new cutting plane algorithm is proposed.

A Complex Algorithm for Solving a Kind of Stochastic Programming

Considering that the probability distribution of random variables in stochastic programming usually has incomplete information due to a perfect sample data in many real applications, this paper discusses a class of two-stage stochastic programming problems modeling with maximum minimum expectation compensation criterion (MaxEMin) under the probability distribution having linear partial information (LPI). In view of the nondifferentiability of this kind of stochastic programming modeling, an improved complex algorithm is designed and analyzed. This algorithm can effectively solve the nondifferentiable stochastic programming problem under LPI through the variable polyhedron iteration. The calculation and discussion of numerical examples show the effectiveness of the proposed algorithm.

Solving the Binary Linear Programming Model in Polynomial Time

The paper presents a technique for solving the binary linear programming model in polynomial time. The general binary linear programming problem is transformed into a convex quadratic programming problem. The convex quadratic programming problem is then solved by interior point algorithms. This settles one of the open problems of whether P = NP or not. The worst case complexity of interior point algorithms for the convex quadratic problem is polynomial. It can also be shown that every liner integer problem can be converted into binary linear problem.

Application of Linear Programming for Optimal Investments in Software Company

We apply the simplex algorithm which is a branch of linear programming to efficiently determine the allocation of resources required to operate a company in the software development field. The main aim of applying this technique is to maximize the profit of a company under certain limitations. This can be done using the trial-and-error approach. However, this tedious process can be replaced by user-level tools such as Excel which are based on linear programming that will give more accurate results. Small software companies cannot afford to hire a high number of senior programmers to produce the required level of quality and to keep up with the demand for adding new features. On the other hand, lowering the quality of the product will reduce the number of customers and decrease profit. Another aspect is maximizing the utilization of hosting servers which are required for providing the services to customers since the cost of buying servers and maintaining them is extremely high. The simplex algorithm in linear programming will take the specified constraints into account to compute the optimal allocation of the available resources to maximize profit and limit the cost. This paper will present a model that uses the simplex algorithm with a set of constraints to determine how many projects of each type a company should take in one period of time.

An Evolutionary Firefly Algorithm, Goal Programming Optimization Approach for Setting the Osmotic Dehydration Parameters of Papaya

An evolutionary nature-inspired Firefly Algorithm (FA) is employed to set the optimal osmotic dehydration parameters in a case study of papaya. In the case, the functional form of the dehydration model is established via a response surface technique with the resulting optimization formulation being a non-linear goal programming model. For optimization, a computationally efficient, FA-driven method is employed and the resulting solution is shown to be superior to those from previous approaches for determining the osmotic process parameters. The final component of this study provides a computational experimentation performed on the FA to illustrate the relative sensitivity of this evolutionary metaheuristic approach over a range of the two key parameters that most influence its running time-the number of iterations and the number of fireflies. This sensitivity analysis revealed that for intermediate-to-high values of either of these two key parameters, the FA would always determine overall optimal solutions, while lower values of either parameter would generate greater variability in solution quality. Since the running time complexity of the FA is polynomial in the number of fireflies but linear in the number of iterations, this experimentation shows that it is more computationally practical to run the FA using a “reasonably small” number of fireflies together with a relatively larger number of iterations than the converse.

An algorithm for earthwork allocation considering non-linear factors

For solving the optimization model of earthwork allocation considering non-linear factors,a hybrid algorithm combined with the ant algorithm(AA)and particle swarm optimization(PSO)is proposed in this paper.Then the proposed method and the LP method are used respectively in solving a linear allocation model of a high rockfill dam project.Results obtained by these two methods are compared each other.It can be concluded that the solution got by the proposed method is extremely approximate to the analytic solution of LP method.The superiority of the proposed method over the LP method in solving a non-linear allocation model is illustrated by a non-linear case.Moreover,further researches on improvement of the algorithm and the allocation model are addressed.

An Alternative Approach for Solving Bi-Level Programming Problems

An algorithm is proposed in this paper for solving two-dimensional bi-level linear programming problems without making a graph. Based on the classification of constraints, algorithm removes all redundant constraints, which eliminate the possibility of cycling and the solution of the problem is reached in a finite number of steps. Example to illustrate the method is also included in the paper.