A note on symmetry reduction for circular traveling tournament problems

The traveling tournament problem (TTP) consists of finding a distance-minimal double round-robin tournament where the number of consecutive breaks is bounded. Easton et al. (2001) introduced the so-called circular TTP instances, where venues of teams are located on a circle. The distance between neighboring venues is one, so that the distance between any pair of teams is the distance on the circle. It is empirically proved that these instances are very hard to solve due to the inherent symmetry. This note presents new ideas to cut off essentially identical parts of the solution space. Enumerative solution approaches, e.g. relying on branch-and-bound, benefit from this reduction. We exemplify this benefit by modifying the DFS∗ algorithm of Uthus et al. (2009) and show that speedups can approximate factor 4n.     

The timetable constrained distance minimization problem

We define the timetable constrained distance minimization problem (TCDMP) which is a sports scheduling problem applicable for tournaments where the total travel distance must be minimized. The problem consists of finding an optimal home-away assignment when the opponents of each team in each time slot are given. We present an integer programming, a constraint programming formulation and describe two alternative solution methods: a hybrid integer programming/constraint programming approach and a branch and price algorithm. We test all four solution methods on benchmark problems and compare the performance. Furthermore, we present a new heuristic solution method called the circular traveling salesman approach (CTSA) for solving the traveling tournament problem. The solution method is able to obtain high quality solutions almost instantaneously, and by applying the TCDMP, we show how the solutions can be further improved.     

Level‐based heuristics and hill climbing for the antibandwidth maximization problem

The antibandwidth maximization problem aims to maximize the minimum distance of entries of a sparse symmetric matrix from the diagonal and as such may be regarded as the dual of the well‐known bandwidth minimization problem. In this paper, we consider the feasibility of adapting heuristic algorithms for the bandwidth minimization problem to the antibandwidth maximization problem. In particular, using an inexpensive level‐based heuristic, we obtain an initial ordering that we refine using a hill‐climbing algorithm. This approach performs well on matrices coming from a range of practical problems with an underlying mesh. Comparisons with existing approaches show that, on this class of problems, our algorithm can be competitive with recently reported results in terms of quality while being significantly faster and applicable to much larger problems. Copyright © 2012 John Wiley & Sons, Ltd.     

A polynomial-time algorithm to find an equitable home-away assignment

We propose a polynomial-time algorithm to find an equitable home-away assignment for a given timetable of a round-robin tournament. Our results give an answer to a problem raised by Elf et al. (Oper. Res. Lett. 31 (2003) 343), which concerns the computational complexity of the break minimization problem in sports timetabling.     

Fuzzy goal programming models for analyzing demand coverage

The main objective of demand coverage models is to locate servers so that a given demand space is appropriately covered. Most existing models assume that demand is located at specific points within an area and that coverage is evaluated by certain quantifiable criteria. However, in realistic applications, the concept of coverage may also include qualitative aspects. Moreover, the location of the servers may be determined on the basis of more than one objective. In this paper, we present a number of fuzzy goal programming models for demand coverage. We consider three objectives: (a) maximization of total coverage, (b) maximization of minimum coverage, and (c) minimization of distance to servers of uncovered demand points. Through a series of realistic problem instances, we demonstrate that the proposed models provide satisfactory solutions with respect to all three objectives.     

信息熵增量最小化准则在供应链中的应用

本文研究了在考虑利润最大化准则和信息熵增量最小准则下，既能满足了利润最大化，又要增加利润可得性，销售商如何确定订购量的问题。数字实验表明：考虑双重准则得到的策略比仅考虑利润最大化准则得到的策略更好，可以使供应链、销售商及制造商都受益。     

Performance guarantees of greedy algorithms for the problems on hereditary systems

Under study are the problems of maximization and minimization of additive functions on hereditary systems which generalize many computationally hard combinatorial optimization problems. A performance guarantee of the greedy algorithm is proven in terms of the parameters of a feasible set and the objective function of the maximization problem. This bound improves the well-known Jenkyns—Korte—Hausmann bound. An analogous result is obtained for the minimization problem of an additive function on a hereditary system.     

