Exact methods and a heuristic for the optimization of an integrated replenishment-storage planning problem

In this paper we study the coordination of different activities in a supply chain issued from a real case. Multiple suppliers send raw materials (RMs) to a distribution center (DC) that delivers them to a unique plant where the storage of the RMs and the finished goods is not possible. Then, the finished goods are directly shipped to multiple customers having just‐in‐time (JIT) demands. Under these hypotheses, we show that the problem can be reduced to multiple suppliers and one DC. Afterwards, we analyze two cases; in the first, we consider an uncapacitated storage at DC, and in the second, we analyze the capacitated storage case. For the first case, we show that the problem is NP‐hard in the ordinary sense using the Knapsack decision problem. We then propose two exact methods: a mixed integer linear program (MILP) and a pseudopolynomial dynamic program. A classical dynamic program and an improved one using the idea of Shaw and Wagelmans are given. With numerical tests we show that the dynamic program gives the optimal solution in reasonable time for quite large instances compared with the MILP. For the second case, the capacity limitation in DC is assumed, which makes the problem solving more challenging. We propose an MILP and a dynamic programming‐based heuristic that provides solutions close to the optimal solution in very short times.     

Exact solution for the optimal neuronal layout problem

Evolution perfected brain design by maximizing its functionality while minimizing costs associated with building and maintaining it. Assumption that brain functionality is specified by neuronal connectivity, implemented by costly biological wiring, leads to the following optimal design problem. For a given neuronal connectivity, find a spatial layout of neurons that minimizes the wiring cost. Unfortunately, this problem is difficult to solve because the number of possible layouts is often astronomically large. We argue that the wiring cost may scale as wire length squared, reducing the optimal layout problem to a constrained minimization of a quadratic form. For biologically plausible constraints, this problem has exact analytical solutions, which give reasonable approximations to actual layouts in the brain. These solutions make the inverse problem of inferring neuronal connectivity from neuronal layout more tractable.     

Exact search-space size for the refactoring scheduling problem

Ouni et al. “Maintainability defects detection and correction: a multi-objective approach” proposed a search-based approach for generating optimal refactoring sequences. They estimated the size of the search space for the refactoring scheduling problem using a formulation that is incorrect; the search space is estimated to be too much larger than it is. We provide in this paper the exact expression for computing the number of possible refactoring sequences of a software system. This could be useful for researchers and practitioners interested in developing new approaches to automate refactoring.     

Exact one-way methods for acoustic waveguides

Exact one-way re-formulations of the Helmholtz equation are useful for waveguide problems, since the resulting equations can be efficiently solved as ‘initial’ value problems by range marching methods. Some numerical methods for these re-formulations are reviewed in this paper. This includes a switched method that avoids the singularities of the operators and the large range step methods that give exact solutions for range independent regions and allow large range steps for weakly range dependent regions. For waveguides with curved bottoms, a method based on a local orthogonal transformation is described. As an interesting application, the scattering problem of periodic waveguides is considered.     

Exact procedures for solving the discrete ordered median problem

The discrete ordered median problem (DOMP) integrates classical discrete location problems, such as the N-median, N-center and Uncapacitated Facility Location problems. It was introduced by Nickel (In: Fleischmann B, Lasch R, Derigs U, Domschke W, Rieder U, editors. Operations Research Proceedings 2000, Berlin: Springer, 2001. p. 71–76), who formulated it as both a nonlinear and a linear integer program. We propose an alternative integer linear programming formulation for the DOMP, discuss relationships between both integer linear programming formulations, and show how properties of optimal solutions can be used to strengthen these formulations. Moreover, we present a specific branch and bound procedure to solve the DOMP more efficiently. We test the integer linear programming formulations and this branch and bound method computationally on randomly generated test problems.     

Exact pseudopolynomial algorithm for one sequence partitioning problem

We consider a strongly NP-hard problem of partitioning a finite sequence of vectors in a Euclidean space into two clusters of given size with the criterion of minimizing the total sum of square distances from cluster elements to their centers. The center of the first cluster is subject to optimization, defined by the mean value of all vectors in this cluster. The center of the second cluster is fixed at the origin. The partition is subject to the following condition: the difference between indices of two subsequent vectors included in the first cluster is bounded from above and below by given constants. We propose an exact pseudopolynomial algorithm for the case of a problem where the dimension of the space is fixed, and components of input vectors are integer-valued.     

Exact solution of the robust knapsack problem

