Hybrid particle swarm optimization with chaotic search for solving integer and mixed integer programming problems

A novel chaotic search method is proposed,and a hybrid algorithm combining particle swarm optimization(PSO) with this new method,called CLSPSO,is put forward to solve 14 integer and mixed integer programming problems.The performances of CLSPSO are compared with those of other five hybrid algorithms combining PSO with chaotic search methods.Experimental results indicate that in terms of robustness and final convergence speed,CLSPSO is better than other five algorithms in solving many of these problems.Furthermore,CLSPSO exhibits good performance in solving two high-dimensional problems,and it finds better solutions than the known ones.A performance index(PI) is introduced to fairly compare the above six algorithms,and the obtained values of(PI) in three cases demonstrate that CLSPSO is superior to all the other five algorithms under the same conditions.

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.

A mixed integer linear programming approach for municipal solid waste management

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

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.

Detection of gross errors using mixed integer optimization approach in process industry

A novel mixed integer linear programming (NMILP) model for detection of gross errors is presented in this paper. Yamamura et al.(1988) designed a model for detection of gross errors and data reconciliation based on Akaike information cri- terion (AIC). But much computational cost is needed due to its combinational nature. A mixed integer linear programming (MILP) approach was performed to reduce the computational cost and enhance the robustness. But it loses the super performance of maximum likelihood estimation. To reduce the computational cost and have the merit of maximum likelihood estimation, the simultaneous data reconciliation method in an MILP framework is decomposed and replaced by an NMILP subproblem and a quadratic programming (QP) or a least squares estimation (LSE) subproblem. Simulation result of an industrial case shows the high efficiency of the method.

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.

Hierarchical On-line Scheduling of Multiproduct Batch Plants with a Combined Approach of Mathematical Programming and Genetic Algorithm

In this contribution we present an online scheduling algorithm for a real world multiproduct batch plant. The overall mixed integer nonlinear programming (MINLP) problem is hierarchically structured into a mixed integer linear programming (MILP) problem first and then a reduced dimensional MINLP problem, which are optimized by mathematical programming (MP) and genetic algorithm (GA) respectively. The basis idea relies on combining MP with GA to exploit their complementary capacity. The key features of the hierarchical model are explained and illustrated with some real world cases from the multiproduct batch plants.

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.

A Green Mixed Integer Linear Programming Model for Optimization of Byproduct Gases in Iron and Steel Industry

Byproduct gas is an important secondary energy in iron and steel industry, and its optimization is vital to cost reduction. With the development of iron and steel industry to be more eco-friendly, it is necessary to construct an integrated optimized system, taking economics, energy consumption and environment into consideration. Therefore, the environmental cost caused by pollutants discharge should be factored in total cost when optimizing byproduct gas distribution. A green mixed integer linear programming （MILP） model for the optimization of byproduct gases was established to reduce total cost, including both operation cost and environmental cost. The operation cost included penalty for gas deviation, costs of fuel and water consumption, holder booster trip penalty, and so forth; while the environmental cost consisted of penalties for both direct and indirect pollutants discharge. Case study showed that the proposed model brought an optimum solution and 2.2% of the total cost could be reduced compared with previous one.

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.

MLD-MPC Approach for Three-Tank Hybrid Benchmark Problem

The present paper aims at validating a Model Predictive Control(MPC),based on the Mixed Logical Dynamical(MLD)model,for Hybrid Dynamic Systems(HDSs)that explicitly involve continuous dynamics and discrete events.The proposed benchmark system is a three-tank process,which is a typical case study of HDSs.The MLD-MPC controller is applied to the level control of the considered tank system.The study is initially focused on the MLD approach that allows consideration of the interacting continuous dynamics with discrete events and includes the operating constraints.This feature of MLD modeling is very advantageous when an MPC controller synthesis for the HDSs is designed.Once the MLD model of the system is well-posed,then the MPC law synthesis can be developed based on the Mixed Integer Programming(MIP)optimization problem.For solving this MIP problem,a Branch and Bound(B&B)algorithm is proposed to determine the optimal control inputs.Then,a comparative study is carried out to illustrate the effectiveness of the proposed hybrid controller for the HDSs compared to the standard MPC approach.Performances results show that the MLD-MPC approach outperforms the standardMPCone that doesn’t consider the hybrid aspect of the system.The paper also shows a behavioral test of the MLDMPC controller against disturbances deemed as liquid leaks from the system.The results are very satisfactory and show that the tracking error is minimal less than 0.1%in nominal conditions and less than 0.6%in the presence of disturbances.Such results confirm the success of the MLD-MPC approach for the control of the HDSs.

Passive shimming based on mixed integer programming for MRI magnet

A mathematical model based on mixed integer programming is presented in this paper for the passive shimming of magnet in magnetic resonance imaging(MRI) scanner.In this model,the magnetic field inhomogeneity tolerance and the central value of the magnetic field after shimming are programmed together with the volume of each shim piece as the variables,which increases the degree of freedom and guarantees a better solution.The magnetic field inhomogeneity tolerance after shimming with a weighting coefficient and the total volume of shim pieces are both contained in the objective function of the model.By assigning different values to the weighting coefficient in the objective function,different shimming plans with different emphases can be obtained.A simulation test has been carried out on a small permanent magnet with frame structure.Several solutions are given and compared in this paper,which indicates that a practical shimming plan can be obtained quickly by solving this model.

Deleting Outliers in Robust Regression with Mixed Integer Programming

