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.

Scheduling Step-Deteriorating Jobs on Parallel Machines by Mixed Integer Programming

Production scheduling has a major impact on the productivity of the manufacturing process. Recently, scheduling problems with deteriorating jobs have attracted increasing attentions from researchers. In many practical situations,it is found that some jobs fail to be processed prior to the pre-specified thresholds,and they often consume extra deteriorating time for successful accomplishment. Their processing times can be characterized by a step-wise function. Such kinds of jobs are called step-deteriorating jobs. In this paper,parallel machine scheduling problem with stepdeteriorating jobs( PMSD) is considered. Due to its intractability,four different mixed integer programming( MIP) models are formulated for solving the problem under consideration. The study aims to investigate the performance of these models and find promising optimization formulation to solve the largest possible problem instances. The proposed four models are solved by commercial software CPLEX. Moreover,the near-optimal solutions can be obtained by black-box local-search solver LocalS olver with the fourth one. The computational results show that the efficiencies of different MIP models depend on the distribution intervals of deteriorating thresholds, and the performance of LocalS olver is clearly better than that of CPLEX in terms of the quality of the solutions and the computational time.

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

General Exact Penalty Functions in Integer Programming

In this paper, the general exact penalty functions in integer programming were studied. The conditions which ensure the exact penalty property for the general penalty function with one penalty parameter were given and a general penalty function with two parameters was proposed.

Optimal set integer programming algorithm for multiple maneuvering targets tracking in clutter

The aim of this paper is to solve the problems of multitarget tracking in clutter. Firstly, the data association of measurement-to-target is formulated as an integer programming problem. Through using the linear programming （LP） based branchand-bound method and adjusting the constraint conditions, an optimal set integer programming （OSIP） algorithm is then proposed for tracking multiple non-maneuvering targets in clutter. For the case of maneuvering targets, this paper introduces the OSIP algorithm into the filtering step of the interacting multiple model （IMM） algorithm resulting in the IMM based on OSIP algorithm. Extensive Monte Carlo simulations show that the presented algorithms can obtain superior estimations even in the case of high density noises.

An Explicit Integer Programming Model of the Minimal Spanning Tree Problem for Digraphs with Asymmetric Weights

As far as the minimal spanning tree problem for the digraph with asymmetric weightsis concerned, an explicit integer programming model is proposed, which could be solved successfullyusing the integer programming packages such as LINDO, and furthermore this model is extendedinto the stochastic version, that is, the minimal spanning tree problem for the digraph with theweights is not constant but random variables. Several algorithms are also developed to solve themodels. Finally, a numerical demonstration is given.

An Integer Programming Model for the KenKen Problem

In this paper we consider modeling techniques for the mathematical puzzle KenKen. It is an interesting puzzle from modeling point of view since it has different kind of mathematical restrictions that are not trivial to express as linear constraints. We give an integer program for solving KenKen and and its implementation on modeling language AMPL. Our integer program uses an innovative way for converting product restrictions into linear constraints. It can be also used for teaching various integer programming techniques in an Operations Research course.

Stochastic level-value approximation for quadratic integer convex programming

We propose a stochastic level value approximation method for a quadratic integer convex minimizing problem in this paper. This method applies an importance sampling technique, and make use of the cross-entropy method to update the sample density functions. We also prove the asymptotic convergence of this algorithm, and report some numerical results to illuminate its effectiveness.

Solving Integer Programming by Evolutionary Soft Agent

Many practical problems in commerce and industry involve finding the best way to allocate scarce resources a-mong competing activities. This paper focuses on the problem of integer programming, and describes an evolutionary soft a-gent model to solve it. In proposed model, agent is composed of three components: goal, environment and behavior. Experimental shows the model has the characters of parallel computing and goal driving.

A mixed integer linear programming approach for municipal solid waste management

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

Dimensionality reduction model based on integer planning for the analysis of key indicators affecting life expectancy

Purpose:Exploring a dimensionality reduction model that can adeptly eliminate outliers and select the appropriate number of clusters is of profound theoretical and practical importance.Additionally,the interpretability of these models presents a persistent challenge.Design/methodology/approach:This paper proposes two innovative dimensionality reduction models based on integer programming(DRMBIP).These models assess compactness through the correlation of each indicator with its class center,while separation is evaluated by the correlation between different class centers.In contrast to DRMBIP-p,the DRMBIP-v considers the threshold parameter as a variable aiming to optimally balances both compactness and separation.Findings:This study,getting data from the Global Health Observatory(GHO),investigates 141 indicators that influence life expectancy.The findings reveal that DRMBIP-p effectively reduces the dimensionality of data,ensuring compactness.It also maintains compatibility with other models.Additionally,DRMBIP-v finds the optimal result,showing exceptional separation.Visualization of the results reveals that all classes have a high compactness.Research limitations:The DRMBIP-p requires the input of the correlation threshold parameter,which plays a pivotal role in the effectiveness of the final dimensionality reduction results.In the DRMBIP-v,modifying the threshold parameter to variable potentially emphasizes either separation or compactness.This necessitates an artificial adjustment to the overflow component within the objective function.Practical implications:The DRMBIP presented in this paper is adept at uncovering the primary geometric structures within high-dimensional indicators.Validated by life expectancy data,this paper demonstrates potential to assist data miners with the reduction of data dimensions.Originality/value:To our knowledge,this is the first time that integer programming has been used to build a dimensionality reduction model with indicator filtering.It not only has applications in life expectancy,but also has obvious advantages in data mining work that requires precise class centers.

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

Global optimality conditions for quadratic 0-1 programming with inequality constraints

