A new approach for solving the Stokes problem

In this paper, a new approach for finding the approximate solution of the Stokes problem is introduced. In this method the problem is transformed to an equivalent optimization problem. Then, by considering it as a distributed parameter control system, the theory of measure is used to approximate the velocity functions by piecewise linear functions. Then, the approximate values of pressure are obtained by a finite difference scheme.     

A tree search procedure for the container pre-marshalling problem

In the container pre-marshalling problem (CPMP) n items are given that belong to G different item groups (g = 1, … , G) and that are piled up in up to S stacks with a maximum stack height H. A move can shift one item from one stack to another one. A sequence of moves of minimum length has to be determined that transforms the initial item distribution so that in each of the stacks the items are sorted by their group index g in descending order. The CPMP occurs frequently in container terminals of seaports. It has to be solved when export containers, piled up in stacks, are sorted in a pre-marshalling process so that they can be loaded afterwards onto a ship faster and more efficiently. This article presents a heuristic tree search procedure for the CPMP. The procedure is compared to solution approaches for the CPMP that were published so far and turns out to be very competitive. Moreover, computational results for new and difficult CPMP instances are presented.     

A global optimization approach for solving the convex multiplicative programming problem

We consider a convex multiplicative programming problem of the form% MathType!MTEF!2!1!+-% feaafiart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn% hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr% 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq-Jc9% vqaqpepm0xbba9pwe9Q8fs0-yqaqpepae9qq-f0-yqaqVeLsFr0-vr% 0-vr0db8meaabaqaciGacaGaaeqabaWaaeaaeaaakeaacaGG7bGaam% OzamaaBaaaleaacaaIXaaabeaakiaacIcacaWG4bGaaiykaiabgwSi% xlaadAgadaWgaaWcbaGaaGOmaaqabaGccaGGOaGaamiEaiaacMcaca% GG6aGaamiEaiabgIGiolaadIfacaGG9baaaa!4A08!\[\{ f_1 (x) \cdot f_2 (x):x \in X\} \]where X is a compact convex set of ⁿ and f ₁, f ₂ are convex functions which have nonnegative values over X.Using two additional variables we transform this problem into a problem with a special structure in which the objective function depends only on two of the (n+2) variables. Following a decomposition concept in global optimization we then reduce this problem to a master problem of minimizing a quasi-concave function over a convex set in ² ₂. This master problem can be solved by an outer approximation method which requires performing a sequence of simplex tableau pivoting operations. The proposed algorithm is finite when the functions f _i, (i=1, 2) are affine-linear and X is a polytope and it is convergent for the general convex case.Partly supported by the Deutsche Forschungsgemeinschaft Project CONMIN.     

A reduction approach for solving the rectangle packing area minimization problem

In the rectangle packing area minimization problem (RPAMP) we are given a set of rectangles with known dimensions. We have to determine an arrangement of all rectangles, without overlapping, inside an enveloping rectangle of minimum area. The paper presents a generic approach for solving the RPAMP that is based on two algorithms, one for the 2D Knapsack Problem (KP), and the other for the 2D Strip Packing Problem (SPP). In this way, solving an instance of the RPAMP is reduced to solving multiple SPP and KP instances. A fast constructive heuristic is used as SPP algorithm while the KP algorithm is instantiated by a tree search method and a genetic algorithm alternatively. All these SPP and KP methods have been published previously. Finally, the best variants of the resulting RPAMP heuristics are combined within one procedure. The guillotine cutting condition is always observed as an additional constraint. The approach was tested on 15 well-known RPAMP instances (above all MCNC and GSRC instances) and new best solutions were obtained for 10 instances. The computational effort remains acceptable. Moreover, 24 new benchmark instances are introduced and promising results are reported.     

A column generation approach for solving the patient admission scheduling problem

This paper addresses the Patient Admission Scheduling (PAS) problem. The PAS problem entails assigning elective patients to beds, while satisfying a number of hard constraints and as many soft constraints as is possible, and arises at all planning levels for hospital management. There exist a few, different variants of this problem. In this paper we consider one such variant and propose an optimization-based heuristic building on branch-and-bound, column generation, and dynamic constraint aggregation to solve it. We achieve tighter lower bounds than previously reported in the literature and, in addition, we are able to produce new best known solutions for five out of twelve instances from a publicly available repository.     

A hybrid metaheuristic approach to solving the UBQP problem

This paper presents a hybrid metaheuristic approach (HMA) for solving the unconstrained binary quadratic programming (UBQP) problem. By incorporating a tabu search procedure into the framework of evolutionary algorithms, the proposed approach exhibits several distinguishing features, including a diversification-based combination operator and a distance-and-quality based replacement criterion for pool updating. The proposed algorithm is able to easily obtain the best known solutions for 31 large random instances up to 7000 variables (which no previous algorithm has done) and find new best solutions for three of nine instances derived from the set-partitioning problem, demonstrating the efficacy of our proposed algorithm in terms of both solution quality and computational efficiency. Furthermore, some key elements and properties of the HMA algorithm are also analyzed.     

