Production stage allocation problem in large corporations

This paper studies a strategic-level decision problem on assigning production stages to geographically distributed subsidiaries in a large corporation so as to minimize the fixed cost and the expected value of the production/transportation costs under stochastic demands of customers. The influence of the economies and diseconomies of scale on unit production cost is considered. A nonlinear mixed integer programming model is designed for this problem. A local branching based solution method and a particle swarm optimization based solution method are developed for solving the model. Computational tests on real world data of Shanghai Volkswagen Auto Corp. are conducted. The results show that the proposed model can save about 2.5% of its revenue by comparing with the current decisions.     

Exact solution method to solve large scale integer quadratic multidimensional knapsack problems

In this paper we develop a branch-and-bound algorithm for solving a particular integer quadratic multi-knapsack problem. The problem we study is defined as the maximization of a concave separable quadratic objective function over a convex set of linear constraints and bounded integer variables. Our exact solution method is based on the computation of an upper bound and also includes pre-procedure techniques in order to reduce the problem size before starting the branch-and-bound process. We lead a numerical comparison between our method and three other existing algorithms. The approach we propose outperforms other procedures for large-scaled instances (up to 2000 variables and constraints). A extended abstract of this paper appeared in LNCS 4362, pp. 456–464, 2007.     

On approximation of the fixed charge transportation problem

In this paper we present a new approximation for computing lower bound for the fixed charge transportation problem (FCTP). The lower bounds thus generated delivered 87% optimal solutions for 56 randomly generated small, up to 6×10 in size, problems in an experimental design. For somewhat larger, 10×10 and 10×15 size problems, the lower bounds delivered an average error of 5%, approximately, using a fraction of CPU times as compared to CPLEX to solve these problems. The proposed lower bound may be used as a superior initial solution with any other existing branch-and-bound method or tabu search heuristic procedure to enhance convergence to the optimal solution for large size problems which cannot be solved by CPLEX due to time constraints.     

Managing Inventory with Cash Register Information: Sales Recorded but Not Demands

Inventory inaccuracy is common in many businesses. While retailers employ cash registers to enter incoming orders and outgoing sales, inaccuracy arises because they do not record invisible demand such as spoilage, damage, pilferage, or returns. This setting results in incomplete inventory and demand information. An important inventory control problem therefore is to maximize the total expected discounted profit under this setting. Allowing for dependence between demand and invisible demand, we obtain the associated dynamic programming equation with an infinite‐dimensional state space, and reduce it to a simpler form by employing the concept of unnormalized probability. We develop an analytical upper bound on the optimal profit as well as an iterative algorithm for an approximate solution of the problem. We compare profits of the iterative solution and the myopic solution, and then to the upper bound. We see that the iterative solution performs better than the myopic solution, and significantly so in many cases. Furthermore, it gives a profit not far from the upper bound, and is therefore close to optimal. Using our results, we also discuss meeting inventory service levels.     

Interactive fuzzy goal programming for multi-objective transportation problems

This paper presents an interactive fuzzy goal programming approach to determine the preferred compromise solution for the multi-objective transportation problem. The proposed approach considers the imprecise nature of the input data by implementing the minimum operator and also assumes that each objective function has a fuzzy goal. The approach focuses on minimizing the worst upper bound to obtain an efficient solution which is close to the best lower bound of each objective function. The solution procedure controls the search direction via updating both the membership values and the aspiration levels. An important characteristic of the approach is that the decision maker's role is concentrated only in evaluating the efficient solution to limit the influences of his/her incomplete knowledge about the problem domain. In addition, the proposed approach can be applied to solve other multi-objective decision making problems. The performance of this solution approach is evaluated by comparing its results with that of the two existing methods in the literature.     

An upper bound on the minimal total cost of the transportation problem with varying demands and supplies