We consider an uncertain variant of the knapsack problem in which the weight of the items is not exactly known in advance, but belongs to a given interval, and an upper bound is imposed on the number of items whose weight differs from the expected one. For this problem, we provide a dynamic programming algorithm and present techniques aimed at reducing its space and time complexities. Finally, we computationally compare the performances of the proposed algorithm with those of different exact algorithms presented so far in the literature for robust optimization problems.     

基于动态资源权重的多技能项目调度启发式算法

多技能资源受限项目调度问题中,一个资源可同时具备多项技能,相较于传统的单技能项目调度,其资源分配对调度计划的工期影响程度更大,因此在对多技能项目进行排程时更加重视资源的分配.基于此,从资源视角提出一种启发式算法求解工期最短的调度计划.算法以并行调度为主体,并设计一种动态资源权重计算方法,在每一决策点,首先采用二分图最大...     

Heuristic framework for the resource constrained multi-project scheduling problem

Real world scheduling problems can be affected by diverse and conflicting goals. Some scheduling problems are bounded with limited resources and represent a considerable challenge to planners. When multiple projects are involved, scheduling problems become even more complex and difficult to resolve. Because of the combinatory explosions and unrealistic assumptions, traditional management sciences techniques such as PERT, CPM, and a host of similar project schedulers are very limited to special cases of scheduling problems. Recent developments of artificial intelligence (AI) and knowledge engineering techniques have made the development of expert systems which can be driven by scheduling heuristics to resolve problems associated with the traditional optimization techniques by giving “better” rather than “best” solutions. This paper presents the conceptual framework and development strategy for an expert system in multi-project scheduling domains. This paper will also present a practical application of the scheduling system.     

Exact algorithms for the double vehicle routing problem with multiple stacks

The Double Traveling Salesman Problem with Multiple Stacks (DTSPMS) is a one-to-one pickup-and-delivery single-vehicle routing problem with backhaul deliveries. The vehicle carries a container divided into stacks of fixed height, each following a Last-In-First-Out policy, and the aim is to perform pickups and deliveries by minimizing the total routing cost and ensuring a feasible loading/unloading of the vehicle.A realistic generalization of the DTSPMS arises when a single vehicle is not enough to collect all products, and therefore multiple, and possibly heterogeneous vehicles are needed to perform the transportation operations. This paper introduces and formulates this generalization, that we refer as the Double Vehicle Routing Problem with Multiple Stacks. It proposes three models, the first one based on a three-index formulation and solved by a branch-and-cut algorithm, and the other two based on two set partitioning formulations using different families of columns and solved by a branch-and-price and a branch-and-price-and-cut algorithm, respectively.The performance of these algorithms has been studied on a wide family of benchmark test instances, observing that, although the branch-and-cut algorithm shows a better performance on instances with a small number of vehicles, the performance of the branch-and-price and the branch-and-price-and-cut algorithms improves as the number of vehicles grows. Additionally, the first set partitioning formulation yields tighter lower bounds, but the second formulation, because of its simplicity, provides better convergence properties, solving instances with up to fifty vertices to proven optimality.     

A genetic algorithm for the robust resource leveling problem

The resource leveling problem (RLP) involves the determination of a project baseline schedule that specifies the planned activity starting times while satisfying both the precedence constraints and the project deadline constraint under the objective of minimizing the variation in the resource utilization. However, uncertainty is inevitable during project execution. The baseline schedule generated by the deterministic RLP model tends to fail to achieve the desired objective when durations are uncertain. We study the robust resource leveling problem in which the activity durations are stochastic and the objective is to obtain a robust baseline schedule that minimizes the expected positive deviation of both resource utilizations and activity starting times. We present a genetic algorithm for the robust RLP. In order to demonstrate the effectiveness of our genetic algorithm, we conduct extensive computational experiments on a large number of randomly generated test instances and investigate the impact of different factors (the marginal cost of resource usage deviations, the marginal cost of activity starting time deviations, the activity duration variability, the due date, the order strength, the resource factor and the resource constrainedness).     

Exact and heuristic algorithms for the interval data robust assignment problem

We consider the Assignment Problem with interval data, where it is assumed that only upper and lower bounds are known for each cost coefficient. It is required to find a minmax regret assignment. The problem is known to be strongly NP-hard. We present and compare computationally several exact and heuristic methods, including Benders decomposition, using CPLEX, a variable depth neighborhood local search, and two hybrid population-based heuristics. We report results of extensive computational experiments.     

Exact and heuristic methods for solving Boolean games

