A simple algorithm for the source-induced fixed-charge transportation problem

The fixed-charge problem is a non-linear programming problem of practical interest in business and industry. The source-induced fixed-charge transportation problem (SIFCTP) is a variation of the regular fixed-charge transportation problem (FCTP) in which a fixed cost is incurred for every supply point that is used in the solution, along with a variable cost that is proportional to the amount shipped. This problem is significantly different from the widely studied FCTP, where a fixed cost is incurred upon activation of a route. The introduction of the fixed costs in addition to variable costs results in the objective function being a step function. Therefore, fixed-charge problems are usually solved using sophisticated analytical or computer software. This paper deviates from that approach. It presents a computationally simple algorithm for the solution of source-induced fixed-charge problems. The results of empirical tests of the effectiveness of the proposed algorithm are presented.     

A Simple Algorithm for Solving Small,Fixed-Charge Transportation Problems

The solution of the classical transportation problem (as generally presented) can be mastered very quickly. The fixed-charge problem is another matter. The reason is that the introduction of fixed costs in addition to variable costs results in the objective function being a step function. Fixed-charge problems are usually solved, therefore, by using sophisticated computer software. This paper deviates from that approach. It presents a low-tech. algorithm for the solution of small, fixed-charge problems.     

Using convex envelopes to solve the interactive fixed-charge linear programming problem

In the well-known fixed-charge linear programming problem, it is assumed, for each activity, that the value of the fixed charge incurred when the level of the activity is positive does not depend upon which other activities, if any, are also undertaken at a positive level. However, we have encountered several practical problems where this assumption does not hold. In an earlier paper, we developed a new problem, called the interactive fixed-charge linear programming problem (IFCLP), to model these problems. In this paper, we show how to construct the convex envelopes and other convex underestimating functions for the objective function for problem (IFCLP) over various rectangular subsets of its domain. Using these results, we develop a specialized branch-and-bound algorithm for problem (IFCLP) which finds an exact optimal solution for the problem in a finite number of steps. We also discuss the main properties of this algorithm.The authors would like to thank an anonymous referee for his helpful suggestions.     

A cutting plane procedure for the travelling salesman problem on road networks

A cutting plane algorithm for the exact solution of the symmetric travelling salesman problem (TSP) is proposed. The real tours on a usually incomplete road network, which are in general non-Hamiltonian, are characterized directly by an integer linear programming model. The algorithm generates special cutting planes for this model. Computational results for real road networks with up to 292 visiting places are reported, as well as for classical problems of the literature with up to 120 cities. Some of the latter problems have been solved for the first time with a pure cutting plane approach.     

An integrated approach to the one-dimensional cutting stock problem in coronary stent manufacturing

This paper presents a two-stage approach for pattern generation and cutting plan determination of the one-dimensional cutting stock problem. Calculation of the total number of patterns that will be cut and generation of the cutting patterns are performed in the first stage. On the other hand, the second stage determines the cutting plan. The proposed approach makes use of two separate integer linear programming models. One of these models is employed by the first stage to generate the cutting patterns through a heuristic procedure with the objective of minimizing trim loss. The cutting patterns obtained from Stage 1 are then fed into the second stage. In this stage, another integer linear programming model is solved to form a cutting plan. The objective of this model is to minimize a generalized total cost function consisting of material inputs, number of setups, labor hours and overdue time; subject to demand requirements, material availability, regular and overtime availability, and due date constraints. The study also demonstrates an implementation of the proposed approach in a coronary stent manufacturer. The case study focuses on the cutting phase of the manufacturing process followed by manual cleaning and quality control activities. The experiments show that the proposed approach is suitable to the conditions and requirements of the company.     

A bi-objective coordination setup problem in a two-stage production system

This paper addresses a problem arising in the coordination between two consecutive departments of a production system, where parts are processed in batches, and each batch is characterized by two distinct attributes. Due to the lack of interstage buffering between the two stages, these departments have to follow the same batch sequence. In the first department, a setup occurs every time the first attribute of a new batch is different from the one of the previous batch. In the downstream department, there is a setup when the second attribute changes in two consecutive batches. The problem consists in finding a batch sequence optimizing the number of setups paid by each department. This case results in a particular bi-objective combinatorial optimization problem. We present a geometrical characterization for the feasible solution set of the problem, and we propose three effective heuristics, as shown by an extensive experimental campaign. The proposed approach can be also used to solve a class of single-objective problems, in which setup costs in the two departments are general increasing functions of the number of setups.     

An algebraic geometry algorithm for scheduling in presence of setups and correlated demands

We study here a problem of schedulingn job types onm parallel machines, when setups are required and the demands for the products are correlated random variables. We model this problem as a chance constrained integer program.Methods of solution currently available—in integer programming and stochastic programming—are not sufficient to solve this model exactly. We develop and introduce here a new approach, based on a geometric interpretation of some recent results in Gröbner basis theory, to provide a solution method applicable to a general class of chance constrained integer programming problems.Out algorithm is conceptually simple and easy to implement. Starting from a (possibly) infeasible solution, we move from one lattice point to another in a monotone manner regularly querying a membership oracle for feasibility until the optimal solution is found. We illustrate this methodology by solving a problem based on a real system.Corresponding author.     

