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.

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.

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.

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.

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.

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.

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.

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.

Integer Programming Model for Maximum Clique in Graph

The maximum clique or maximum independent set of graph is a classical problem in graph theory. Com- bined with Boolean algebra and integer programming, two integer programming models for maximum clique problem, which improve the old results were designed in this paper. Then, the programming model for maximum independent set is a corollary of the main results. These two models can be easily applied to computer algorithm and software, and suitable for graphs of any scale. Finally the models are presented as Lingo algorithms, verified and compared by sev- eral examples.

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

An integer programming formulation and iterative scheme algorithm for the block relocation problem

In this paper, we deal with the unrestricted block relocation problem. We present a new integerprogramming formulation for solving the problem. The initial formulation is improved by tighteningconstraints and a pre-processing step to fix several variables. We design a exact iterativescheme algorithm based on a fast heuristic for the integer programming formulation (ISA-FH).Computational results show the effectiveness of the improved formulation and algorithm.

NONLINEAR INTEGER PROGRAMMING AND GLOBALOPTIMIZATION

Various approaches have been developed for solving a variety of continuous global optimization problems. But up to now, less work has been devoted to solving nonlinear integer programming problems due to the inherent difficulty. This paper manages to transform the general nonlinear integer programming problem into an equivalent' special continuous global minimization problem. Thus any effective global optimization algorithm can be used to solve nonlinear integer programming problems. This result will also promote the research on global optimization. We present an interval Branch-and-Bound algorithm. Numerical experiments show that this approach is efficient. (Author abstract) 11 Refs.

A virtual network mapping algorithm based on integer programming

The virtual network(VN) embedding/mapping problem is recognized as an essential question of network virtualization. The VN embedding problem is a major challenge in this field. Its target is to efficiently map the virtual nodes and virtual links onto the substrate network resources. Previous research focused on designing heuristic-based algorithms or attempting two-stage solutions by solving node mapping in the first stage and link mapping in the second stage. In this study, we propose a new VN embedding algorithm based on integer programming. We build a model of an augmented substrate graph, and formulate the VN embedding problem as an integer program with an objective function and some constraints. A factor of topology-awareness is added to the objective function. The VN embedding problem is solved in one stage. Simulation results show that our algorithm greatly enhances the acceptance ratio, and increases the revenue/cost(R/C) ratio and the revenue while decreasing the cost of the VN embedding problem.

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.

Exact Penalty Function and Asymptotic Strong Nonlinear Duality in Integer Programming

In this paper, a logarithmic-exponential penalty function with two parameters for integer programming is discussed. We obtain the exact penalty properties and then establish the asymptotic strong nonlinear duality in the corresponding logarithmic-exponential dual formulation by using the obtained exact penalty properties. The discussion is based on the logarithmic-exponential nonlinear dual formulation proposed in [6].

Integer Programming Models for Computational Biology Problems

The recent years have seen an impressive increase in the use of IntegerProgramming models for the solution of optimization problems originating in Molecular Biology. Inthis survey, some of the most successful Integer Programming approaches are described, while a broadoverview of application areas being is given in modern Computational Molecular Biology.