Approximating a two-machine flow shop scheduling under discrete scenario uncertainty

This paper deals with the two machine permutation flow shop problem with uncertain data, whose deterministic counterpart is known to be polynomially solvable. In this paper, it is assumed that job processing times are uncertain and they are specified as a discrete scenario set. For this uncertainty representation, the min-max and min-max regret criteria are adopted. The min-max regret version of the problem is known to be weakly NP-hard even for two processing time scenarios. In this paper, it is shown that the min-max and min-max regret versions of the problem are strongly NP-hard even for two scenarios. Furthermore, the min-max version admits a polynomial time approximation scheme if the number of scenarios is constant and it is approximable with performance ratio of 2 and not (4/3 − ?)-approximable for any ? > 0 unless P = NP if the number of scenarios is a part of the input. On the other hand, the min-max regret version is not at all approximable even for two scenarios.     

Robust combinatorial optimization with variable cost uncertainty

We present in this paper a new model for robust combinatorial optimization with cost uncertainty that generalizes the classical budgeted uncertainty set. We suppose here that the budget of uncertainty is given by a function of the problem variables, yielding an uncertainty multifunction. The new model is less conservative than the classical model and approximates better Value-at-Risk objective functions, especially for vectors with few non-zero components. An example of budget function is constructed from the probabilistic bounds computed by Bertsimas and Sim. We provide an asymptotically tight bound for the cost reduction obtained with the new model. We turn then to the tractability of the resulting optimization problems. We show that when the budget function is affine, the resulting optimization problems can be solved by solving n+1$n+1$ deterministic problems. We propose combinatorial algorithms to handle problems with more general budget functions. We also adapt existing dynamic programming algorithms to solve faster the robust counterparts of optimization problems, which can be applied both to the traditional budgeted uncertainty model and to our new model. We evaluate numerically the reduction in the price of robustness obtained with the new model on the shortest path problem and on a survivable network design problem.     

Revisiting dynamic programming for finding optimal subtrees in trees

In this paper we revisit an existing dynamic programming algorithm for finding optimal subtrees in edge weighted trees. This algorithm was sketched by Maffioli in a technical report in 1991. First, we adapt this algorithm for the application to trees that can have both node and edge weights. Second, we extend the algorithm such that it does not only deliver the values of optimal trees, but also the trees themselves. Finally, we use our extended algorithm for developing heuristics for the k-cardinality tree problem in undirected graphs G with node and edge weights. This NP-hard problem consists of finding in the given graph a tree with exactly k edges such that the sum of the node and the edge weights is minimal. In order to show the usefulness of our heuristics we conduct an extensive computational analysis that concerns most of the existing problem instances. Our results show that with growing problem size the proposed heuristics reach the performance of state-of-the-art metaheuristics. Therefore, this study can be seen as a cautious note on the scaling of metaheuristics.     

The inverse Fermat–Weber problem

Given n points in the plane with nonnegative weights, the inverse Fermat–Weber problem consists in changing the weights at minimum cost such that a prespecified point in the plane becomes the Euclidean 1-median. The cost is proportional to the increase or decrease of the corresponding weight. In case that the prespecified point does not coincide with one of the given n points, the inverse Fermat–Weber problem can be formulated as linear program. We derive a purely combinatorial algorithm which solves the inverse Fermat–Weber problem with unit cost using O(n) greedy-like iterations where each of them can be done in constant time if the points are sorted according to their slopes. If the prespecified point coincides with one of the given n points, it is shown that the corresponding inverse problem can be written as convex problem and hence is solvable in polynomial time to any fixed precision.     

Reverse 2-median problem on trees

This paper concerns the reverse 2-median problem on trees and the reverse 1-median problem on graphs that contain exactly one cycle. It is shown that both models under investigation can be transformed to an equivalent reverse 2-median problem on a path. For this new problem an algorithm is proposed, where n is the number of vertices of the path. It is also shown that there exists an integral solution if the input data are integral.     

On the adjustment problem for linear programs

We propose a generalization of the inverse problem which we will call the adjustment problem. For an optimization problem with linear objective function and its restriction defined by a given subset of feasible solutions, the adjustment problem consists in finding the least costly perturbations of the original objective function coefficients, which guarantee that an optimal solution of the perturbed problem is also feasible for the considered restriction. We describe a method of solving the adjustment problem for continuous linear programming problems when variables in the restriction are required to be binary.     

Uniform-cost inverse absolute and vertex center location problems with edge length variations on trees