Solving one-dimensional cutting stock problems exactly with a cutting plane algorithm

When solving the one-dimensional cutting stock problem (1D CSP) as an integer linear programming problem one has to overcome computational difficulties arising from the integrality condition and a huge number of variables. In the Gilmore–Gomory approach the corresponding continuous relaxation is solved via column generation techniques followed by an appropriate rounding of the in general non-integer solution. Obviously, there is no guarantee of obtaining an optimal solution in this way but it is extremely effective in practice. However, in two- and three-dimensional cutting stock problems the heuristics are not so good which necessitates the research of effective exact methods. In this paper we present an exact solution approach for the 1D CSP which is based on a combination of the cutting plane method and the column generation technique. Results of extensive computational experiments are reported.     

Finding and identifying optimal inventory levels for systems with common components

In this article, we consider the problem of finding the optimal inventory level for components in an assembly system where multiple products share common components in the presence of random demand. Previously, solution procedures that identify the optimal inventory levels for components in a component commonality problem have been considered for two product or one common component systems. We will here extend this to a three products system considering any number of common components. The inventory problem considered is modeled as a two stage stochastic recourse problem where the first stage is to set the inventory levels to maximize expected profit while the second stage is to allocate components to products after observing demand. Our main contribution, and the main focus of this paper, is the outline of a procedure that finds the gradient for the stochastic problem, such that an optimal solution can be identified and a gradient based search method can be used to find the optimal solution.     

The Application of Preprocessing and Cutting Plane Techniques for a Class of Production Planning Problems

This paper investigates properties of integer programming models for a class of production planning problems. The models are developed within a decision support system to advise a sales team of the products on which to focus their efforts in gaining new orders in the short term. The products generally require processing on several manufacturing cells and involve precedence relationships. The cells are already (partially) committed with products for stock and to satisfy existing orders and therefore only the residual capacities of each cell in each time period of the planning horizon are considered. The determination of production recommendations to the sales team that make use of residual capacities is a nontrivial optimization problem. Solving such models is computationally demanding and techniques for speeding up solution times are highly desirable. An integer programming model is developed and various preprocessing techniques are investigated and evaluated. In addition, a number of cutting plane approaches have been applied. The performance of these approaches which are both general and application specific is examined.     

Setup minimising conditions in the trim loss problem

The one-dimensional cutting stock, trim or deckling problem arises in cutting short units from long ones. The long units could be pipes, rods or reels of paper. The objectives are to fill demand with as little stock as possible, to reduce trim waste and to keep the number of setups to a minimum.We examine a formal approach to setup minimization and show that, at best, it provides necessary conditions for solving this task. Sufficient conditions also require the generation of all possible patterns, in principle at least.     

Selective Gram–Schmidt orthonormalization for conic cutting surface algorithms

It is not straightforward to find a new feasible solution when several conic constraints are added to a conic optimization problem. Examples of conic constraints include semidefinite constraints and second order cone constraints. In this paper, a method to slightly modify the constraints is proposed. Because of this modification, a simple procedure to generate strictly feasible points in both the primal and dual spaces can be defined. A second benefit of the modification is an improvement in the complexity analysis of conic cutting surface algorithms. Complexity results for conic cutting surface algorithms proved to date have depended on a condition number of the added constraints. The proposed modification of the constraints leads to a stronger result, with the convergence of the resulting algorithm not dependent on the condition number. Research supported in part by NSF grant number DMS-0317323. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect the views of the National Science Foundation.     

A multi-parametric programming approach for multilevel hierarchical and decentralised optimisation problems

In this paper, we outline the foundations of a general global optimisation strategy for the solution of multilevel hierarchical and general decentralised multilevel problems, based on our recent developments on multi-parametric programming and control theory. The core idea is to recast each optimisation subproblem, present in the hierarchy, as a multi-parametric programming problem, with parameters being the optimisation variables belonging to the remaining subproblems. This then transforms the multilevel problem into single-level linear/convex optimisation problems. For decentralised systems, where more than one optimisation problem is present at each level of the hierarchy, Nash equilibrium is considered. A three person dynamic optimisation problem is presented to illustrate the mathematical developments.     

Approximate and exact algorithms for the fixed-charge knapsack problem

The subject of this paper is the formulation and solution of a variation of the classical binary knapsack problem. The variation that is addressed is termed the “fixed-charge knapsack problem”, in which sub-sets of variables (activities) are associated with fixed costs. These costs may represent certain set-ups and/or preparations required for the associated sub-set of activities to be scheduled. Several potential real-world applications as well as problem extensions/generalizations are discussed. The efficient solution of the problem is facilitated by a standard branch-and-bound algorithm based on (1) a non-iterative, polynomial algorithm to solve the LP relaxation, (2) various heuristic procedures to obtain good candidate solutions by adjusting the LP solution, and (3) powerful rules to peg the variables. Computational experience shows that the suggested branch-and-bound algorithm shows excellent potential in the solution of a wide variety of large fixed-charge knapsack problems.     

