Solving a gas-lift optimization problem by dynamic programming

Gas lift is a costly, however indispensable means to recover oil from high-depth reservoirs that entails solving the gas-lift optimization problem, GOP, often in response to variations in the dynamics of the reservoir and economic oscillations. GOP can be cast as a mixed integer nonlinear programming problem whose integer variables decide which oil wells should produce, while the continuous variables allocate the gas-compressing capacity to the active ones. This paper extends the GOP formulation to encompass uncertainties in the oil outflow and precedence constraints imposed on the activation of wells. Recursive solutions are suggested for instances devoid of precedence constraints, as well as instances arising from precedence constraints induced by forests and general acyclic graphs. For the first two classes, pseudo-polynomial algorithms are developed to solve a discretized version of GOP, while the most general version is shown to be NP-Hard in the strong sense. Numerical experiments provide evidence that the approximate algorithms obtained by solving the recurrences produce near-optimal solutions. Further, the family of cover inequalities of the knapsack problem is extended to the gas-lift optimization problem.     

Solving a bicriterion scheduling problem

Consider n jobs to be sequenced on a single machine. The objective functions to be minimized are the holding cost and the maximum tardiness. We first characterize the set of efficient points and then proceed to give a pseudo-polynomial algorithm to enumerate all these efficient points. Computational results illustrate the usefulness of the procedure.     

Solving a chemical batch scheduling problem by local search

In this paper the following chemical batch scheduling problem is considered: a set of orders has to be processed on a set of facilities. For each order a given amount of a product must be produced by means of chemical reactions before a given deadline. The production consists of a sequence of processes whereby each process has to be performed by one facility out of a given subset of facilities allowed for this process. The processing times depend on the choice of the facility and the processing is done in batch mode with given minimum and maximum sizes. The problem is to assign the processes to the facilities, splitting them into batches, and scheduling these batches in order to produce the demands within the given deadlines. For the scheduling part of the problem we present an approach based on the following steps. First, a procedure to calculate the minimum number of batches needed to satisfy the demands is presented. Based on this, the given problem is modeled in two different ways: as a general shop scheduling problem with set-up times or as scheduling problem with positive time-lags. Finally, a two-phase tabu search method is presented which is based on the two different formulations of the problem. The method is tested on some real world data. This revised version was published online in June 2006 with corrections to the Cover Date.     

Solving the sum-of-ratios problem by a stochastic search algorithm

In spite of the recent progress in fractional programming, the sum-of-ratios problem remains untoward. Freund and Jarre proved that this is an NP-complete problem. Most methods overcome the difficulty using the deterministic type of algorithms, particularly, the branch-and-bound method. In this paper, we propose a new approach by applying the stochastic search algorithm introduced by Birbil, Fang and Sheu to a transformed image space. The algorithm then computes and moves sample particles in the q − 1 dimensional image space according to randomly controlled interacting electromagnetic forces. Numerical experiments on problems up to sum of eight linear ratios with a thousand variables are reported. The results also show that solving the sum-of-ratios problem in the image space as proposed is, in general, preferable to solving it directly in the primal domain.     

Solving a multiobjective traveling salesman problem by dynamic programming

In this paper Klötzler's method of multiobjective dynamic programming is applied to the solution of a two-dimensional traveling salesman problem. In this way Bellman's and Held/Karp's dynamic programming approach to one-dimensional traveling salesman problems is extended to the multiobjective case.     

Solving multi-objective parallel machine scheduling problem by a modified NSGA-II

In this paper, we modify a Multi-Objective Evolutionary Algorithm, known as Nondominated sorting Genetic Algorithm-II (NSGA-II) for a parallel machine scheduling problem with three objectives. The objectives are – (1) minimization of total cost due tardiness, (2) minimization of the deterioration cost and (3) minimization of makespan. The formulated problem has been solved by three Multi-Objective Evolutionary Algorithms which are: (1) the original NSGA-II (Non-dominated Sorting Genetic Algorithm–II), (2) SPEA2 (Strength Pareto Evolutionary Algorithm-2) and (3) a modified version of NSGA-II as proposed in this paper. A new mutation algorithm has also been proposed depending on the type of problem and embedded in the modified NSGA-II. The results of the three algorithms have been compared and conclusions have been drawn. The modified NSGA-II is observed to perform better than the original NSGA-II. Besides, the proposed mutation algorithm also works effectively, as evident from the experimental results.     