In general cases, to find the exact upper bound on the minimal total cost of the transportation problem with varying demands and supplies is an NP-hard problem. In literature, there are only two approaches with several shortcomings to solve the problem. In this paper, the problem is formulated as a bi-level programming model, and proven to be solvable in a polynomial time if the sum of the lower bounds for all the supplies is no less than the sum of the upper bounds for all the demands; and a heuristic algorithm named TPVDS-A based on genetic algorithm is developed as an efficient and robust solution method of the model. Computational experiments on benchmark and new randomly generated instances show that the TPVDS-A algorithm outperforms the two existing approaches.     

A refined algorithm for maximum independent set in degree-4 graphs

The maximum independent set problem is one of the most important problems in theoretical analysis on time and space complexities of exact algorithms. Theoretical improvement on upper bounds on time complexity to solve this problem in low-degree graphs can lead to an improvement on that to the problem in general graphs. In this paper, we derive an upper bound \(O^*(1.1376^n)\) on the time complexity of a polynomial-space algorithm that solves the maximum independent set problem in an n-vertex graph with degree bounded by 4, improving all previous upper bounds on the time complexity of exact algorithms to this problem. Our algorithm is a branch-and-reduce algorithm and analyzed by using the measure-and-conquer method. To make an amortized analysis of the running time bound, we use an idea of “shift” to save some decrease of the measure from good branches to bad branches. Our algorithm first deals with small vertex cuts and vertices of degree \({\ge }5\), which may be created in our algorithm even if the input graph has maximum degree 4, then eliminates cycles of length 3 and 4 containing degree-4 vertices, and finally branches on degree-4 vertices. We invoke an exact algorithm for this problem in graphs with maximum degree 3 directly when the graph has no vertices of degree \({\ge }4\). Branching on degree-4 vertices on special local structures will be the bottleneck case, and we carefully design rules of choosing degree-4 vertices to branch on so that the resulting instances after branching decrease the measure effectively in the next step.     

LOT-SIZING IN CAPACITATED MULTI-STAGE SERIAL SYSTEMS

The lot-sizing problem in capacitated multi-stage systems with a serial product structure is addressed. This is a complex optimization problem that is part of the decision set in material requirements planning (MRP) systems. The mathematical model that describes the problem uses the concept of echelon stock and includes lead times. Setup times are taken into account, which implies that the problem of finding a feasible solution is NP-Complete. This paper proposes a heuristic method that provides a production plan in order to minimize inventory, production, and setup costs. The heuristic starts from a solution for the uncapacitated problem, which is given by the sequential application of the Wagner-Whitin algorithm. Feasibility is then attempted by shifting production amounts between periods. Computational tests conducted in 1,800 instances with up to 40 components and 18 periods have shown that feasible solutions were obtained in 83.7% of the instances. For the infeasible instances, on average, the heuristic is able to find solutions with very low capacity excess. The solutions' quality is evaluated through a lower bound provided by Lagrangean relaxation and on average the gap is less than 10%.     

The maximum dispersion problem

In the maximum dispersion problem, a given set of objects has to be partitioned into a number of groups. Each object has a non-negative weight and each group has a target weight, which may be different for each group. In addition to meeting the target weight of each group, all objects assigned to the same group should be as dispersed as possible with respect to some distance measure between pairs of objects. Potential applications for this problem come from such diverse fields as the problem of creating study groups or the design of waste collection systems. We develop and compare two different (mixed-) integer linear programming formulations for the problem. We also study a specific relaxation that enables us to derive tight bounds that improve the effectiveness of the formulations. Thereby, we obtain an upper bound by finding in an auxiliary graph subsets of given size with minimal diameter. A lower bound is derived based on the relation of the optimal solution of the relaxation to the chromatic number of a series of auxiliary graphs. Finally, we propose an exact solution scheme for the maximum dispersion problem and present extensive computational experiments to assess its efficiency.     

Branch-and-Bound Strategies for the Log Bucking Problem