A matheuristic approach for solving a home health care problem

We deal with a Home Health Care Problem (HHCP) which objective consists in constructing the optimal routes and rosters for the health care staffs. The challenge lies in combining aspects of vehicle routing and staff rostering which are two well known hard combinatorial optimization problems. To solve this problem, we initially propose an integer linear programming formulation (ILP) and we tested this model on small instances. To deal with larger instances we develop a matheuristic based on the decomposition of the ILP formulation into two problems. The first one is a set partitioning like problem and it represents the rostering part. The second problem consists in the routing part. This latter is equivalent to a Multi-depot Traveling Salesman Problem with Time Windows (MTSPTW).     

A memetic algorithm approach for solving the multidimensional multi-way number partitioning problem

In this paper, we describe a generalization of the multidimensional two-way number partitioning problem (MDTWNPP) where a set of vectors has to be partitioned into p sets (parts) such that the sums per every coordinate should be exactly or approximately equal. We will call this generalization the multidimensional multi-way number partitioning problem (MDMWNPP). Also, an efficient memetic algorithm (MA) heuristic is developed to solve the multidimensional multi-way number partitioning problem obtained by combining a genetic algorithm (GA) with a powerful local search (LS) procedure. The performances of our memetic algorithm have been compared with the existing numerical results obtained by CPLEX based on an integer linear programming formulation of the problem. The solution reveals that our proposed methodology performs very well in terms of both quality of the solutions obtained and the computational time compared with the previous method of solving the multidimensional two-way number partitioning problem.     

A decomposition approach for solving a broadcast domination network design problem

We consider an optimization problem that integrates network design and broadcast domination decisions. Given an undirected graph, a feasible broadcast domination is a set of nonnegative integer powers f _i assigned to each node i, such that for any node j in the graph, there exists some node k having a positive f _k -value whose shortest distance to node j is no more than f _k . The cost of a broadcast domination solution is the sum of all node power values. The network design problem constructs edges that decrease the minimum broadcast domination cost on the graph. The overall problem we consider minimizes the sum of edge construction costs and broadcast domination costs. We show that this problem is NP-hard in the strong sense, even on unweighted graphs. We then propose a decomposition strategy, which iteratively adds valid inequalities based on optimal broadcast domination solutions corresponding to the first-stage network design solutions. We demonstrate that our decomposition approach is computationally far superior to the solution of a single large-scale mixed-integer programming formulation.     

A decomposition approach for a new test-scenario in complex problem solving

Over the last years, psychological research has increasingly used computer-supported tests, especially in the analysis of complex human decision making and problem solving. The approach is to use computer-based test scenarios and to evaluate the performance of participants and correlate it to certain attributes, such as the participant's capacity to regulate emotions. However, two important questions can only be answered with the help of modern optimization methodology. The first one considers an analysis of the exact situations and decisions that led to a bad or good overall performance of test persons. The second important question concerns performance, as the choices made by humans can only be compared to one another, but not to the optimal solution, as it is unknown in general.Additionally, these test-scenarios have usually been defined on a trial-and-error basis, until certain characteristics became apparent. The more complex models become, the more likely it is that unforeseen and unwanted characteristics emerge in studies. To overcome this important problem, we propose to use mathematical optimization methodology not only as an analysis and training tool, but also in the design stage of the complex problem scenario.We present a novel test scenario, the IWR Tailorshop, with functional relations and model parameters that have been formulated based on optimization results. We also present a tailored decomposition approach to solve the resulting mixed-integer nonlinear programs with nonconvex relaxations and show some promising results of this approach.     

A new computational approach for solving optimal control of linear PDEs problem

In this paper, we present a new computational approach for solving an internal optimal control problem, which is governed by a linear parabolic partial differential equation. Our approach is to approximate the PDE problem by a nonhomogeneous ordinary differential equation system in higher dimension. Then, the homogeneous part of ODES is solved using semigroup theory. In the next step, the convergence of this approach is verified by means of Toeplitz matrix. In the rest of the paper, the optimal control problem is solved by utilizing the solution of homogeneous part. Finally, a numerical example is given.     

A finite-element approach to solving a thermal conductivity problem for thick plates

