A Controlled Random Search Technique Incorporating the Simulated Annealing Concept for Solving Integer and Mixed Integer Global Optimization Problems

In this paper, a computational algorithm, named RST2ANU algorithm, has been developed for solving integer and mixed integer global optimization problems. This algorithm, which primarily is based on the original controlled random search approach of Price [22i], incorporates a simulated annealing type acceptance criterion in its working so that not only downhill moves but also occasional uphill moves can be accepted. In its working it employs a special truncation procedure which not only ensures that the integer restrictions imposed on the decision variables are satisfied, but also creates greater possibilities for the search leading to a global optimal solution. The reliability and efficiency of the proposed RST2ANU algorithm has been demonstrated on thirty integer and mixed integer optimization problems taken from the literature. The performance of the algorithm has been compared with the performance of the corresponding purely controlled random search based algorithm as well as the standard simulated annealing algorithm. The performance of the method on mathematical models of three realistic problems has also been demonstrated.     

An exact approach for solving integer problems under probabilistic constraints with random technology matrix

This paper addresses integer programming problems under probabilistic constraints involving discrete distributions. Such problems can be reformulated as large scale integer problems with knapsack constraints. For their solution we propose a specialized Branch and Bound approach where the feasible solutions of the knapsack constraint are used as partitioning rules of the feasible domain. The numerical experience carried out on a set covering problem with random covering matrix shows the validity of the solution approach and the efficiency of the implemented algorithm.     

NONLINEAR INTEGER PROGRAMMING AND GLOBALOPTIMIZATION

1.IntroductionAlthoughthegenerallinearintegerprogrammingproblemisNP-hard,muchworkhasbeendevotedtoit(SeeNumhauserandWolsey[1988],Schrijver[1986]).Thesolutionmethodsincludethecuttingplane,theBranch-and-Bound,thedynamicprogrammingmethodsetc..However,thegeneralnonlinearintegerprogrammingproblemisdifficulttosolve.GareyandJohnson[1979]pointedoutthattheintegerprogrammingoverRewithalinearobjectivefunctionandquadraticconstraintsisundecidable.Soifanonlinearintegerprogrammingproblemishandled,itisalw…     

A genetic algorithm for the generalised assignment problem

A new algorithm for the generalised assignment problem is described in this paper. The algorithm is adapted from a genetic algorithm which has been successfully used on set covering problems, but instead of genetically improving a set of feasible solutions it tries to genetically restore feasibility to a set of near-optimal ones. Thus it may be regarded as operating in a dual sense to the more familiar genetic approach. The algorithm has been tested on generalised assignment problems of substantial size and compared to an exact integer programming approach and a well-established heuristic approach.     

Dual decomposition in stochastic integer programming

We present an algorithm for solving stochastic integer programming problems with recourse, based on a dual decomposition scheme and Lagrangian relaxation. The approach can be applied to multi-stage problems with mixed-integer variables in each time stage. Numerical experience is presented for some two-stage test problems.     

A real coded genetic algorithm for solving integer and mixed integer optimization problems

In this paper, a real coded genetic algorithm named MI-LXPM is proposed for solving integer and mixed integer constrained optimization problems. The proposed algorithm is a suitably modified and extended version of the real coded genetic algorithm, LXPM, of Deep and Thakur [K. Deep, M. Thakur, A new crossover operator for real coded genetic algorithms, Applied Mathematics and Computation 188 (2007) 895-912; K. Deep, M. Thakur, A new mutation operator for real coded genetic algorithms, Applied Mathematics and Computation 193 (2007) 211-230]. The algorithm incorporates a special truncation procedure to handle integer restrictions on decision variables along with a parameter free penalty approach for handling constraints. Performance of the algorithm is tested on a set of twenty test problems selected from different sources in literature, and compared with the performance of an earlier application of genetic algorithm and also with random search based algorithm, RST2ANU, incorporating annealing concept. The proposed MI-LXPM outperforms both the algorithms in most of the cases which are considered.     

A simple dual algorithm for the generalised assignment problem

A new algorithm for the generalised assignment problem is described in this paper. The dual-type algorithm uses a simple heuristic derived from a relaxation of the problem. The algorithm has been tested on generalised assignment problems of substantial size and compared to an exact integer programming approach and a well-established heuristic approach. Computational results look promising in terms of speed and solution quality.     