In robust regression we often have to decide how many are the unusualobservations, which should be removed from the sample in order to obtain better fitting for the restof the observations. Generally, we use the basic principle of LTS, which is to fit the majority ofthe data, identifying as outliers those points that cause the biggest damage to the robust fit.However, in the LTS regression method the choice of default values for high break down-point affectsseriously the efficiency of the estimator. In the proposed approach we introduce penalty cost fordiscarding an outlier, consequently, the best fit for the majority of the data is obtained bydiscarding only catastrophic observations. This penalty cost is based on robust design weights andhigh break down-point residual scale taken from the LTS estimator. The robust estimation is obtainedby solving a convex quadratic mixed integer programming problem, where in the objective functionthe sum of the squared residuals and penalties for discarding observations is minimized. Theproposed mathematical programming formula is suitable for small-sample data. Moreover, we conduct asimulation study to compare other robust estimators with our approach in terms of their efficiencyand robustness.

Reserve Constrained Dynamic Economic Dispatch with Valve-point Effect:A Two-stage Mixed Integer Linear Programming Approach

This paper proposes a deterministic two-stage mixed integer linear programming(TSMILP)approach to solve the reserve constrained dynamic economic dispatch(DED)problem considering valve-point effect(VPE).In stage one,the nonsmooth cost function and the transmission loss are piecewise linearized and consequently the DED problem is formulated as a mixed integer linear programming(MILP)problem,which can be solved by commercial solvers.In stage two,based on the solution obtained in stage one,a range compression technique is proposed to make a further exploitation in the subspace of the whole solution domain.Due to the linear approximation of the transmission loss,the solution obtained in stage two dose not strictly satisfies the power balance constraint.Hence,a forward procedure is employed to eliminate the error.The simulation results on four test systems show that TSMILP makes satisfactory performances,in comparison with the existing methods.

Randomized MILP framework for Securing Virtual Machines from Malware Attacks

Cloud computing involves remote server deployments with public net-work infrastructures that allow clients to access computational resources.Virtual Machines(VMs)are supplied on requests and launched without interactions from service providers.Intruders can target these servers and establish malicious con-nections on VMs for carrying out attacks on other clustered VMs.The existing system has issues with execution time and false-positive rates.Hence,the overall system performance is degraded considerably.The proposed approach is designed to eliminate Cross-VM side attacks and VM escape and hide the server’s position so that the opponent cannot track the target server beyond a certain point.Every request is passed from source to destination via one broadcast domain to confuse the opponent and avoid them from tracking the server’s position.Allocation of SECURITY Resources accepts a safety game in a simple format as input andfinds the best coverage vector for the opponent using a Stackelberg Equilibrium(SSE)technique.A Mixed Integer Linear Programming(MILP)framework is used in the algorithm.The VM challenge is reduced by afirewall-based controlling mechanism combining behavior-based detection and signature-based virus detection.The pro-posed method is focused on detecting malware attacks effectively and providing better security for the VMs.Finally,the experimental results indicate that the pro-posed security method is efficient.It consumes minimum execution time,better false positive rate,accuracy,and memory usage than the conventional approach.

A mixed-integer linear programming approach for robust state estimation

In this paper,a mixed integer linear programming(MILP)formulation for robust state estimation(RSE)is proposed.By using the exactly linearized measurement equations instead of the original nonlinear ones,the existingmixed integer nonlinear programming formulation for RSE is converted to a MILP problem.The proposed approach not only guarantees to find the global optimum,but also does not have convergence problems.Simulation results on a rudimentary 3-bus system and several IEEE standard test systems fully illustrate that the proposed methodology is effective with high efficiency.

AN EXTRACTION ALGORITHM FOR A SET OF ELEMENTARY SIPHONS BASED ON MIXED-INTEGER PROGRAMMING

Elementary siphons are useful in the development of a deadlock prevention policy for a discrete event system modeled with Petri nets. This paper proposes an algorithm to iteratively extract a set of elementary siphons in a class of Petri nets, called system of simple sequential processes with resources （S3pR）. At each iteration, by a mixed-integer programming （MIP） method, the proposed algorithm finds a maximal unmarked siphon, classifies the places in it, extracts an elementary siphon from the classified places, and adds a new constraint in order to extract the next elementary siphon. This algorithm iteratively executes until no new unmarked siphons can be found. It finally obtains a unique set of elementary siphons and avoids a complete siphon enumeration. A theoretical analysis and examples are given to demonstrate its efficiency and practical potentials.

A Linear Mixed Integer Programming Model for N-Vehicle Exploration Problem

Finding the accurate solution for N-vehicle exploration problem is NP-hard in strong sense.In this paper,authors build a linear mixed integer programming model for N-vehicle exploration problem based on its properties.The model is then proved equivalent to the original problem.Given the model,one can apply the already existed methods and algorithms for mixed integer linear programming on N-vehicle exploration problem,which helps to enrich methods for solving N-vehicle exploration problem.

Optimization Methods for Mixed Integer Weakly Concave Programming Problems

In this paper,we consider a class of mixed integer weakly concave programming problems(MIWCPP)consisting of minimizing a difference of a quadratic function and a convex function.A new necessary global optimality conditions for MIWCPP is presented in this paper.A new local optimization method for MIWCPP is designed based on the necessary global optimality conditions,which is different from the traditional local optimization method.A global optimization method is proposed by combining some auxiliary functions and the new local optimization method.Furthermore,numerical examples are also presented to show that the proposed global optimization method for MIWCPP is efficient.