This article considers the inverse absolute and the inverse vertex 1-center location problems with uniform cost coefficients on a tree network T with n+1 vertices. The aim is to change (increase or reduce) the edge lengths at minimum total cost with respect to given modification bounds such that a prespecified vertex s becomes an absolute (or a vertex) 1-center under the new edge lengths. First an O(nlogn) time method for solving the height balancing problem with uniform costs is described. In this problem the height of two given rooted trees is equalized by decreasing the height of one tree and increasing the height of the second rooted tree at minimum cost. Using this result a combinatorial O(nlogn) time algorithm is designed for the uniform-cost inverse absolute 1-center location problem on tree T. Finally, the uniform-cost inverse vertex 1-center location problem on T is investigated. It is shown that the problem can be solved in O(nlogn) time if all modified edge lengths remain positive. Dropping this condition, the general model can be solved in O(r_vnlogn) time where the parameter r_v is bounded by ⌈n/2⌉. This corrects an earlier result of Yang and Zhang.     

General solutions to the single vehicle routing problem with pickups and deliveries

The single vehicle routing problem with pickups and deliveries (SVRPPD) is defined on a graph in which pickup and delivery demands are associated with the customer vertices. The problem consists of designing a least cost route for a vehicle of capacity Q. Each customer is allowed to be visited once for a combined pickup and delivery, or twice if these two operations are performed separately. This article proposes a mixed integer linear programming model for the SVRPPD. It introduces the concept of general solution which encompasses known solution shapes such as Hamiltonian, double-path and lasso. Classical construction and improvement heuristics, as well as a tabu search heuristic, are developed and tested over several instances. Computational results show that the best solutions generated by the heuristics are frequently non-Hamiltonian and may contain up to two customers visited twice.     

Classes of cycle bases

In the last years, new variants of the minimum cycle basis (MCB) problem and new classes of cycle bases have been introduced, as motivated by several applications from disparate areas of scientific and technological inquiries. At present, the complexity status of the MCB problem has been settled only for undirected, directed, and strictly fundamental cycle bases.In this paper, we offer an unitary classification accommodating these three classes and further including the following four relevant classes: 2-bases (or planar bases), weakly fundamental cycle bases, totally unimodular cycle bases, and integral cycle bases. The classification is complete in that, for each ordered pair (A,B) of classes considered, we either prove that A⊆B holds for every graph or provide a counterexample graph for which A?B. The seven notions of cycle bases are distinct (either A?B or B?A is exhibited for each pair (A,B)).All counterexamples proposed have been designed to be ultimately effective in separating the various algorithmic variants of the MCB problem naturally associated to each one of these seven classes. Furthermore, we provide a linear time algorithm for computing a minimum 2-basis of a graph. Finally, notice that the resolution of the complexity status of some of the remaining three classes would have an immediate impact on practical applications, as for instance in periodic railway timetabling, only integral cycle bases are of direct use.     

Domination analysis for minimum multiprocessor scheduling

Let P be a combinatorial optimization problem, and let A be an approximation algorithm for P. The domination ratio domr(A,s) is the maximal real q such that the solution x(I) obtained by A for any instance I of P of size s is not worse than at least the fraction q of the feasible solutions of I. We say that P admits an asymptotic domination ratio one (ADRO) algorithm if there is a polynomial time approximation algorithm A for P such that . Alon, Gutin and Krivelevich [Algorithms with large domination ratio, J. Algorithms 50 (2004) 118-131] proved that the partition problem admits an ADRO algorithm. We extend their result to the minimum multiprocessor scheduling problem.     

An electromagnetism metaheuristic for the unicost set covering problem

In this paper we propose a new heuristic algorithm to solve the unicost version of the well-known set covering problem. The method is based on the electromagnetism metaheuristic approach which, after generating a pool of solutions to create the initial population, applies a fixed number of local search and movement iterations based on the “electromagnetism” theory. In addition to some random aspects, used in the construction and local search phases, we also apply mutation in order to further escape from local optima.     

Some formulations for the group steiner tree problem

The group Steiner tree problem consists of, given a graph G, a collection R of subsets of V(G) and a cost c(e) for each edge of G, finding a minimum-cost subtree that connects at least one vertex from each R∈R. It is a generalization of the well-known Steiner tree problem that arises naturally in the design of VLSI chips. In this paper, we study a polyhedron associated with this problem and some extended formulations. We give facet defining inequalities and explore the relationship between the group Steiner tree problem and other combinatorial optimization problems.     

On combinatorial optimization problems on matroids with uncertain weights

