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%.

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.

Two-parameters quasi-filled function algorithm for nonlinear integer programming

A quasi-filled function for nonlinear integer programming problem is given in this paper. This function contains two parameters which are easily to be chosen. Theoretical properties of the proposed quasi-filled function are investigated. Moreover, we also propose a new solution algorithm using this quasi-filled function to solve nonlinear integer programming problem in this paper. The examples with 2 to 6 variables are tested and computational results indicated the efficiency and reliability of the pro- posed quasi-filled function algorithm.

One-parameter quasi-filled function algorithm for nonlinear integer programming

A definition of the quasi-filled function for nonlinear integer programming problem is given in this paper. A quasi-filled function satisfying our definition is presented. This function contains only one parameter. The properties of the pro- posed quasi-filled function and the method using this quasi-filled function to solve nonlinear integer programming problem are also discussed in this paper. Numerical results indicated the efficiency and reliability of the proposed quasi-filled function algo- rithm.

Efficient Algorithm for K-Barrier Coverage Based on Integer Linear Programming

Barrier coverage of wireless sensor networks is an important issue in the detection of intruders who are attempting to cross a region of interest.However,in certain applications,barrier coverage cannot be satisfied after random deployment.In this paper,we study how mobile sensors can be efficiently relocated to achieve k-barrier coverage.In particular,two problems are studied:relocation of sensors with minimum number of mobile sensors and formation of k-barrier coverage with minimum energy cost.These two problems were formulated as 0–1 integer linear programming(ILP).The formulation is computationally intractable because of integrality and complicated constraints.Therefore,we relax the integrality and complicated constraints of the formulation and construct a special model known as RELAX-RSMN with a totally unimodular constraint coefficient matrix to solve the relaxed 0–1 ILP rapidly through linear programming.Theoretical analysis and simulation were performed to verify the effectiveness of our approach.

Short-Term Scheduling of Combined Cycle Units Using Mixed Integer Linear Programming Solution

Combined cycle plants (CCs) are broadly used all over the world. The inclusion of CCs into the optimal resource scheduling causes difficulties because they can be operated in different operating configuration modes based on the number of combustion and steam turbines. In this paper a model CCs based on a mixed integer linear programming approach to be included into an optimal short term resource optimization problem is presented. The proposed method allows modeling of CCs in different modes of operation taking into account the non convex operating costs for the different combined cycle mode of operation.

A One-parameter Filled Function Method for Nonlinear Integer Programming

This paper gives a new definition of the filled function for nonlinear integer programming problem. A filled function satisfying our definition is presented. This function contains only one parameter. The properties of the proposed filled function and the method using this filled function to solve nonlinear integer programming problem are also discussed. Numerical results indicate the efficiency and reliability of the proposed filled function algorithm.

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.

A Dimensional Reduction Approach Based on Essential Constraints in Linear Programming

This paper presents a new dimension reduction strategy for medium and large-scale linear programming problems. The proposed method uses a subset of the original constraints and combines two algorithms: the weighted average and the cosine simplex algorithm. The first approach identifies binding constraints by using the weighted average of each constraint, whereas the second algorithm is based on the cosine similarity between the vector of the objective function and the constraints. These two approaches are complementary, and when used together, they locate the essential subset of initial constraints required for solving medium and large-scale linear programming problems. After reducing the dimension of the linear programming problem using the subset of the essential constraints, the solution method can be chosen from any suitable method for linear programming. The proposed approach was applied to a set of well-known benchmarks as well as more than 2000 random medium and large-scale linear programming problems. The results are promising, indicating that the new approach contributes to the reduction of both the size of the problems and the total number of iterations required. A tree-based classification model also confirmed the need for combining the two approaches. A detailed numerical example, the general numerical results, and the statistical analysis for the decision tree procedure are presented.

Revision of stratified OWL ontologiesbased on integer linear programming

To revise stratified web ontology language(OWL)ontologies,the kernel revision operator is extended by defining novel conflict stratification and the incision function based on integer linear programming(ILP).The ILP-based model considers an optimization problem of minimizing a linear objective function which is suitable for selecting the minimal number of axioms to remove when revising ontologies.Based on the incision function,a revision algorithm is proposed to apply ILP to all minimal incoherence-preserving subsets(MIPS).Although this algorithm can often find a minimal number of axioms to remove,it is very time-consuming to compute MIPS.Thus,an adapted revision algorithm to deal with unsatisfiable concepts individually is also given.Experimental results reveal that the proposed ILP-based revision algorithm is much more efficient than the commonly used algorithm based on the hitting set tree.In addition,the adapted algorithm can achieve higher efficiency,while it may delete more axioms.

A mixed integer linear programming approach for municipal solid waste management

ＡｍｉｘｅｄｉｎｔｅｇｅｒｌｉｎｅａｒｐｒｏｇｒａｍｍｉｎｇａｐｐｒｏａｃｈｆｏｒｍｕｎｉｃｉｐａｌｓｏｌｉｄｗａｓｔｅｍａｎａｇｅｍｅｎｔＧｏｒｄｏｎＧｕｏＨｅＨｕａｎｇＥｎｖｉｒｏｎｍｅｎｔａｌＳｙｓｔｅｍｓＥｎｇｉｎｅｅｒｉｎｇ，Ｕｎｉｖｅｒ...

Application of Optimization Principle in Landmark University Project Selection under Multi-Period Capital Rationing Using Linear and Integer Programming

