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.

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.

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.

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.

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.

ALLOCATING REPAIRABLE SYSTEM'S RELIABILITY SUBJECT TO MINIMAL TOTAL COST-AN INTEGER PROGRAMMING APPROACH

Reliability allocation problem is commonly treated using a closed-form expression relating the cost to reliability. A recent approach has introduced the use of discrete integer technique for un-repairable systems. This research addresses the allocation problem for repairable systems. It presents an integer formulation for finding the optimum selection of components based on the integer values of their Mean Time to Failure （MTTF） and Mean Time to Repair （MTTR）. The objective is to minimize the total cost under a system reliability constraint, in addition to other physical constraints. Although, a closed-form expression relating the cost to reliability may not be a linear; however, in this research, the objective function will always be linear regardless of the shape of the equivalent continuous closed-form function. An example is solved using the proposed method and compared with the solution of the continuous closed-form version. The formulation for all possible system configurations, components and subsystems are also considered.

An Approximate Algorithm for a Class of Nonlinear Bilevel Integer Programming

The algorithm for a class of nonlinear bilevel integer programming is discussed in this paper. It is based on the theory and algorithm for nonlinear integer programming. The continuity methods for integer programming are studied in this paper. After simulated annealing algorithm is applied to the upper-level programming problem and the thought of filled function method for continuous global optimization is applied to the corresponding lower-level programming, an approximate algorithm is established. The satisfactory algorithm is elaborated in the following example.

Fitting boxes to Manhattan scenes using linear integer programming

We propose an approach for automatic generation of building models by assembling a set of boxes using a Manhattan-world assumption.The method first aligns the point cloud with a per-building local coordinate system,and then fits axis-aligned planes to the point cloud through an iterative regularization process.The refined planes partition the space of the data into a series of compact cubic cells(candidate boxes)spanning the entire 3D space of the input data.We then choose to approximate the target building by the assembly of a subset of these candidate boxes using a binary linear programming formulation.The objective function is designed to maximize the point cloud coverage and the compactness of the final model.Finally,all selected boxes are merged into a lightweight polygonal mesh model,which is suitable for interactive visualization of large scale urban scenes.Experimental results and a comparison with state-of-the-art methods demonstrate the effectiveness of the proposed framework.

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.

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.

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.