Uncapacitated two-level lot-sizing

For the uncapacitated two-level production-in-series T period lot-sizing model, a dynamic program with running time O(T²logT) and a compact and tight extended formulation with O(T³) variables and O(T²) equality constraints are presented. Limited computational comparisons of various formulations of two-level production/transportation problems with multiple clients are reported.     

Extended formulations for the cardinality constrained subtree of a tree problem

Given a tree with n nodes, we consider the problem of finding the most profitable subtree of that tree with at most K nodes which is known as the Cardinality Subtree of a Tree Problem. We present a new exact linear extended formulation with O(nK) two-indexed variables and O(nK) constraints.     

3-coloring in time

We consider worst case time bounds for several NP-complete problems, based on a constraint satisfaction (CSP) formulation of these problems: (a,b)-CSP instances consist of a set of variables, each with up to a possible values, and constraints disallowing certain b-tuples of variable values; a problem is solved by assigning values to all variables satisfying all constraints, or by showing that no such assignment exist. 3-SAT is equivalent to (2,3)-CSP while 3-coloring and various related problems are special cases of (3,2)-CSP; there is also a natural duality transformation from (a,b)-CSP to (b,a)-CSP. We show that n-variable (3,2)-CSP instances can be solved in time O(1.3645ⁿ), that satisfying assignments to (d,2)-CSP instances can be found in randomized expected time O((0.4518d)ⁿ); that 3-coloring of n-vertex graphs can be solved in time O(1.3289ⁿ); that 3-list-coloring of n-vertex graphs can be solved in time O(1.3645ⁿ); that 3-edge-coloring of n-vertex graphs can be solved in time O(2^n/2), and that 3-satisfiability of a formula with t 3-clauses can be solved in time O(n^O(1)+1.3645^t).     

A matheuristic approach for the two-machine total completion time flow shop problem

This paper deals with the two-machine total completion time flow shop problem. We present a so-called matheuristic post processing procedure that improves the objective function value with respect to the solutions provided by state of the art procedures. The proposed procedure is based on the positional completion times integer programming formulation of the problem with O(n ²) variables and O(n) constraints.     

Fast rectangular matrix multiplication and some applications

We study asymptotically fast multiplication algorithms for matrix pairs of arbitrary di- mensions, and optimize the exponents of their arithmetic complexity bounds. For a large class of input matrix pairs, we improve the known exponents. We also show some applications of our results:(i) we decrease from O(n~2 n~(1 o)(1)logq)to O(n~(1.9998) n~(1 o(1))logq)the known arithmetic complexity bound for the univariate polynomial factorization of degree n over a finite field with q elements; (ii) we decrease from 2.837 to 2.7945 the known exponent of the work and arithmetic processor bounds for fast deterministic(NC)parallel evaluation of the determinant, the characteristic polynomial, and the inverse of an n×n matrix, as well as for the solution to a nonsingular linear system of n equations; (iii)we decrease from O(m~(1.575)n)to O(m~(1.5356)n)the known bound for computing basic solutions to a linear programming problem with m constraints and n variables.     

Improved dynamic programming algorithms for bandwidth minimization and the MinCut Linear Arrangement problem

The dynamic programming algorithm of [12.] for the bandwidth minimization problem is improved. It is shown that, for all k > 1, BANDWIDTH(k) can be solved in O(n^k) steps and simultaneous O(n^k) space, where n is the number of vertices in the graph, and that each such problem is in NSPACE(log n). The same improved dynamic programming algorithm approach works to show that the MINCUT LINEAR ARRANGEMENT problem restricted to the fixed value k, denoted by MINCUT(k), is solvable in O(n^k) steps and simultaneous O(n^k) space and is in the class NSPACE(log n).     

Parallel algorithms for permutation graphs

In this paper, parallel algorithms are presented for solving some problems on permutation graphs. The coloring problem is solved inO(log² n) time usingO(n ³/logn) processors on the CREW PRAM, orO(logn) time usingO(n ³) processors on the CRCW PRAM. The weighted clique problem, the weighted independent set problem, the cliques cover problem, and the maximal layers problem are all solved with the same complexities. We can also show that the longest common subsequence problem belongs to the class NC.     

Random walks in a convex body and an improved volume algorithm

We give a randomized algorithm using O(n⁷ log² n) separation calls to approximate the volume of a convex body with a fixed relative error. The bound is O(n⁶ log⁴ n) for centrally symmpetric bodies and for polytopes with a polynomial number of facets, and O(n⁵ log⁴ n) for centrally symmetric polytopes with a polynomial number of facets. We also give an O(n⁶ log n) algorithm to sample a point from the uniform distribution over a convex body. Several tools are developed that may be interesting on their own. We extend results of Sinclair–Jerrum [43] and the authors [34] on the mixing rate of Markov chains from finite to arbitrary Markov chains. We also analyze the mixing rate of various random walks on convex bodies, in particular the random walk with steps from the uniform distribution over a unit ball. © 1993 John Wiley & Sons, Inc.     