Solving the unconstrained optimization problem by a variable neighborhood search

This paper presents variable neighborhood search (VNS) for the problem of finding the global minimum of a nonconvex function. The variable neighborhood search, which changes systematically neighborhood structures in the search for finding a better solution, is used to guide a set of standard improvement heuristics. This algorithm was tested on some standard test functions, and successful results were obtained. Its performance was compared with the other algorithms, and observed to be better.     

Solving feature subset selection problem by a Parallel Scatter Search

The aim of this paper is to develop a Parallel Scatter Search metaheuristic for solving the Feature Subset Selection Problem in classification. Given a set of instances characterized by several features, the classification problem consists of assigning a class to each instance. Feature Subset Selection Problem selects a relevant subset of features from the initial set in order to classify future instances. We propose two methods for combining solutions in the Scatter Search metaheuristic. These methods provide two sequential algorithms that are compared with a recent Genetic Algorithm and with a parallelization of the Scatter Search. This parallelization is obtained by running simultaneously the two combination methods. Parallel Scatter Search presents better performance than the sequential algorithms.     

Solving a capacitated hub location problem

In this paper we address a problem consisting of determining the routes and the hubs to be used in order to send, at minimum cost, a set of commodities from sources to destinations in a given capacitated network. The capacities and costs of the arcs and hubs are given, and the arcs connecting the hubs are not assumed to create a complete graph. We present a mixed integer linear programming formulation and describe two branch-and-cut algorithms based on decomposition techniques. We evaluate and compare these algorithms on instances with up to 25 commodities and 10 potential hubs. One of the contributions of this paper is to show that a Double Benders’ Decomposition approach outperforms the standard Benders’ Decomposition, which has been widely used in recent articles on similar problems. For larger instances we propose a heuristic approach based on a linear programming relaxation of the mixed integer model. The heuristic turns out to be very effective and the results of our computational experiments show that near-optimal solutions can be derived rapidly.     

Solving a large-scale crew pairing problem

Airline companies seek to solve the problem of determining an assignment of crews to a pre-determined flight schedule with minimum total cost, called the Crew Pairing Problem (CPP). Most of the existing studies focus on the CPP of North American airlines, which widely differs from that of most European airline companies in terms of the objective function, the flight structure, and the planning horizon. In this study, we develop an optimization-driven heuristic algorithm that can efficiently handle large-scale instances of the CPP that must be solved on a monthly basis. We perform computational experiments using flight schedules of an European airline company to test the performance of the solution method. Our computational results demonstrate that our algorithm is able to provide high-quality solutions to monthly instances with up to 27?000 flight legs.     

Solving a nonlinear inverse Robin problem through a linear Cauchy problem

ABSTRACT

Considered in this paper is an inverse Robin problem governed by a steady-state diffusion equation. By the Robin inverse problem, one wants to recover the unknown Robin coefficient on an inaccessible boundary from Cauchy data measured on the accessible boundary. In this paper, instead of reconstructing the Robin coefficient directly, we compute first the Cauchy data on the inaccessible boundary which is a linear inverse problem, and then compute the Robin coefficient through Newton's law. For the Cauchy problem, a parameter-dependent coupled complex boundary method (CCBM) is applied. The CCBM has its own merits, and this is particularly true when it is applied to the Cauchy problem. With the introduction of a positive parameter, we can prove the regularized solution is uniformly bounded with respect to the regularization parameter which is a very good property because the solution can now be reconstructed for a rather small value of the regularization parameter. For the problem of computing the Robin coefficient from the recovered Cauchy data, a least square output Tikhonov regularization method is applied to Newton's law to obtain a stable approximate Robin coefficient. Numerical results are given to show the feasibility and effectiveness of the proposed method.     

Solving a class of two-resource allocation problem by equivalent load method

We present an efficient algorithm for solving a class of two-resource allocation problem defined on a series-parallel graph, where nodes represent tasks of a given project and arcs represent precedence relationships. Two separate workloads are associated with each task and the time to complete a workload is inversely proportional to the amount of resource allocated. The time to complete a task is the maximum of the times taken to complete the two workloads. The problem is to allocate the two resources across the project so as to minimize the project duration. The proposed algorithm is derived based on the Equivalent Load Method by Monma, Schrijver, Todd, and Wei for the single-resource allocation problem.     

Solving the generalized minimum spanning tree problem by a branch-and-bound algorithm

