The teacher assignment problem: A special case of the fixed charge transportation problem

A basic model of the task of assigning classes to professors, in such a way that the average number of distinct subjects assigned to each professor is minimized, is formulated as a mixed integer program. It turns out that the problem is a special case of the fixed charge transportation problem which in some cases corresponds to finding a basic solution of a transportation problem which is as degenerate as possible. We present an equivalent alternative formulation of the problem which makes it easy to prove that it is NP-hard in the strong sense and an exact branch and bound algorithm for its solution based on this alternative formulation is outlined. Computational experiments with data from a concrete problem, concludes the paper.     

Solving fixed charge transportation problem with interval parameters

In the present paper the fixed charge transportation problem under uncertainty, particularly when parameters are given in interval forms, is formulated. In this case it is assumed that both cost and constraint parameters are arrived in interval numbers. Considering two different order relations for interval numbers, two solution procedures are developed in order to obtain an optimal solution for interval fixed charge transportation problem (IFCTP). In addition, the two order relations are compared to give a better comprehension of their differences. Furthermore, numerical examples are provided to illustrate each of solution procedures.     

A column generation based decomposition algorithm for a parallel machine just-in-time scheduling problem

We propose a column generation based exact decomposition algorithm for the problem of scheduling n jobs with an unrestrictively large common due date on m identical parallel machines to minimize total weighted earliness and tardiness. We first formulate the problem as an integer program, then reformulate it, using Dantzig–Wolfe decomposition, as a set partitioning problem with side constraints. Based on this set partitioning formulation, a branch and bound exact solution algorithm is developed for the problem. In the branch and bound tree, each node is the linear relaxation problem of a set partitioning problem with side constraints. This linear relaxation problem is solved by column generation approach where columns represent partial schedules on single machines and are generated by solving two single machine subproblems. Our computational results show that this decomposition algorithm is capable of solving problems with up to 60 jobs in reasonable cpu time.     

On the structure of the fixed charge transportation problem

This work extends the theory of the fixed charge transportation problem (FCTP), currently based mostly on a forty-year-old publication by Hirsch and Danzig. This paper presents novel properties that need to be considered by those using existing, or those developing new methods for optimizing FCTP. It also defines the problem in an easier way, making it understandable to a wider spectrum of readers. While the analysis is limited to FCTP only, elements of it can easily be extended to the general fixed charge problem. Finally a novel, snap method for finding global minima for FCTPs with large fixed charge coefficients is introduced.     

Multi-item single source ordering problem with transportation cost: A Lagrangian decomposition approach

As a part of supply chain management literature and practice, it has been recognized that there can be significant gains in integrating inventory and transportation decisions. The problem we tackle here is a common one both in retail and production sectors where several items have to be ordered from a single supplier. We assume that there is a finite planning horizon to make the ordering decisions for the items, and in this finite horizon the retailer or the producer knows the demand of each item in each period. In addition to the inventory holding cost, an item-base fixed cost associated with each item included in the order, and a piecewise linear transportation cost are incurred. We suggest a Lagrangean decomposition based solution procedure for the problem and carry out numerical experiments to analyze the value of integrating inventory and transportation decisions under different scenarios.     

A bicriteria solid transportation problem with fixed charge under stochastic environment

In this paper, a bicriteria solid transportation problem with stochastic parameters is investigated. Three mathematical models are constructed for the problem, including expected value goal programming model, chance-constrained goal programming model and dependent-chance goal programming model. A hybrid algorithm is also designed based on the random simulation algorithm and tabu search algorithm to solve the models. At last, some numerical experiments are presented to show the performance of models and algorithm.     

Lagrangian formulation of domain decomposition methods: A unified theory

Domain decomposition methods based on one Lagrange multiplier have been shown to be very efficient for solving ill-conditioned problems in parallel. Several variants of these methods have been developed in the last ten years. These variants are based on an augmented Lagrangian formulation involving one or two Lagrange multipliers and on mixed type interface conditions between the sub-domains. In this paper, the Lagrangian formulations of some of these domain decomposition methods are presented both from a continuous and a discrete point of view.     

The decomposition method for a control problem for an underactuated Lagrangian system

The control problem for an underactuated Lagrangian system is considered. A system of smooth non-linear functions of the generalized coordinates is introduced into the treatment and the number of functions is equal to the number of generalized control forces. The aim of the control is to bring the system in a finite time to a terminal set specified by the level lines of the selected functions, and it is required that the motion at the terminal instant occurs along the level lines. As a result, a development and extension of Chernous’ko's decomposition method is given. This method was proposed for designing feedback control for Lagrangian systems when the number of controls in a system is equal to the number of its degrees of freedom.     