Tree bucking is the initial production process in converting felled trees into useable wood products. This process has been previously modelled as a dynamic programming problem. Unlike other production problems that have been modelled as dynamic programming problems, there have been no serious attempts to formulate this problem as a branch-and-bound model and then examine the model's performance. This research develops the tree bucking problem as a branch-and-bound model to be tested by varying several parameters. The testing is performed in two phases: (1) a sensitivity analysis is performed to test two key parameters used by the model, and (2) branching strategies are tested on various problem scenarios. The size of the solution sets searched by the technique vary from as low as 40 to as many as 41,000 possible combinations.     

Some inverse min-max network problems under weighted l1 and l∞ norms with bound constraints on changes

We consider some inverse min-max (or max-min) network problems. Such an inverse problem is to modify the weights with bound constraints so that a given feasible solution becomes an optimal solution of a min-max (or max-min) network problem, and the deviation of the weights, measured by the weighted l ₁ norm or weighted l _∞ norm, is minimum. In this paper, we present strongly polynomial time algorithms to solve the inverse min-max spanning tree problem and the inverse maximum capacity path problem.     

A best first search exact algorithm for the Multiple-choice Multidimensional Knapsack Problem

In this paper, we propose an optimal algorithm for the Multiple-choice Multidimensional Knapsack Problem MMKP. The main principle of the approach is twofold: (i) to generate an initial feasible solution as a starting lower bound, and (ii) at different levels of the search tree to determine an intermediate upper bound obtained by solving an auxiliary problem called MMKP_aux and perform the strategy of fixing items during the exploration. The approach which we develop is of best-first search strategy. The method was able to optimally solve the MMKP. The performance of the exact algorithm is evaluated on a set of small and medium instances, some of them are extracted from the literature and others are randomly generated. This algorithm is parallelizable and it is one of its important feature.     

Approximate and Exact Algorithms for Constrained (Un) Weighted Two-dimensional Two-staged Cutting Stock Problems

In this paper we propose two algorithms for solving both unweighted and weighted constrained two-dimensional two-staged cutting stock problems. The problem is called two-staged cutting problem because each produced (sub)optimal cutting pattern is realized by using two cut-phases. In the first cut-phase, the current stock rectangle is slit down its width (resp. length) into a set of vertical (resp. horizontal) strips and, in the second cut-phase, each of these strips is taken individually and chopped across its length (resp. width).First, we develop an approximate algorithm for the problem. The original problem is reduced to a series of single bounded knapsack problems and solved by applying a dynamic programming procedure. Second, we propose an exact algorithm tailored especially for the constrained two-staged cutting problem. The algorithm starts with an initial (feasible) lower bound computed by applying the proposed approximate algorithm. Then, by exploiting dynamic programming properties, we obtain good lower and upper bounds which lead to significant branching cuts. Extensive computational testing on problem instances from the literature shows the effectiveness of the proposed approximate and exact approaches.     

A lower bound for the adaptive two-echelon capacitated vehicle routing problem

Adaptive two-echelon capacitated vehicle routing problem (A2E-CVRP) proposed in this paper is a variant of the classical 2E-CVRP. Comparing to 2E-CVRP, A2E-CVRP has multiple depots and allows the vehicles to serve customers directly from the depots. Hence, it has more efficient solution and adapt to real-world environment. This paper gives a mathematical formulation for A2E-CVRP and derives a lower bound for it. The lower bound is used for deriving an upper bound subsequently, which is also an approximate solution of A2E-CVRP. Computational results on benchmark instances show that the A2E-CVRP outperforms the classical 2E-CVRP in the costs of routes.     

Blocking Rumor by Cut

In this paper, a rumor blocking problem is studied with an objective function which is neither submodular or supermodular. We will prove that this problem is NP-hard and give a data-dependent approximation with sandwich method. In addition, we show that every set function has a pair of monotone nondecreasing modular functions as upper bound and lower bound, respectively.     

Allocation of Returned Products among Different Recovery Options through an Opportunity Cost–Based Dynamic Approach*