In this paper the combinatorial optimization problem on weighted matroid is considered. It is assumed that the weights in the problem are ill-known and they are modeled as fuzzy intervals. The optimality of solutions and the optimality of elements are characterized. This characterization is performed in the setting of possibility theory. A method of choosing a solution under uncertainty is also proposed.     

The complexity of maximum matroid-greedoid intersection and weighted greedoid maximization

The maximum intersection problem for a matroid and a greedoid, given by polynomial-time oracles, is shown NP-hard by expressing the satisfiability of boolean formulas in 3-conjunctive normal form as such an intersection. The corresponding approximation problems are shown NP-hard for certain approximation performance bounds. Moreover, some natural parameterized variants of the problem are shown W[P]-hard. The results are in contrast with the maximum matroid-matroid intersection which is solvable in polynomial time by an old result of Edmonds. We also prove that it is NP-hard to approximate the weighted greedoid maximization within 2^nO(1) where n is the size of the domain of the greedoid.     

The x-and-y-axes travelling salesman problem

The x-and-y-axes travelling salesman problem forms a special case of the Euclidean TSP, where all cities are situated on the x-axis and on the y-axis of an orthogonal coordinate system of the Euclidean plane. By carefully analyzing the underlying combinatorial and geometric structures, we show that this problem can be solved in polynomial time. The running time of the resulting algorithm is quadratic in the number of cities.     

Minimizing the number of workers in a paced mixed-model assembly line

We study a problem of minimizing the maximum number of identical workers over all cycles of a paced assembly line comprised of m stations and executing n parts of k types. There are lower and upper bounds on the workforce requirements and the cycle time constraints. We show that this problem is equivalent to the same problem without the cycle time constraints and with fixed workforce requirements. We prove that the problem is NP-hard in the strong sense if $m=4$ and the workforce requirements are station independent, and present an Integer Linear Programming model, an enumeration algorithm and a dynamic programming algorithm. Polynomial in k and polynomial in n algorithms for special cases with two part types or two stations are also given. Relations to the Bottleneck Traveling Salesman Problem and its generalizations are discussed.     

The school bus routing problem: A review

This paper aims to provide a comprehensive review of the school bus routing problem (SBRP). SBRP seeks to plan an efficient schedule for a fleet of school buses where each bus picks up students from various bus stops and delivers them to their designated schools while satisfying various constraints such as the maximum capacity of a bus, the maximum riding time of a student in a bus, and the time window of a school. This class of problem consists of different sub-problems involving data preparation, bus stop selection, bus route generation, school bell time adjustment, and bus scheduling. In this paper, the various assumptions, constraints, and solution methods used in the literature on SBRP are summarized. A list of issues requiring further research is also presented.     

A provably convergent heuristic for stochastic bicriteria integer programming

We propose a general-purpose algorithm APS (Adaptive Pareto-Sampling) for determining the set of Pareto-optimal solutions of bicriteria combinatorial optimization (CO) problems under uncertainty, where the objective functions are expectations of random variables depending on a decision from a finite feasible set. APS is iterative and population-based and combines random sampling with the solution of corresponding deterministic bicriteria CO problem instances. Special attention is given to the case where the corresponding deterministic bicriteria CO problem can be formulated as a bicriteria integer linear program (ILP). In this case, well-known solution techniques such as the algorithm by Chalmet et al. can be applied for solving the deterministic subproblem. If the execution of APS is terminated after a given number of iterations, only an approximate solution is obtained in general, such that APS must be considered a metaheuristic. Nevertheless, a strict mathematical result is shown that ensures, under rather mild conditions, convergence of the current solution set to the set of Pareto-optimal solutions. A modification replacing or supporting the bicriteria ILP solver by some metaheuristic for multicriteria CO problems is discussed. As an illustration, we outline the application of the method to stochastic bicriteria knapsack problems by specializing the general framework to this particular case and by providing computational examples.     

A reduction approach to the repeated assignment problem

We consider the repeated assignment problem (RAP), which is a K-fold repetition of the n × n linear assignment problem (LAP), with the additional requirement that no assignment can be repeated more than once. In actual applications K is typically much smaller than n. First, we derive upper and lower bounds respectively by a heuristic together with local search, and an efficient method solving the continuous relaxation. The latter also solves a Lagrangian relaxation, such that the related pegging test, to fix variables at zero or one, decomposes into K independent pegging tests to LAPs. These can be solved exactly by transforming them into all-pairs shortest path problems. Together with these procedures, we also employ a virtual pegging test and reduce RAP in size. Numerical experiments show that the reduced instances, with K ? n, can be solved exactly using standard MIP solvers.