A method is proposed for the numerical solution of a problem in the thermal conductivity a plate heated by a moving heat source, taking into account the dependence of the thermal properties of the material on temperature. A hypothesis of N. N. Rykalin concerning the state of the thermal field is adopted. The method is based on a spline variant of the finite-element method; this is based on the synthesis of parametrization and finite elements with splines. A FORTRAN algorithm is given for performing the method on an ES series computer.Translated from Matematichekie Metody i Fiziko-Mekhanicheskie Polya, No. 29, pp. 58–62, 1989.     

A new crossover approach for solving the multiple travelling salesmen problem using genetic algorithms

This paper proposes a new crossover operator called two-part chromosome crossover (TCX) for solving the multiple travelling salesmen problem (MTSP) using a genetic algorithm (GA) for near-optimal solutions. We adopt the two-part chromosome representation technique which has been proven to minimise the size of the problem search space. Nevertheless, the existing crossover method for the two-part chromosome representation has two limitations. Firstly, it has extremely limited diversity in the second part of the chromosome, which greatly restricts the search ability of the GA. Secondly, the existing crossover approach tends to break useful building blocks in the first part of the chromosome, which reduces the GA’s effectiveness and solution quality. Therefore, in order to improve the GA search performance with the two-part chromosome representation, we propose TCX to overcome these two limitations and improve solution quality. Moreover, we evaluate and compare the proposed TCX with three different crossover methods for two MTSP objective functions, namely, minimising total travel distance and minimising longest tour. The experimental results show that TCX can improve the solution quality of the GA compared to three existing crossover approaches.     

An approach for solving a fuzzy multiobjective programming problem

In this paper we present a new approach, based on the Nearest Interval Approximation Operator, for dealing with a multiobjective programming problem with fuzzy-valued objective functions.     

An approach for solving of a moving boundary problem

In this paper we shall study moving boundary problems, and we introduce an approach for solving a wide range of them by using calculus of variations and optimization. First, we transform the problem equivalently into an optimal control problem by defining an objective function and artificial control functions. By using measure theory, the new problem is modified into one consisting of the minimization of a linear functional over a set of Radon measures; then we obtain an optimal measure which is then approximated by a finite combination of atomic measures and the problem converted to an infinite-dimensional linear programming. We approximate the infinite linear programming to a finite-dimensional linear programming. Then by using the solution of the latter problem we obtain an approximate solution for moving boundary function on specific time. Furthermore, we show the path of moving boundary from initial state to final state.     

An approach for solving the lot-sizing problem of a market-driven foundry

Foundries can be found all over Brazil and they are very important to its economy. In 2008, a mixed integer-programming model for small market-driven foundries was published, attempting to minimize delivery delays. We undertook a study of that model. Here, we present a new approach based on the decomposition of the problem into two sub-problems: production planning of alloys and production planning of items. Both sub-problems are solved using a Lagrangian heuristic based on transferences. An important aspect of the proposed heuristic is its ability to take into account a secondary practice objective solution: the furnace waste. Computational tests show that the approach proposed here is able to generate good quality solutions that outperform prior results.     

A new linear programming approach and genetic algorithm for solving airline boarding problem

The airline industry is under intense competition to simultaneously increase efficiency and satisfaction for passengers and profitability and internal system benefit for itself. The boarding process is one way to achieve these objectives as it tends itself to adaptive changes. In order to increase the flying time of a plane, commercial airlines try to minimize the boarding time, which is one of the most lengthy parts of a plane’s turn time. To reduce boarding time, it is thus necessary to minimize the number of interferences between passengers by controlling the order in which they get onto the plane through a boarding policy. Here, we determine the passenger boarding problem and examine the different kinds of passenger boarding strategies and boarding interferences in a single aisle aircraft. We offer a new integer linear programming approach to reduce the passenger boarding time. A genetic algorithm is used to solve this problem. Numerical results show effectiveness of the proposed algorithm.     

A tabu search approach for solving a difficult forest harvesting machine location problem

This paper deals with two main problems in forest harvesting. The first is that of selecting the locations for the machinery to haul logs from the points where they are felled to the roadside. The second consists in designing the access road network connecting the existing road network with the points where machinery is installed. Their combination induces a very important and difficult problem to solve in forest harvesting. It can be formulated as a combination of two difficult optimization problems: a plant location problem and a fixed charge network flow problem. In this paper, we propose a solution approach based on tabu search. The proposed heuristic includes several enhancements of the basic tabu search framework. The main difficulty lies in evaluating neighboring solutions, which involves decisions related to location of machinery and to road network arcs. Hence, the neighborhood is more complex than in typical applications of metaheuristics. Minimum spanning tree algorithms and Steiner tree heuristics are used to deal with this problem. Numerical results indicate that the heuristic approach is very attractive and leads to better solutions than those provided by state-of-the-art integer programming codes in limited computation times, with solution times significantly smaller. The numerical results do not vary too much when typical parameters such as the tabu tenure are modified, except for the dimension of neighborhood.