Nonlinear bipartite matching

We study the problem of optimizing nonlinear objective functions over bipartite matchings. While the problem is generally intractable, we provide several efficient algorithms for it, including a deterministic algorithm for maximizing convex objectives, approximative algorithms for norm minimization and maximization, and a randomized algorithm for optimizing arbitrary objectives.     

Capacitated location allocation problem with stochastic location and fuzzy demand: A hybrid algorithm

In this article, a capacitated location allocation problem is considered in which the demands and the locations of the customers are uncertain. The demands are assumed fuzzy, the locations follow a normal probability distribution, and the distances between the locations and the customers are taken Euclidean and squared Euclidean. The fuzzy expected cost programming, the fuzzy β-cost minimization model, and the credibility maximization model are three types of fuzzy programming that are developed to model the problem. Moreover, two closed-form Euclidean and squared Euclidean expressions are used to evaluate the expected distance between customers and facilities. In order to solve the problem at hand, a hybrid intelligent algorithm is applied in which the simplex algorithm, fuzzy simulation, and a modified genetic algorithm are integrated. Finally, in order to illustrate the efficiency of the proposed hybrid algorithm, some numerical examples are presented.     

Sign reversion approach to concave minimization problems

We consider a problem of minimization of a concave function subject to affine constraints. By using sign reversion techniques we show that the initial problem can be transformed into a family of concave maximization problems. This property enables us to suggest certain algorithms based on the parametric dual optimization problem.     

Heuristic procedures for the single facility inspection problem with minimal repair and increasing failure rate

This paper presents the problem of setting inspection schedules for a single imperfect facility undergoing minimal repair once detected in an ‘out-of-control’ state. The problem is modelled under a non-Markovian failure mechanism with increasing failure rate. We show that the profit maximization formulation of the problem is equivalent to the cost minimization formulation and concentrate on the latter. We then develop three heuristic procedures that are shown to be very cost effective based on the results of the numerical examples used for illustration.     

A new branch-and-price algorithm for the traveling tournament problem

The traveling tournament problem (ttp) consists of finding a distance-minimal double round-robin tournament where the number of consecutive breaks is bounded. For solving the problem exactly, we propose a new branch-and-price approach. The starting point is a new compact formulation for the ttp. The corresponding extensive formulation resulting from a Dantzig-Wolfe decomposition is identical to one given by Easton, K., Nemhauser, G., Trick, M., 2003. Solving the traveling tournament problem: a combined interger programming and constraint programming approach. In: Burke, E., De Causmaecker, P. (Eds.), Practice and Theory of Automated Timetabling IV, Volume 2740 of Lecture Notes in Computer Science, Springer Verlag Berlin/Heidelberg, pp. 100–109, who suggest to solve the tour-generation subproblem by constraint programming. In contrast to their approach, our method explicitly utilizes the network structure of the compact formulation: First, the column-generation subproblem is a shortest-path problem with additional resource and task-elementarity constraints. We show that this problem can be reformulated as an ordinary shortest-path problem over an expanded network and, thus, be solved much faster. An exact variable elimination procedure then allows the reduction of the expanded networks while still guaranteeing optimality. Second, the compact formulation gives rise to supplemental branching rules, which are needed, since existing rules do not ensure integrality in all cases. Third, non-repeater constraints are added dynamically to the master problem only when violated. The result is a fast exact algorithm, which improves many lower bounds of knowingly hard ttp instances from the literature. For some instances, solutions are proven optimal for the first time.     

Deriving weights from pairwise comparison ratio matrices: An axiomatic approach