A Parallel Reduction of Hamiltonian Cycle to Hamiltonian Path in Tournaments

We propose a parallel algorithm which reduces the problem of computing Hamiltonian cycles in tournaments to the problem of computing Hamiltonian paths. The running time of our algorithm is O(log n) using O(n²/log n) processors on a CRCW PRAM, and O(log n log log n) on an EREW PRAM using O(n²/log n log log n) processors. As a corollary, we obtain a new parallel algorithm for computing Hamiltonian cycles in tournaments. This algorithm can be implemented in time O(log n) using O(n²/log n) processors in the CRCW model and in time O(log²n) with O(n²/log n log log n) processors in the EREW model.     

Formulations and Benders decomposition algorithms for multidepot salesmen problems with load balancing

This paper describes new models and exact solution algorithms for the fixed destination multidepot salesmen problem defined on a graph with n nodes where the number of nodes each salesman is to visit is restricted to be in a predefined range. Such problems arise when the time to visit a node takes considerably longer as compared to the time of travel between nodes, in which case the number of nodes visited in a salesman’s tour is the determinant of their ‘load’. The new models are novel multicommodity flow formulations with O(n²) binary variables, which is contrary to the existing formulations for the same (and similar) problems that typically include O(n³) binary variables. The paper also describes Benders decomposition algorithms based on the new formulations for solving the problem exactly. Results of the computational experiments on instances derived from TSPLIB show that some of the proposed algorithms perform remarkably well in cases where formulations solved by a state-of-the-art optimization code fail to yield optimal solutions within reasonable computation time.     

New integer linear programming formulation for the traveling salesman problem with time windows: minimizing tour duration with waiting times

The travelling salesman problem, being one of the most attractive and well-studied combinatorial optimization problems, has many variants, one of which is called ‘travelling salesman problem with Time Windows (TSPTW)’. In this problem, each city (nodes, customers) must be visited within a time window defined by the earliest and the latest time. In TSPTW, the traveller has to wait at a city if he/she arrives early; thus waiting times directly affect the duration of a tour. It would be useful to develop a new model solvable by any optimizer directly. In this paper, we propose a new integer linear programming formulation having O(n²) binary variables and O(n²) constraints, where (n) equals the number of nodes of the underlying graph. The objective function is stated to minimize the total travel time plus the total waiting time. A computational comparison is made on a suite of test problems with 20 and 40 nodes. The performances of the proposed and existing formulations are analysed with respect to linear programming relaxations and the CPU times. The new formulation considerably outperforms the existing one with respect to both the performance criteria. Adaptation of our formulation to the multi-traveller case and some additional restrictions for special situations are illustrated.     

Ray Shooting Amidst Convex Polygons in 2D

We consider the problem of ray shooting in a two-dimensional scene consisting ofmconvex polygons with a total ofnedges. We present a data structure that requiresO(mn log m) space and preprocessing time and that answers a ray shooting query inO(log² m log² n) time. If the polygons are pairwise disjoint, the space and preprocessing time can be improved toO((m²+n)log m) andO((m²+n log n)log m), respectively. Our algorithm also works for a collection of disjoint simple polygons. We also show that if we allow onlyO(n) space, a ray shooting query among a collection of disjoint simple polygons can be answered in timeO(m/[formula]¹⁺ log² n) time, for any >0.     

A Fast and Simple Algorithm for Identifying 2-Monotonic Positive Boolean Functions

Consider the problem of identifying min T(f) and max F(f) of a positive (i.e., monotone) Boolean functionf, by using membership queries only, where min T(f) (max F(f)) denotes the set of minimal true vectors (maximum false vectors) off. Moreover, as the existence of a polynomial total time algorithm (i.e., polynomial time in the length of input and output) for this problem is still open, we consider here a restricted problem: given an unknown positive functionfofnvariables, decide whetherfis 2-monotonic or not, and iffis 2-monotonic, output both min T(f) and max F(f). For this problem, we propose a simple algorithm, which is based on the concept of maximum latency, and we show that it usesO(n²m) time andO(n²m) queries, wherem = |min T(f)| + |max F(f)|. This answers affirmatively the conjecture raised in Boroset al.[Lecture Notes in Comput. Sci.557(1991), 104–115], Boroset al.[SIAM J. Comput.26(1997), 93–109], and is an improvement over the two algorithms discussed therein: one usesO(n³m) time andO(n³m) queries, and the other usesO(nm² + n²m) time andO(nm) queries.     