Quadratic 0-1 problems with linear inequality constraints are briefly considered in this paper.Global optimality conditions for these problems,including a necessary condition and some sufficient conditions,are presented.The necessary condition is expressed without dual variables.The relations between the global optimal solutions of nonconvex quadratic 0-1 problems and the associated relaxed convex problems are also studied.

A Hybrid Dynamic Programming Method for Concave Resource Allocation Problems

Concave resource allocation problem is an integer programming problem of minimizing a nonincreasing concave function subject to a convex nondecreasing constraint and bounded integer variables. This class of problems are encountered in optimization models involving economies of scale. In this paper, a new hybrid dynamic programming method was proposed for solving concave resource allocation problems. A convex underestimating function was used to approximate the objective function and the resulting convex subproblem was solved with dynamic programming technique after transforming it into a 0-1 linear knapsack problem. To ensure the convergence, monotonicity and domain cut technique was employed to remove certain integer boxes and partition the revised domain into a union of integer boxes. Computational results were given to show the efficiency of the algorithm.

Stochastic Programming For Order Allocation And Production Planning

Stochastic demand is an important factor that heavily affects production planning.It influences activities such as purchasing,manufacturing,and selling,and quick adaption is required.In production planning,for reasons such as reducing costs and obtaining supplier discounts,many decisions must be made in the initial stage when demand has not been realized.The effects of non-optimal decisions will propagate to later stages,which can lead to losses due to overstocks or out-of-stocks.To find the optimal solutions for the initial and later stage regarding demand realization,this study proposes a stochastic two-stage linear program-ming model for a multi-supplier,multi-material,and multi-product purchasing and production planning process.The objective function is the expected total cost after two stages,and the results include detailed plans for purchasing and production in each demand scenario.Small-scale problems are solved through a deterministic equivalent transformation technique.To solve the problems in the large scale,an algorithm combining metaheuristic and sample average approximation is suggested.This algorithm can be implemented in parallel to utilize the power of the solver.The algorithm based on the observation that if the remaining quantity of materials and number of units of products at the end of the initial stage are given,then the problems of the first and second stages can be decomposed.

Convexity Properties for a Function of Two Integer Variables

Sufficient conditions are given for any local minimum of a function of two integer variables to be a global minimum. An example is given to show that a function of two integer variables need not be discrete convex for this condition to hold.

Closed-loop scheduling optimization strategy based on particle swarm optimization with niche technology and soft sensor method of attributes-applied to gasoline blending process

Gasoline blending scheduling optimization can bring significant economic and efficient benefits to refineries.However,the optimization model is complex and difficult to build,which is a typical mixed integer nonlinear programming(MINLP)problem.Considering the large scale of the MINLP model,in order to improve the efficiency of the solution,the mixed integer linear programming-nonlinear programming(MILP-NLP)strategy is used to solve the problem.This paper uses the linear blending rules plus the blending effect correction to build the gasoline blending model,and a relaxed MILP model is constructed on this basis.The particle swarm optimization algorithm with niche technology(NPSO)is proposed to optimize the solution,and the high-precision soft-sensor method is used to calculate the deviation of gasoline attributes,the blending effect is dynamically corrected to ensure the accuracy of the blending effect and optimization results,thus forming a prediction-verification-reprediction closed-loop scheduling optimization strategy suitable for engineering applications.The optimization result of the MILP model provides a good initial point.By fixing the integer variables to the MILPoptimal value,the approximate MINLP optimal solution can be obtained through a NLP solution.The above solution strategy has been successfully applied to the actual gasoline production case of a refinery(3.5 million tons per year),and the results show that the strategy is effective and feasible.The optimization results based on the closed-loop scheduling optimization strategy have higher reliability.Compared with the standard particle swarm optimization algorithm,NPSO algorithm improves the optimization ability and efficiency to a certain extent,effectively reduces the blending cost while ensuring the convergence speed.

Multi-Patch Black-White Topology Optimization in Isogeometric Analysis

Topological optimization plays a guiding role in the conceptual design process.This paper conducts research on structural topology optimization algorithm within the framework of isogeometric analysis.For multi-component structures,the Nitsche’smethod is used to glue differentmeshes to performisogeometricmulti-patch analysis.The discrete variable topology optimization algorithm based on integer programming is adopted in order to obtain clear boundaries for topology optimization.The sensitivity filtering method based on the Helmholtz equation is employed for averaging of curved elements’sensitivities.In addition,a simple averaging method along coupling interfaces is proposed in order to ensure the material distribution across coupling areas is reasonably smooth.Finally,the performance of the algorithm is demonstrated by numerical examples,and the effectiveness of the algorithm is verified by comparing it with the results obtained by single-patch and ABAQUS cases.

A Mixed-Integer Programming Formulation for a Simplified Model of the Double Row Layout Problem

The double row layout problem(DRLP)is to assign facilities on two rows in parallel so that the total cost of material handling among facilities is minimized.Since it is vital to save cost and enhance productivity,the DRLP plays an important role in many application fields.Nevertheless,it is very hard to handle the DRLP because of its complex model.In this paper,we consider a new simplified model for the DRLP(SM-DRLP)and provide a mixed integer programming(MIP)formulation for it.The continuous decision variables of the DRLP are divided into two parts:start points of double rows and adjustable clearances between adjacent facilities.The former one is considered in the new simplified model for the DRLP with the purpose of maintaining solution quality,while the latter one is not taken into account with the purpose of reducing computational time.To evaluate its performance,our SM-DRLP is compared with the model of a general DRLP and the model of another simplified DRLP.The experimental results show the efficiency of our proposed model.