In a make‐to‐order product recovery environment, we consider the allocation decision for returned products decision under stochastic demand of a firm with three options: refurbishing to resell, parts harvesting, and recycling. We formulate the problem as a multiperiod Markov decision process (MDP) and present a linear programming (LP) approximation that provides an upper bound on the optimal objective function value of the MDP model. We then present two solution approaches to the MDP using the LP solution: a static approach that uses the LP solution directly and a dynamic approach that adopts a revenue management perspective and employs bid‐price controls technique where the LP is resolved after each demand arrival. We calculate the bid prices based on the shadow price interpretation of the dual variables for the inventory constraints and accept a demand if the marginal value is higher than the bid price. Since the need for solving the LP at each demand arrival requires a very efficient solution procedure, we present a transportation problem formulation of the LP via variable redefinitions and develop a one‐pass optimal solution procedure for it. We carry out an extensive numerical analysis to compare the two approaches and find that the dynamic approach provides better performance in all of the tested scenarios. Furthermore, the solutions obtained are within 2% of the upper bound on the optimal objective function value of the MDP model.     

SOLUTION OF THE SHORTEST ROUTE PROBLEM USING THE ASSIGNMENT TECHNIQUE

A solution to the shortest route problem of going from city i to city j with p necessary intermediate stops (0 p n - 2) is given using the assignment algorithm, with a simple modification of the initial matrix. A branch and bound algorithm is necessary in all but the simplest case (p = 0).     

Solving constrained optimization problems by solution-based decomposition search

Solving constrained optimization problems (COPs) is a challenging task. In this paper we present a new strategy for solving COPs called solve and decompose (or \( S \& D\) for short). The proposed strategy is a systematic iterative depth-first strategy that is based on problem decomposition. \( S \& D\) uses a feasible solution of the COP, found by any exact method, to further decompose the original problem into a bounded number of subproblems which are considerably smaller in size. It also uses the value of the feasible solution as a bound that we add to the created subproblems in order to strengthen the cost-based filtering. Furthermore, the feasible solution is exploited in order to create subproblems that have more promise in finding better solutions which are explored in a depth-first manner. The whole process is repeated until we reach a specified depth where we do not decompose the subproblems anymore but we solve them to optimality using any exact method like Branch and Bound. Our initial results on two benchmark problems show that \( S \& D\) may reach improvements of up to three orders of magnitude in terms of runtime when compared to Branch and Bound.     

Dynamic Programming and Hill-Climbing Techniques for Constrained Two-Dimensional Cutting Stock Problems

In this paper we propose an algorithm for the constrained two-dimensional cutting stock problem (TDC) in which a single stock sheet has to be cut into a set of small pieces, while maximizing the value of the pieces cut. The TDC problem is NP-hard in the strong sense and finds many practical applications in the cutting and packing area. The proposed algorithm is a hybrid approach in which a depth-first search using hill-climbing strategies and dynamic programming techniques are combined. The algorithm starts with an initial (feasible) lower bound computed by solving a series of single bounded knapsack problems. In order to enhance the first-level lower bound, we introduce an incremental procedure which is used within a top-down branch-and-bound procedure. We also propose some hill-climbing strategies in order to produce a good trade-off between the computational time and the solution quality. Extensive computational testing on problem instances from the literature shows the effectiveness of the proposed approach. The obtained results are compared to the results published by Alvarez-Valdés et al. (2002).     

具有遗憾值约束的鲁棒供应链网络设计模型研究

考虑不确定性环境,研究战略层次的供应链网络鲁棒设计问题,目标是设计参数发生摄动时,供应链性能能够保持稳健性。基于鲁棒解的定义,建立从上游供应商选择到下游设施选址-需求分配的供应链网络设计鲁棒优化模型;提出确定遗憾值限定系数上限和下限的方法,允许决策者调节鲁棒水平,选择多种供应链网络结构;通过模型分解与协调,设计了供应链节点配置的禁忌搜索算法。算例的计算结果表明了禁忌搜索算法具有良好的收敛特性,以及在处理大规模问题上的优越性;同时也反映了利用鲁棒优化模型进行供应链网络设计,可以有效规避投资风险。