This paper examines the problem of extracting object or attribute weights from a pairwise comparison ratio matrix. This problem is approached from the point of view of a distance measure on the space of all such matrices. A set of axioms is presented which such a distance measure should satisfy, and the uniqueness of the measure is proven. The problem of weight derivation is then shown to be equivalent to that of finding a totally transitive matrix which is a minimum distance from the given matrix. This problem reduces to a goal programming model. Finally, it is shown that the problem of weight derivation is related to that of ranking players in a round robin tournament. The space of all binary tournament matrices is proven to be isometric to a subset of the space of ratio matrices.     

Improved bounds for the traveling umpire problem: A stronger formulation and a relax-and-fix heuristic

Given a double round-robin tournament, the traveling umpire problem (TUP) consists of determining which games will be handled by each one of several umpire crews during the tournament. The objective is to minimize the total distance traveled by the umpires, while respecting constraints that include visiting every team at home, and not seeing a team or venue too often. We strengthen a known integer programming formulation for the TUP and use it to implement a relax-and-fix heuristic that improves the quality of 24 out of 25 best-known feasible solutions to instances in the TUP benchmark. We also improve all best-known lower bounds for those instances and, for the first time, provide lower bounds for instances with more than 16 teams.     

Partial Geometric Regularity of Some Optimal Connected Transportation Networks

We consider a continuous optimization model of a one-dimensional connected transportation network under the assumption that the cost of transportation with the use of network is negligible in comparison with the cost of transportation without it. We investigate the connections between this problem and its important special case, the minimization of the average distance functional. For the average distance minimization problem we formulate a number of conditions for the partial geometric regularity of a solution in ℝⁿ with an arbitrary dimension n ⩾ 2. The corresponding results are applied to solutions to the general optimization problem. Bibliography: 26 titles. Illustrations: 1 Figure. __________ Translated from Problemy Matematicheskogo Analiza, No. 31, 2005, pp. 129–157.     

A linear time approximation algorithm for movement minimization in conveyor flow shop processing

We consider the movement minimization problem in a conveyor flow shop processing controlled by one worker for all machines. A machine can only execute tasks if the worker is present. Each machine can serve as a buffer. The worker has to cover a certain distance to move from one machine to the other. The distance between two machines P_p and P_q is |p−q|. The objective is to minimize the total distance the worker has to cover for the processing of all jobs. We introduce a linear time approximation algorithm for the conveyor flow shop problem with performance 3. Such minimization problems usually appear in conveyor controlled manufacturing systems.     

On Lagrangian duality in vector optimization: applications to the linear case

We recall a general scheme for vector problems based on separation arguments and alternative theorems, and then, this approach is exploited to study Lagrangian duality in vector optimization. We show that the vector linear duality theory due to Isermann can be embedded in this separation approach. The theoretical part of this paper serves the purpose of introducing two possible applications. Some well-known classical applications in economics are the minimization of costs and the maximization of profit for a firm. We extend these two examples to the multiobjective framework in the linear case, exploiting the duality theory of Isermann. For the former, we consider the minimization of costs and of pollution as two different and conflicting goals; for the latter, we introduce as second objective function the profit for a competitor firm. This allows us to study the relationships between the shadow prices referred to the two different goals and to introduce a new representation of the feasible region of the dual problem.     

Duality for Anticonvex Programs

Calling anticonvex a program which is either a maximization of a convex function on a convex set or a minimization of a convex function on the set of points outside a convex subset, we introduce several dual problems related to each of these problems. We give conditions ensuring there is no duality gap. We show how solutions to the dual problems can serve to locate solutions of the primal problem.     

Exponential approximation schemata for some network design problems

We study approximation of some well-known network design problems such as the traveling salesman problem (for both minimization and maximization versions) and the min steiner tree problem by moderately exponential algorithms. The general goal of the issue of moderately exponential approximation is to catch up on polynomial inapproximability by designing superpolynomial algorithms achieving approximation ratios unachievable in polynomial time. Worst-case running times of such algorithms are significantly smaller than those needed for optimal solutions of the problems handled.