We present an exact algorithm for solving the generalized minimum spanning tree problem (GMST). Given an undirected connected graph and a partition of the graph vertices, this problem requires finding a least-cost subgraph spanning at least one vertex out of every subset. In this paper, the GMST is formulated as a minimum spanning tree problem with side constraints and solved exactly by a branch-and-bound algorithm. Lower bounds are derived by relaxing, in a Lagrangian fashion, complicating constraints to yield a modified minimum cost spanning tree problem. An efficient preprocessing algorithm is implemented to reduce the size of the problem. Computational tests on a large set of randomly generated instances with as many as 250 vertices, 1000 edges, and 25 subsets provide evidence that the proposed solution approach is very effective.     

Solving a final value fractional diffusion problem by boundary condition regularization

The evolution process of fractional order describes some phenomenon of anomalous diffusion and transport dynamics in complex system. The equation containing fractional derivatives provides a suitable mathematical model for describing such a process. The initial boundary value problem is hard to solve due to the nonlocal property of the fractional order derivative. We consider a final value problem in a bounded domain for fractional evolution process with respect to time, which means to recover the initial state for some slow diffusion process from its present status. For this ill-posed problem, we construct a regularizing solution using quasi-reversible method. The well-posedness of the regularizing solution as well as the convergence property is rigorously analyzed. The advantage of the proposed scheme is that the regularizing solution is of the explicit analytic solution and therefore is easy to be implemented. Numerical examples are presented to show the validity of the proposed scheme.     

Solving the plant location problem on a line by linear programming

This paper investigates the simple uncapacitated plant location problem on a line. We show that under general conditions the special structure of the problem allows the optimal solution to be obtained directly from a linear programming relaxation. This result may be extended to the related p-median problem on a line. Thus, the practitioner is now able to use readily available LP codes in place of specialized algorithms to solve these one-dimensional models. The findings also shed some light on the “integer friendliness” of the general problem.     

Solving a vehicle routing problem by balancing the vehicles time utilization

Various vehicle routing problems (VRP) appear in the literature due to their important applications in the area of transportation and distribution.A VRP is characterized by the constraints that the involved factors must satisfy and by an optimality goal.In this paper, we develop a heuristic algorithm that

• (i)partitions suitably a distribution network into subnetworks. A single depot complies with every subnetwork, where a fleet of identical vehicles will start their itinerary. The nodes of the corresponding subnetwork are demand nodes that require a onetime visit by one only vehicle.
• (ii)Determine the routes of k vehicles, k=2,3,…, for every subnetwork so to minimize the visiting time of the corresponding demand nodes. Consequently the method computes the necessary vehicle number for each subnetwork so as to complete promptly the visiting requirement of all the demand nodes of the whole network. The main strategy of the algorithm for designing the vehicle routes consists of balancing the time utilization of the used vehicles. The paper is integrated by an application of the presented algorithm to the center of the city of Thessaloniki.

     

Solving a nonlinear spectral problem for a matrix

This paper examines the solving of the eigenvalue problem for a matrix M () with a nonlinear occurrence of the spectral parameter. Two methods are suggested for replacing the equation dat M()=0 by a scalar equationf()=0. Here the functionf() is not written formally, but a rule for computingf() at a fixed point of the domain in which the desired roots lie is indicated. Müller's method is used to solve the equationf()=0. The eigenvalue found is refined by Newton's method based on the normalized expansion of matrix M(), and the linearly independent vectors corresponding to it are computed. An ALGOL program and test examples are presented.Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova AN SSSR, Vol. 58, pp. 54–66, 1976.     

Solving a two-dimensional trim-loss problem with MILP

In this paper a two-dimensional trim-loss problem connected to the paper-converting industry is considered. The problem is to produce a set of product paper rolls from larger raw paper rolls such that the cost for waste and the cutting time is minimized. The problem is generally non-convex due to a bilinear objective function and some bilinear constraints, which give rise to difficulties in finding efficient numerical procedures for the solution. The problem can, however, be solved as a two-step procedure, where the latter step is a mixed integer linear programming (MILP) problem. In the present formulation, both the width and length of the raw paper rolls as well as the lengths of the product paper rolls are considered variables. All feasible cutting patterns are included in the problem and global optimal cutting patterns are obtained as the solution from the corresponding MILP problem. A numerical example is included to illustrate the proposed procedure.