A simplex social spider algorithm for solving integer programming and minimax problems

In this paper, we propose a new hybrid social spider algorithm with simplex Nelder-Mead method in order to solve integer programming and minimax problems. We call the proposed algorithm a Simplex Social Spider optimization (SSSO) algorithm. In the the proposed SSSO algorithm, we combine the social spider algorithm with its powerful capability of performing exploration, exploitation, and the Nelder-Mead method in order to refine the best obtained solution from the standard social spider algorithm. In order to investigate the general performance of the proposed SSSO algorithm, we test it on 7 integer programming problems and 10 minimax problems and compare against 10 algorithms for solving integer programming problems and 9 algorithms for solving minimax problems. The experiments results show the efficiency of the proposed algorithm and its ability to solve integer and minimax optimization problems in reasonable time.     

Bus driver duty optimization using an integer programming and evolutionary hybrid algorithm

This paper describes the details of a successful application where an integer programming and evolutionary hybrid algorithm was used to solve a bus driver duty optimization problem. The task is NP-hard, therefore theoretically optimal solutions can only be calculated for very small problem instances. Our aim is to obtain solutions of good quality within reasonable time limits. We first applied an integer programming approach to a set partitioning problem. The model was solved with a column generation algorithm in a branch and bound scheme. In order to solve larger real-life problems, we have combined the integer programming method with a greedy 1+1 steady state evolutionary algorithm. The resulting hybrid algorithm was capable of providing near-optimal solutions within reasonable timescales to larger instances of the bus driver scheduling problem. We present the results and running times of our algorithm in detail, as well as possible directions of future improvements.     

Column enumeration based decomposition techniques for a class of non-convex MINLP problems

We propose a decomposition algorithm for a special class of nonconvex mixed integer nonlinear programming problems which have an assignment constraint. If the assignment decisions are decoupled from the remaining constraints of the optimization problem, we propose to use a column enumeration approach. The master problem is a partitioning problem whose objective function coefficients are computed via subproblems. These problems can be linear, mixed integer linear, (non-)convex nonlinear, or mixed integer nonlinear. However, the important property of the subproblems is that we can compute their exact global optimum quickly. The proposed technique will be illustrated solving a cutting problem with optimum nonlinear programming subproblems.     

On the computation of all supported efficient solutions in multi-objective integer network flow problems

This paper presents a new algorithm for identifying all supported non-dominated vectors (or outcomes) in the objective space, as well as the corresponding efficient solutions in the decision space, for multi-objective integer network flow problems. Identifying the set of supported non-dominated vectors is of the utmost importance for obtaining a first approximation of the whole set of non-dominated vectors. This approximation is crucial, for example, in two-phase methods that first compute the supported non-dominated vectors and then the unsupported non-dominated ones. Our approach is based on a negative-cycle algorithm used in single objective minimum cost flow problems, applied to a sequence of parametric problems. The proposed approach uses the connectedness property of the set of supported non-dominated vectors/efficient solutions to find all integer solutions in maximal non-dominated/efficient facets.     

Algorithms for highly symmetric linear and integer programs

This paper deals with exploiting symmetry for solving linear and integer programming problems. Basic properties of linear representations of finite groups can be used to reduce symmetric linear programming to solving linear programs of lower dimension. Combining this approach with knowledge of the geometry of feasible integer solutions yields an algorithm for solving highly symmetric integer linear programs which only takes time which is linear in the number of constraints and quadratic in the dimension.     

Finding discrete global minima with a filled function for integer programming

The filled function method is an approach to find the global minimum of multidimensional functions. This paper proposes a new definition of the filled function for integer programming problem. A filled function which satisfies this definition is presented. Furthermore, we discuss the properties of the filled function and design a new filled function algorithm. Numerical experiments on several test problems with up to 50 integer variables have demonstrated the applicability and efficiency of the proposed method.     

A partitioning algorithm for the network loading problem

