Search

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.ejor.2005.04.050 Byline: Rainer E. Burkard Keywords: Monge property; Transportation problem; Greedy algorithm; Discrete convexity; Bounding probability distribution functions Abstract: Starting from Monge's mass transportation problem we review the role Monge properties play in optimization. In particular we discuss transportation problems whose cost functions fulfill a Monge property, Monge sequences, algebraic Monge properties, the recognition of permuted Monge arrays and multidimensional Monge arrays and the connections between Monge properties and discrete convexity. Finally we discuss Prekopa's recent approach using Monge arrays in bounding multivariate probability distribution functions. Author Affiliation: Institut fur Mathematik B, Graz University of Technology, Steyrergasse 30, A-8010 Graz, Austria Article History: Received 20 December 2004; Accepted 22 April 2005 Article Note: (footnote) [star] The author acknowledges financial support by the Spezialforschungsbereich F 003 'Optimierung und Kontrolle', Projektbereich Diskrete Optimierung.

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.ejor.2005.03.011 Byline: Rainer E. Burkard, Johannes Hatzl Keywords: Scheduling problems; Batch production systems; Makespan minimization; Heuristics Abstract: In this paper we investigate a heuristic for batch processing problems occurring in the chemical industry, where the objective is to minimize the makespan. Usually, this kind of problem is solved using mixed-integer linear programs. However, due to the large number of binary variables good results within a reasonable computational time could only be obtained for small instances. We propose an iterative construction algorithm which alternates between construction and deconstruction phases. Moreover, we suggest diversification and intensification strategies in order to obtain good suboptimal solutions within moderate running times. Computational results show the power of this algorithm. Author Affiliation: Institute of Optimization, Dynamical Systems and Discrete Mathematics, Graz University of Technology, Steyrergasse 30, A-8010 Graz, Austria Article History: Received 17 August 2004; Accepted 16 March 2005 Article Note: (footnote) [star] This research has been financially supported by the Spezialforschungsbereich F 302 'Optimierung und Kontrolle', Projektbereich Kombinatorische Optimierung komplexer Systeme.

Capacity expansion problems (CEPs) and weight reduction problems (WRPs) are considered in connection with bottleneck optimization problems. It is shown that WRP can be reformulated as a parametric combinatorial optimization problem.

A branch and bound procedure for solving the quadratic assignment problem, otherwise known as minimax assignment problem on tree networks, is introduced. The problem involves the minimization of the maximum intermediate traffic by optimizing the message routing pattern and the embedding of the communication centers. Depending on whether the solution is based on the single-path of fractional model, it is NP-complete even for the case of paths, cycles, doublestars and stars of branch length three.

The inverse-parametric knapsack problem is analyzed wherein the costs of a knapsack problem are replaced by linear functions in a parameter t. A value for t is then needed to make the optimal solution of the knapsack problem equal to a given solution value. Pseudopolynomial algorithms were derived for the inverse-parametric problem. Sample applications show that straight-forward methods perform better than pseudopolynomial algorithms.

Heuristic methods for biquadratic assignment problems (BiQAP) are discussed. These include pair exchange algorithms, variants of simulated annealing and taboo search. These methods were translated into C codes for testing on BiQAP instances with known solutions. Results show that the third version of simulated annealing provides the lowest value of relative error compared to the other heuristics.

A special case of the traveling salesman problem (TSP) is considered where optimization is done over a specially structured set of permutations, which are represented by a given PQ-tree. For PQ-trees whose maximum degree is bounded by a constant, the special case of the TSP is shown to be solvable in polynomial time. The results can be applied to the Bottleneck version of the TSP and to the general algebraic TSP.