The interactive fixed charge inhomogeneous flows optimization problem

An optimization problem of interactive inhomogenous flows (Steiner multicommodity network flow problem) is formulated. The problem's main characteristic is a fixed charge change when combining multicommodity communications. In this paper we propose a method for solving this problem which, in order to restrict the search on the feasible domain, reduces the original problem to a concave programming problem in the form: min {f(x)|xX} wheref:ⁿ is a concave function, andX ₀ ⁿ is a flow polytope defined by network transportation constraints. For practical large-scale problems arising from planning transportation networks on inhomogeneous surfaces defined by a digital model, a method of local optimization over a flow polytope vertex set is proposed, which is far more effective in comparison with the Gallo and Sodini method under polytope strong degeneracy conditions.     

Lagrangian based heuristics for the multicommodity network flow problem with fixed costs on paths

We study the multicommodity network flow problem with fixed costs on paths, with specific application to the empty freight car distribution process of a rail operator. The classification costs for sending a group of cars do not depend on the number of cars in the group, as long as the group is kept together as one unit. Arcs correspond to trains, so we have capacity restrictions on arcs but fixed costs on the paths corresponding to routes for groups of cars. As solution method, we propose a Lagrangian based heuristic using dual subgradient search and primal heuristics based on path information of the Lagrangian subproblem solutions. The method illustrates several ways of exploiting the specific structures of the problem. Computational tests indicate that the method is able to generate fairly good primal feasible solutions and lower bounds on the optimal objective function value.     

The stochastic bid generation problem in combinatorial transportation auctions

In this paper, we deal with the generation of bundles of loads to be submitted by carriers participating in combinatorial auctions in the context of long-haul full truckload transportation services. We develop a probabilistic optimization model that integrates the bid generation and pricing problems together with the routing of the carrier’s fleet. We propose two heuristic procedures that enable us to solve models with up to 400 auctioned loads.     

The minimum spanning strong subdigraph problem is fixed parameter tractable

A digraph D is strong if it contains a directed path from x to y for every choice of vertices x,y in D. We consider the problem (MSSS) of finding the minimum number of arcs in a spanning strong subdigraph of a strong digraph. It is easy to see that every strong digraph D on n vertices contains a spanning strong subdigraph on at most 2n−2 arcs. By reformulating the MSSS problem into the equivalent problem of finding the largest positive integer k≤n−2 so that D contains a spanning strong subdigraph with at most 2n−2−k arcs, we obtain a problem which we prove is fixed parameter tractable. Namely, we prove that there exists an O(f(k)n^c) algorithm for deciding whether a given strong digraph D on n vertices contains a spanning strong subdigraph with at most 2n−2−k arcs.We furthermore prove that if k≥1 and D has no cut vertex then it has a kernel of order at most (2k−1)². We finally discuss related problems and conjectures.     

A column generation approach for determining optimal fleet mix,schedules, and transshipment facility locations for a vessel transportation problem

This paper presents a column generation approach for a storage replenishment transportation-scheduling problem. The problem is concerned with determining an optimal combination of multiple-vessel schedules to transport a product from multiple sources to different destinations based on demand and storage information at the destinations, along with cost-effective optimal strategic locations for temporary transshipment storage facilities. Such problems are faced by oil/trucking companies that own a fleet of vessels (oil tankers or trucks) and have the option of chartering additional vessels to transport a product (crude oil or gasoline) to customers (storage facilities or gas stations) based on agreed upon contracts. An integer-programing model that determines a minimum-cost operation of vessels based on implicitly representing feasible shipping schedules is developed in this paper. Due to the moderate number of constraints but an overwhelming number of columns in the model, a column generation approach is devised to solve the continuous relaxation of the model, which is then coordinated with a sequential fixing heuristic in order to solve the discrete problem. Computational results are presented for a range of test problems to demonstrate the efficacy of the proposed approach.     

Efficient decomposition and linearization methods for the stochastic transportation problem

The stochastic transportation problem can be formulated as a convex transportation problem with nonlinear objective function and linear constraints. We compare several different methods based on decomposition techniques and linearization techniques for this problem, trying to find the most efficient method or combination of methods. We discuss and test a separable programming approach, the Frank-Wolfe method with and without modifications, the new technique of mean value cross decomposition and the more well known Lagrangean relaxation with subgradient optimization, as well as combinations of these approaches. Computational tests are presented, indicating that some new combination methods are quite efficient for large scale problems.     