Boolean games are a framework for reasoning about the rational behavior of agents whose goals are formalized using propositional formulas. Compared to normal form games, a well-studied and related game framework, Boolean games allow for an intuitive and more compact representation of the agents’ goals. So far, Boolean games have been mainly studied in the literature from the Knowledge Representation perspective, and less attention has been paid on the algorithmic issues underlying the computation of solution concepts. Although some suggestions for solving specific classes of Boolean games have been made in the literature, there is currently no work available on the practical performance. In this paper, we propose the first technique to solve general Boolean games that does not require an exponential translation to normal-form games. Our method is based on disjunctive answer set programming and computes solutions (equilibria) of arbitrary Boolean games. It can be applied to a wide variety of solution concepts, and can naturally deal with extensions of Boolean games such as constraints and costs. We present detailed experimental results in which we compare the proposed method against a number of existing methods for solving specific classes of Boolean games, as well as adaptations of methods that were initially designed for normal-form games. We found that the heuristic methods that do not require all payoff matrix entries performed well for smaller Boolean games, while our ASP based technique is faster when the problem instances have a higher number of agents or action variables.     

针对资源调度问题的局部优化算法

由于现有局部搜索算法在处理数据量较大的受限资源工程调度问题时效果欠佳,提出了一种与FBI优化相结合的局部搜索方案--FBLS.FBLS利用问题的对称性,以局部搜索的解集为单位,在原问题与对称问题上交替进行优化.通过分析领域中解的合法性以及可能出现的重复情况,削减领域中解的数量,提高搜索效率.在PSPLIB的数据测试中,经FBLS优化所得到的结果已经优于所有非智能甚至大部分智能演化算法.作为一种通过局部搜索进行优化的方法,FBLS可以被灵活诮用于各种已有的智能算法框架求解RCPSP问题.     

Exact and approximate algorithms for the index selection problem inphysical database design

The index selection problem (ISP) is an important optimization problem in the physical design of databases. The aim of this paper is to show that ISP, although NP-hard, can in practice be solved effectively through well-designed algorithms. We formulate ISP as a 0-1 integer linear program and describe an exact branch-and-bound algorithm based on the linear programming relaxation of the model. The performance of the algorithm is enhanced by means of procedures to reduce the size of the candidate index set. We also describe heuristic algorithms based on the solution of a suitably defined knapsack subproblem and on Lagrangian decomposition. Finally, computational results on several classes of test problems are given. We report the exact solution of large-scale ISP instances involving several hundred indexes and queries. We also evaluate one of the heuristic algorithms we propose on very large-scale instances involving several thousand indexes and queries and show that it consistently produces very tight approximate (and sometimes provably optimal) solutions. Finally, we discuss possible extensions and future directions of research     

Exact formulations and algorithm for the train timetabling problem with dynamic demand

In this paper we study the design and optimization of train timetabling adapted to a dynamic demand environment. This problem arises in rapid train services which are common in most important cities. We present three formulations for the problem, with the aim of minimizing passenger average waiting time. The most intuitive model would consider binary variables representing train departure times but it yields to non-linear objective function. Instead, we introduce flow variables, which allow a linear representation of the objective function. We provide incremental improvements on these formulations, which allows us to evaluate and compare the benefits and disadvantages of each modification. We present a branch-and-cut algorithm applicable to all formulations. Through extensive computational experiments on several instances derived from real data provided by the Madrid Metropolitan Railway, we show the advantages of designing a timetable adapted to the demand pattern, as opposed to a regular timetable. We also perform an extensive computational comparison of all linear formulations in terms of size, solution quality and running time.     

Exact algorithms for the minimum power symmetric connectivity problem in wireless networks

In this paper we consider the problem of assigning transmission powers to the nodes of a wireless network in such a way that all the nodes are connected by bidirectional links and the total power consumption is minimized.Two mixed integer programming formulations are presented together with some new valid inequalities for the polytopes associated. A preprocessing technique and two exact algorithms based on the formulations previously introduced are also proposed.Comprehensive computational results, which show the effectiveness of the new valid inequalities and of the preprocessing technique are presented. The experiments also show that the exact approaches we propose outperform more complex methods recently appeared in the literature.     

Priority-based heuristics for the multi-skill resource constrained project scheduling problem

In this paper we investigate one of the most recent extensions of the Resource Constrained Project Scheduling Problem (RCPSP): the Multi-Skill Resource Constrained Project Scheduling Problem (MSRCPSP). For this complex problem we propose the use of a parallel scheduling scheme. Such scheme has been successfully applied to the RCPSP. Nevertheless, in order to apply it to the MSRCPSP two new concepts are developed: resource weight and activity grouping. We discuss such concepts and use them for the new heuristic framework proposed. A series of computational tests performed using a large number of instances and reported in this paper shows that the new heuristic is very effective in finding high quality solutions within very small CPU times.