The current structure of Landmark University (LU) was induced by raising a generation of solution providers through a qualitative and life-applicable training system that focuses on values and creative knowledge by making it more responsive and relevant to the modern-day demands of demonstration, industrialization and development. The challenge facing Landmark University is the question of which of its numerous projects they should invest to give maximum output with minimum input. In this paper, we maximize the Net Present Value (NPV) and maintain the net discount cash overflow of each project per period as contained and extracted as the secondary data of cash inflows of the Landmark University (LU) monthly financial statement and annual reports from 2012 to 2017 of which the documents have been regrouped as small and large scale projects as many enterprises make more use of the trial-and-error method and as such firms have been finding it difficult in allocating scarce resources in a manner that will ensure profit maximization and/or cost minimization with a simple and accurate decision making by the company through an optimization principle in selecting LU project under multi-period capital rationing using linear programming (LP) and integer programming (IP). The annual net cash flow which is the difference between the cash inflows and cash outflows during each period for the project was estimated and recorded. The discount factors were estimated at cost of capital of 10% for each cash flow per period with the corresponding NPV at 10% which revealed that the optimal decision achieves maximum returns of $110 × 102 and this assisted the project manager to select a large number of the variable projects that can maximize the profit which is far better than relying on an ad-hoc judgmental approach to project investment that could have cost 160 × 102 for the same project. Sensitivity analysis on the project parameters are also carried out to test the extent to which project selection is sensitive to changes in the parameters of the system revealed that a little reduction and or addition of reduced cost by certain amount or percentages to its corresponding coefficient in the objective function effect no changes in the shadow prices with solution values for variables (x1), (x4), (x5) and the optimal objective function.

Reduction and Analysis of a Max-Plus Linear System to a Constraint Satisfaction Problem for Mixed Integer Programming

This research develops a solution method for project scheduling represented by a max-plus-linear (MPL) form. Max-plus-linear representation is an approach to model and analyze a class of discrete-event systems, in which the behavior of a target system is represented by linear equations in max-plus algebra. Several types of MPL equations can be reduced to a constraint satisfaction problem (CSP) for mixed integer programming. The resulting formulation is flexible and easy-to-use for project scheduling;for example, we can obtain the earliest output times, latest task-starting times, and latest input times using an MPL form. We also develop a key method for identifying critical tasks under the framework of CSP. The developed methods are validated through a numerical example.

Multi-Document Summarization Model Based on Integer Linear Programming

This paper proposes an extractive generic text summarization model that generates summaries by selecting sentences according to their scores. Sentence scores are calculated using their extensive coverage of the main content of the text, and summaries are created by extracting the highest scored sentences from the original document. The model formalized as a multiobjective integer programming problem. An advantage of this model is that it can cover the main content of source (s) and provide less redundancy in the generated sum- maries. To extract sentences which form a summary with an extensive coverage of the main content of the text and less redundancy, have been used the similarity of sentences to the original document and the similarity between sentences. Performance evaluation is conducted by comparing summarization outputs with manual summaries of DUC2004 dataset. Experiments showed that the proposed approach outperforms the related methods.

An Exact Penalty Approach for Mixed Integer Nonlinear Programming Problems

We propose an exact penalty approach for solving mixed integer nonlinear programming (MINLP) problems by converting a general MINLP problem to a finite sequence of nonlinear programming (NLP) problems with only continuous variables. We express conditions of exactness for MINLP problems and show how the exact penalty approach can be extended to constrained problems.

Combining Geographic Information Systems for Transportation and Mixed Integer Linear Programming in Facility Location-Allocation Problems

In this study, we aimed to assess the solution quality for location-allocation problems from facilities generated by the software TransCAD®?, a Geographic Information System for Transportation (GIS-T). Such facilities were obtained after using two routines together: Facility Location and Transportation Problem, when compared with optimal solutions from exact mathematical models, based on Mixed Integer Linear Programming (MILP), developed externally for the GIS. The models were applied to three simulations: the first one proposes opening factories and customer allocation in the state of Sao Paulo, Brazil;the second involves a wholesaler and a study of location and allocation of distribution centres for retail customers;and the third one involves the location of day-care centers and allocation of demand (0 - 3 years old children). The results showed that when considering facility capacity, the MILP optimising model presents results up to 37% better than the GIS and proposes different locations to open new facilities.

A non-monotone Phase-1 method in linear programming

To gain superior computational efficiency, it might be necessary to change the underlying philosophy of the simplex method. In this paper, we propose a Phase-1 method along this line. We relax not only the conventional condition that some function value increases monotonically, but also the condition that all feasible variables remain feasible after basis change in Phase-1. That is, taking a purely combinatorial approach to achieving feasibility. This enables us to get rid of ratio test in pivoting, reducing computational cost per iteration to a large extent. Numerical results on a group of problems are encouraging.

A Modified Algorithm for Nonliear Integer Programming

Based on the analysis to the random sear ch algorithm of LUUS, a modified random directed integer search algorithm (MRDI SA) is given for first time. And a practical example is given to show that the adva ntage of this kind of algorithm is the reliability can’t be infuenced by the ini tial value X (0) and the start search domain R (0) . Besides, i t can be applied to solve the higher dimensional constrained nonlinear integer p rogramming problem.

Linear Programming建模研讨

研究用图解法、simplex method和匈牙利法建立Linear Programming的数学模型并求得了最优解.结果表明:对仅有两个变量的Linear Programming,既可通过图解法求得最优解;也可用单纯形表简便地求得最优解;而对任务和人数不等的assignment problem,则用匈牙利法求最优解.