Integrating SQP and Branch-and-Bound for Mixed Integer Nonlinear Programming

This paper considers the solution of Mixed Integer Nonlinear Programming (MINLP) problems. Classical methods for the solution of MINLP problems decompose the problem by separating the nonlinear part from the integer part. This approach is largely due to the existence of packaged software for solving Nonlinear Programming (NLP) and Mixed Integer Linear Programming problems.In contrast, an integrated approach to solving MINLP problems is considered here. This new algorithm is based on branch-and-bound, but does not require the NLP problem at each node to be solved to optimality. Instead, branching is allowed after each iteration of the NLP solver. In this way, the nonlinear part of the MINLP problem is solved whilst searching the tree. The nonlinear solver that is considered in this paper is a Sequential Quadratic Programming solver.A numerical comparison of the new method with nonlinear branch-and-bound is presented and a factor of up to 3 improvement over branch-and-bound is observed.     

A branch-and-cut-and-price algorithm for one-dimensional stock cutting and two-dimensional two-stage cutting

The one-dimensional cutting stock problem (1D-CSP) and the two-dimensional two-stage guillotine constrained cutting problem (2D-2CP) are considered in this paper. The Gilmore–Gomory models of these problems have very strong continuous relaxations providing a good bound in an LP-based solution approach. In recent years, there have been several efforts to attack the one-dimensional problem by LP-based branch-and-bound with column generation (called branch-and-price) and by general-purpose Chvátal–Gomory cutting planes. In this paper we investigate a combination of both approaches, i.e., the LP relaxation at each branch-and-price node is strengthened by Chvátal–Gomory and Gomory mixed-integer cuts. The branching rule is that of branching on variables of the Gilmore–Gomory formulation. Tests show that, for 1D-CSP, general-purpose cuts are useful only in exceptional cases. However, for 2D-2CP their combination with branching is more effective than either approach alone and mostly better than other methods from the literature.     

Analysis of some greedy algorithms for the single-sink fixed-charge transportation problem

The single-sink fixed-charge transportation problem (SSFCTP) consists of finding a minimum cost flow from a number of nodes to a single sink. Beside a cost proportional to the amount shipped, the flow cost encompass a fixed charge. The SSFCTP is an important subproblem of the well-known fixed-charge transportation problem. Nevertheless, just a few methods for solving this problem have been proposed in the literature. In this paper, some greedy heuristic solutions methods for the SSFCTP are investigated. It is shown that two greedy approaches for the SSFCTP known from the literature can be arbitrarily bad, whereas an approximation algorithm proposed in the literature for the binary min-knapsack problem has a guaranteed worst case bound if adapted accordingly to the case of the SSFCTP.     

The stochastic trim-loss problem

The cutting stock problem (CSP) is one of the most fascinating problems in operations research. The problem aims at determining the optimal plan to cut a number of parts of various length from an inventory of standard-size material so to satisfy the customers demands. The deterministic CSP ignores the uncertain nature of the demands thus typically providing recommendations that may result in overproduction or in profit loss. This paper proposes a stochastic version of the CSP which explicitly takes into account uncertainty. Using a scenario-based approach, we develop a two-stage stochastic programming formulation. The highly non-convex nature of the model together with its huge size prevent the application of standard software. We use a solution approach designed to exploit the specific problem structure. Encouraging preliminary computational results are provided.     

A facility neighborhood search heuristic for capacitated facility location with single-source constraints and flexible demand

We consider a generalization of the well-known capacitated facility location problem with single source constraints in which customer demand contains a flexible dimension. This work focuses on providing fast and practically implementable optimization-based heuristic solution methods for very large scale problem instances. We offer a unique approach that utilizes a high-quality efficient heuristic within a neighborhood search to address the combined assignment and fixed-charge structure of the underlying optimization problem. We also study the potential benefits of combining our approach with a so-called very large-scale neighborhood search (VLSN) method. As our computational test results indicate, our work offers an attractive solution approach that can be tailored to successfully solve a broad class of problem instances for facility location and similar fixed-charge problems.     

The one-dimensional cutting stock problem with due dates

The one-dimensional cutting stock problem is the problem of cutting stock material into shorter lengths, in order to meet demand for these shorter lengths while minimizing waste. In industrial cutting operations, it may also be necessary to fill the orders for these shorter lengths before a given due date. We propose new optimization models and solution procedures which solve the cutting stock problem when orders have due dates. We evaluate our approach using data from a large manufacturer of reinforcement steel and show that we are able to solve industrial-size problems, while also addressing common cutting considerations such as aggregation of orders, multiple stock lengths and cutting different types of material on the same machine. In addition, we evaluate operational performance in terms of resulting waste and tardiness of orders using our model in a rolling horizon framework.