This paper proposes a Benders-like partitioning algorithm to solve the network loading problem. The approach is an iterative method in which the integer programming solver is not used to produce the best integer point in the polyhedral relaxation of the set of feasible capacities. Rather, it selects an integer solution that is closest to the best known integer solution. Contrary to previous approaches, the method does not exploit the original mixed integer programming formulation of the problem. The effort of computing integer solutions is entirely left to a pure integer programming solver while valid inequalities are generated by solving standard nonlinear multicommodity flow problems. The method is compared to alternative approaches proposed in the literature and appears to be efficient for computing good upper bounds.     

Parametric Integer Programming Analysis: A Contraction Approach

An algorithm is presented for solving families of integer linear programming problems in which the problems are "related" by having identical objective coefficients and constraint matrix coefficients. The righthand-side constants have the form b + θd where b and d are conformable vectors and θ varies from zero to one.The approach consists primarily of solving the most relaxed problem (θ = 1) using cutting planes and then contracting the region of feasible integer solutions in such a manner that the current optimal integer solution is eliminated.The algorithm was applied to 1800 integer linear programming problems with reasonable success. Integer programming problems which have proved to be unsolvable using cutting planes have been solved by expanding the region of feasible integer solutions (θ = 1) and then contracting to the original region.     

A primogenitary linked quad tree approach for solution storage and retrieval in heuristic binary optimization

A data structure, called the primogenitary linked quad tree (PLQT), is used to store and retrieve solutions in heuristic solution procedures for binary optimization problems. Two ways are proposed to use integer vectors to represent solutions represented by binary vectors. One way is to encode binary vectors into integer vectors in a much lower dimension and the other is to use the sorted indices of binary variables with values equal to 0 or equal to 1. The integer vectors are used as composite keys to store and retrieve solutions in the PLQT. An algorithm processing trial solutions for insertion into or retrieval from the PLQT is developed. Examples are provided to demonstrate the way the algorithm works. Another algorithm traversing the PLQT is also developed. Computational results show that the PLQT approach takes only a very tiny portion of the CPU time taken by a linear list approach for the same purpose for any reasonable application. The CPU time taken by the PLQT managing trial solutions is negligible as compared to that taken by a heuristic procedure for any reasonably hard to solve binary optimization problem, as shown in a tabu search heuristic procedure for the capacitated facility location problem. Compared to the hashing approach, the PLQT approach takes the same or less amount of CPU time but much less memory space while completely eliminating collision.     

One approach to solving a discrete production planning problem with interval data

In this paper, we develop an approach to solving integer programming problems with interval data based on using the possibilities of varying the relaxation set of the problem. This is illustrated by means of an L-class enumeration algorithm for solving a dicrete production planning problem. We describe the algorithm and a number of its modifications and present results of a computational experiment for families of problems from the OR Library and with randomly generated initial data. This approach is also applied to obtain approximate solutions of the mentioned problem in its conventional setting.     

Solving Convex MINLP Optimization Problems Using a Sequential Cutting Plane Algorithm

In this article we look at a new algorithm for solving convex mixed integer nonlinear programming problems. The algorithm uses an integrated approach, where a branch and bound strategy is mixed with solving nonlinear programming problems at each node of the tree. The nonlinear programming problems, at each node, are not solved to optimality, rather one iteration step is taken at each node and then branching is applied. A Sequential Cutting Plane (SCP) algorithm is used for solving the nonlinear programming problems by solving a sequence of linear programming problems. The proposed algorithm generates explicit lower bounds for the nodes in the branch and bound tree, which is a significant improvement over previous algorithms based on QP techniques. Initial numerical results indicate that the described algorithm is a competitive alternative to other existing algorithms for these types of problems.     

A constraint generation scheme to probabilistic linear problems with an application to power system expansion planning

In this paper, we first describe a constraint generation scheme for probabilistic mixed integer programming problems. Next, we present a decomposition approach to the peak capacity expansion planning of interconnected hydrothermal generating systems, with bounds on the transmission capacity between the regions. The objective is to minimize investments in generating units and interconnection links, subject to constraints on supply reliability. The problem is formulated as a stochastic integer program. The constraint generation scheme, which is similar to Benders decomposition, is applied in the solution of the peak capacity expansion problem. The master problem in this decomposition scheme is an integer program, solved by implicit enumeration. The operating subproblem corresponds to a stochastic network flow problem, and is solved by a maximum flow algorithm and Monte Carlo simulation. The approach is illustrated through a case study involving the expansion of the system of the Brazilian Southeastern region.