Projection of diffusions on submanifolds: Application to mean force computation

We consider the problem of sampling a Boltzmann‐Gibbs probability distribution when this distribution is restricted (in some suitable sense) on a submanifold Σ of ?ⁿ implicitly defined by N constraints q₁(x) = ? = q_N(x) = 0 (N < n). This problem arises, for example, in systems subject to hard constraints or in the context of free energy calculations. We prove that the constrained stochastic differential equations (i.e., diffusions) proposed in [7, 13] are ergodic with respect to this restricted distribution. We also construct numerical schemes for the integration of the constrained diffusions. Finally, we show how these schemes can be used to compute the gradient of the free energy associated with the constraints. © 2007 Wiley Periodicals, Inc.     

Computing homotopic shortest paths in the plane

We address the problem of computing homotopic shortest paths in the presence of obstacles in the plane. Problems on homotopy of paths received attention very recently [Cabello et al., in: Proc. 18th Annu. ACM Sympos. Comput. Geom., 2002, pp. 160–169; Efrat et al., in: Proc. 10th Annu. European Sympos. Algorithms, 2002, pp. 411–423]. We present two output-sensitive algorithms, for simple paths and non-simple paths. The algorithm for simple paths improves the previous algorithm [Efrat et al., in: Proc. 10th Annu. European Sympos. Algorithms, 2002, pp. 411–423]. The algorithm for non-simple paths achieves O(log²n) time per output vertex which is an improvement by a factor of O(n/log²n) of the previous algorithm [Hershberger, Snoeyink, Comput. Geom. Theory Appl. 4 (1994) 63–98], where n is the number of obstacles. The running time has an overhead O(n²⁺) for any positive constant . In the case k<n²⁺, where k is the total size of the input and output, we improve the running to O((n+k+(nk)^2/3)log^O(1)n).     

Scheduling jobs with release times preemptively on a single machine to minimize the number of late jobs

We give a direct combinatorial O(n³logn) algorithm for minimizing the number of late jobs on a single machine when jobs have release times and preemptions are allowed. Our algorithm improves the earlier O(n⁵) and O(n⁴) dynamic programming algorithms for this problem.     

Efficient generation of random nonsingular matrices

We present an efficient algorithm for generating an n × n nonsingular matrix uniformly over a finite field. This algorithm is useful for several cryptographic and checking applications. Over GF[2] our algorithm runs in expected time M(n) + O(n²), where M(n) is the time needed to multiply two n × n matrices, and the expected number of random bits it uses is n² + 3. (Over other finite fields we use n² + O(1) random field elements on average.) This is more efficient than the standard method for solving this problem, both in terms of expected running time and the expected number of random bits used. The standard method is to generate random n × n matrices until we produce one with nonzero determinant. In contrast, our technique directly produces a random matrix guaranteed to have nonzero determinant. We also introduce efficient algorithms for related problems such as uniformly generating singular matrices or matrices with fixed determinant. © 1993 John Wiley & Sons, Inc.     

Improved complexity results for several multifacility location problems on trees

In this paper we consider multifacility location problems on tree networks. On general networks, these problems are usually NP-hard. On tree networks, however, often polynomial time algorithms exist; e.g., for the median, center, centdian, or special cases of the ordered median problem. We present an enhanced dynamic programming approach for the ordered median problem that has a time complexity of just O(ps ² n ⁶) for the absolute and O(ps ² n ²) for the node restricted problem, improving on the previous results by a factor of O(n ³). (n and p being the number of nodes and new facilities, respectively, and s (≤n) a value specific for the ordered median problem.) The same reduction in complexity is achieved for the multifacility k-centrum problem leading to O(pk ² n ⁴) (absolute) and O(pk ² n ²) (node restricted) algorithms.     

Bound reduction using pairs of linear inequalities

We describe a procedure to reduce variable bounds in mixed integer nonlinear programming (MINLP) as well as mixed integer linear programming (MILP) problems. The procedure works by combining pairs of inequalities of a linear programming (LP) relaxation of the problem. This bound reduction procedure extends the feasibility based bound reduction technique on linear functions, used in MINLP and MILP. However, it can also be seen as a special case of optimality based bound reduction, a method to infer variable bounds from an LP relaxation of the problem. For an LP relaxation with m constraints and n variables, there are O(m ²) pairs of constraints, and a naïve implementation of our bound reduction scheme has complexity O(n ³) for each pair. Therefore, its overall complexity O(m ² n ³) can be prohibitive for relatively large problems. We have developed a more efficient procedure that has complexity O(m ² n ²), and embedded it in two Open-Source solvers: one for MINLP and one for MILP. We provide computational results which substantiate the usefulness of this bound reduction technique for several instances.