A note on column generation in Dantzig—Wolfe decomposition algorithms

A modification of the column generation operation in Dantzig—Wolfe decomposition is suggested. Instead of the usual procedure of solving one or more subproblems at each major iteration, it is shown how the subproblems may be solved parametrically in such a way as to maximize the immediate improvement in the value of objective in the master problem, rather than to maximize the reduced profit of the entering column. The parametric problem is shown to involve the maximization of a piece-wise linear concave function of a single variable. It is hoped that in some cases the use of the suggested procedure may improve the slow rates of convergence common in decomposition algorithms.     

A column generation approach for an emission-oriented vehicle routing problem on a multigraph

In this work, an emission-minimizing vehicle routing problem with heterogeneous vehicles and a heterogeneous road and traffic network is considered as it is typical in urban areas. Depending on the load of the vehicle, there exist multiple emission-minimal arcs for traveling between two locations. To solve the vehicle routing problem efficiently, a column generation approach is presented. At the core of the procedure an emission-oriented elementary shortest path problem on a multigraph is solved by a backward labeling algorithm. It is shown that the labeling algorithm can be sped up by adjusting the dual master program and by restricting the number of labels propagated in the sub-problem. The column generation technique is used to setup a fast heuristic as well as a branch-and-price algorithm. Both procedures are evaluated based on test instances with up to 100 customers. It turns out that the heuristic approach is very effective and generates near-optimal solutions with gaps below 0.1% on average while only requiring a fraction of the runtime of the exact approach.     

Natural language and the art and science of problem/opportunity formulation: a transportation planning case analysis

The formulation process has been called the most important phase of decision making, yet little is known about how this process is carried out in a group, team, or organizational context through a discussion of issues and opportunities. This paper reviews the literatures on problem/opportunity formulation, particularly as related to the use of natural language in developing collective perception. Applying a taxonomy of six linguistic structures, the formulation process of a 13-member transportation planning committee is analysed. The results of this field study suggest overall preferences for simple rather than complex linguistic structures, differentiated by member roles (leader versus non-leader). Further, exploration of the problem/opportunity-space began with a relatively broad interpretation of the problematic situation, and proceeded incrementally. Digressions from this incremental exploration increased as the process unfolded, precipitated by changes in speakers. The implications of this analysis for understanding and managing the formulation process, as well as for future research, are discussed.     

Mixed-integer column generation algorithms and the probabilistic maximum satisfiability problem

The column generation approach to large-scale linear programming is extended to the mixed-integer case. Two general algorithms, a dual and a primal one, are presented. Both involve finding k-best solutions to combinatorial optimization subproblems. Algorithms for these subproblems must be tailored to each specific application. Their use is illustrated by applying them to a new combinatorial optimization problem with applications in Artificial Intelligence: Probabilistic Maximum Satisfiability. This problem is defined as follows: consider a set of logical sentences together with probabilities that they are true, assume this set of sentences is not satisfiable in the probabilistic sense, i.e., there is no probability distribution on the set of possible worlds (truth assignments to the sentences corresponding to at least one truth assignment to the logical variables they contain) such that for each sentence the sum of probabilities of the possible worlds in which it is true is equal to its probability of being true; determine a minimum set of sentences to be deleted in order to make the remaining set of sentences satisfiable. Computational experience with both algorithms is reported on.     

A linear-time algorithm for the bottleneck transportation problem with a fixed number of sources

We investigate a special case of the bottleneck transportation problem where the number s of sources is bounded by a constant and not part of the input. For the subcase s=2, a best-possible linear-time algorithm has been derived by Varadarajan [Oper. Res. Lett. 10 (1991) 525–529]. In this note we show that for any fixed number s⩾1, the bottleneck transportation problem with s sources can be solved in linear-time. The algorithm is conceptually simple, and easy to implement.     

The value function of a transportation problem

We investigate the value of an optimal transportation problem with the maximization objective as a function of costs and vectors of production and consumption. The value is concave in production. For generic costs, the numbers of linearity domains and peak points are independent of costs and consumption. The peak points are determined by an auxiliary assignment problem. The volumes of the linearity domains are independent of costs while their dependence on consumption can be expressed via the multinomial distribution.