A bilevel programming approach to the travelling salesman problem

We show that the travelling salesman problem is polynomially reducible to a bilevel toll optimization program. Based on natural bilevel programming techniques, we recover the lifted Miller-Tucker-Zemlin constraints. Next, we derive an O(n²) multi-commodity extension whose LP relaxation is comparable to the exponential formulation of Dantzig, Fulkerson and Johnson.     

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.     

Maximization Problems in Single Machine Scheduling

Problems of scheduling n jobs on a single machine to maximize regular objective functions are studied. Precedence constraints may be given on the set of jobs and the jobs may have different release times. Schedules of interest are only those for which the jobs cannot be shifted to start earlier without changing job sequence or violating release times or precedence constraints. Solutions to the maximization problems provide an information about how poorly such schedules can perform. The most general problem of maximizing maximum cost is shown to be reducible to n similar problems of scheduling n?1 jobs available at the same time. It is solved in O(mn+n ²) time, where m is the number of arcs in the precedence graph. When all release times are equal to zero, the problem of maximizing the total weighted completion time or the weighted number of late jobs is equivalent to its minimization counterpart with precedence constraints reversed with respect to the original ones. If there are no precedence constraints, the problem of maximizing arbitrary regular function reduces to n similar problems of scheduling n?1 jobs available at the same time.     

Duality gaps in semi-infinite linear programming—an approximation problem

This paper builds upon the relationship between the objective function of a semi-infinite linear program and its constraints to identify a class of semi-infinite linear programs which do not have a duality gap. The key idea is to guarantee the approximation of the primal program by a sequence of linear programs where thenth approximating program is to minimize the objective function subject to the firstn constraints. The paper goes on to show that any program not in the identified class can be linearly perturbed into it with the optimal value of the perturbed program converging to the optimal value of the original program. The results are then extended to the case when an uncountable number of constraints are present by reducing this case to the countable case.     

Optimal interleaving schemes for correcting two-dimensional cluster errors

We present an elementary theory of optimal interleaving schemes for correcting cluster errors in two-dimensional digital data. It is assumed that each data page contains a fixed number of, say n, codewords with each codeword consisting of m code symbols and capable of correcting a single random error (or erasure). The goal is to interleave the codewords in the m×n array such that different symbols from each codeword are separated as much as possible, and consequently, an arbitrary error burst with size up to t can be corrected for the largest possible value of t. We show that, for any given m, n, the maximum possible interleaving distance, or equivalently, the largest size of correctable error bursts in an m×n array, is given by if n?⌈m²/2⌉, and t=m+⌊(n-⌈m²/2⌉)/m⌋ if n?⌈m²/2⌉. Furthermore, we develop a simple cyclic shifting algorithm that can provide a systematic construction of an m×n optimal interleaving array for arbitrary m and n. This extends important earlier work on the complementary problem of constructing interleaving arrays that, given the burst size t, minimize the interleaving degree, that is, the number of different codewords in a 2-D (or 3-D) array such that any error burst with given size t can be corrected. Our interleaving scheme thus provides the maximum burst error correcting power without requiring prior knowledge of the size or shape of an error burst.     

On a test of equality of two-parameter exponential distributions

In this paper, an asymptotic expansion of the distribution of the statistic for testing the equality of p two-parameter exponential distributions is obtained upto the order n^?4 with the second term of the order n^?3 where n is the size of the sample drawn from the i th exponential population. The asymptotic expansion can therefore be used to obtain accurate approximations to the critical values of the test statistic even for comparatively small values of n. Also we have shown that F-tables can be used to test the hypothesis when the sample size is moderately large.     

A bicriteria flowshop scheduling with a learning effect

In many situations, a worker’s ability improves as a result of repeating the same or similar tasks; this phenomenon is known as the learning effect. In this paper the learning effect is considered in a two-machine flowshop. The objective is to find a sequence that minimizes a weighted sum of total completion time and makespan. Total completion time and makespan are widely used performance measures in scheduling literature. To solve this scheduling problem, an integer programming model with n² + 6n variables and 7n constraints where n is the number of jobs is formulated. Because of the lengthy computing time and high computing complexity of the integer programming model, the problem with up to 30 jobs can be solved. A heuristic algorithm and a tabu search based heuristic algorithm are presented to solve large size problems. Experimental results show that the proposed heuristic methods can solve this problem with up to 300 jobs rapidly. According to the best of our knowledge, no work exists on the bicriteria flowshop with a learning effect.     

Solving large single allocation p-hub problems with two or three hubs

In this paper we present an efficient approach for solving single allocation p-hub problems with two or three hubs. Two different variants of the problem are considered: the uncapacitated single allocation p-hub median problem and the p-hub allocation problem. We solve these problems using new mixed integer linear programming formulations that require fewer variables than those formerly used in the literature. The problems that we solve here are the largest single allocation problems ever solved. The numerical results presented here will demonstrate the superior performance of our mixed integer linear programs over traditional approaches for large problems. Finally we present the first mixed integer linear program for solving single allocation hub location problems that requires only O(n²) variables and O(n²) constraints that is valid for any number of hubs.     

Maximum weight independent set of circular-arc graph and its application

In this paper, an algorithm is designed to find a maximum weight independent set of a circular-arc graph withn vertices. The weights considered here are all non-negative real numbers and associated with each of the vertex of the graph. The proposed algorithm runs in timeO(n²). Here we shown that the program slots of television channels during 24 hours can be modeled as a circular-arc graph. Each program represents a vertex and number of viewers of that program represents the weight of the corresponding vertex. Two vertices are connected by an edge iff the corresponding program slots have a common program time, i.e., ifI _i andI _j are the program slots of two programsi andj then the corresponding verticesi andj are connected by an edge iffI _i ∩ I_j 6? Φ. We also shown that the non-overlapping program slots with maximum number of viewers can be selected by computing maximum weight independent set on the corresponding circular-arc graph.     

Two machine preemptive scheduling problem with release dates,equal processing times and precedence constraints

We consider a scheduling problem with two identical parallel machines and n jobs. For each job we are given its release date when job becomes available for processing. All jobs have equal processing times. Preemptions are allowed. There are precedence constraints between jobs which are given by a (di)graph consisting of a set of outtrees and a number of isolated vertices. The objective is to find a schedule minimizing mean flow time. We suggest an O(n²) algorithm to solve this problem.The suggested algorithm also can be used to solve the related two-machine open shop problem with integer release dates, unit processing times and analogous precedence constraints.     

Periods in strings

In this paper we explore the notion of periods of a string. A period can be thought of as a shift that causes the string to match over itself. We obtain two sets of necessary and sufficient conditions for a set of integers to be the set of periods of some string (what we call the correlation of the string). We show that the number of distinct correlations of length n is independent of the alphabet size and is of order n^logn. By using generating function methods we enumerate the strings having a given correlation, and investigate certain related questions.     

On convex quadratic programs with linear complementarity constraints

The paper shows that the global resolution of a general convex quadratic program with complementarity constraints (QPCC), possibly infeasible or unbounded, can be accomplished in finite time. The method constructs a minmax mixed integer formulation by introducing finitely many binary variables, one for each complementarity constraint. Based on the primal-dual relationship of a pair of convex quadratic programs and on a logical Benders scheme, an extreme ray/point generation procedure is developed, which relies on valid satisfiability constraints for the integer program. To improve this scheme, we propose a two-stage approach wherein the first stage solves the mixed integer quadratic program with pre-set upper bounds on the complementarity variables, and the second stage solves the program outside this bounded region by the Benders scheme. We report computational results with our method. We also investigate the addition of a penalty term y ^T Dw to the objective function, where y and w are the complementary variables and D is a nonnegative diagonal matrix. The matrix D can be chosen effectively by solving a semidefinite program, ensuring that the objective function remains convex. The addition of the penalty term can often reduce the overall runtime by at least 50 %. We report preliminary computational testing on a QP relaxation method which can be used to obtain better lower bounds from infeasible points; this method could be incorporated into a branching scheme. By combining the penalty method and the QP relaxation method, more than 90 % of the gap can be closed for some QPCC problems.     

Embedding a Latin square with transversal into a projective space

A Latin square of side n defines in a natural way a finite geometry on 3n points, with three lines of size n and n² lines of size 3. A Latin square of side n with a transversal similarly defines a finite geometry on 3n+1 points, with three lines of size n, n²−n lines of size 3, and n concurrent lines of size 4. A collection of k mutually orthogonal Latin squares defines a geometry on kn points, with k lines of size n and n² lines of size k. Extending the work of Bruen and Colbourn [A.A. Bruen, C.J. Colbourn, Transversal designs in classical planes and spaces, J. Combin. Theory Ser. A 92 (2000) 88-94], we characterise embeddings of these finite geometries into projective spaces over skew fields.     

A Theorem Concerning the Integer Lattice

This note shows that if an integer linear program in n variables has more than 2ⁿ linear inequality constraints, then either some of the constraints are unnecessary or there is at least one feasible integer point.     

The Facial Decomposition Method

This note presents a brute force approach to linearly constrained programming in non-convex optimization; our aim here is to illustrate a general methodology which can be applied to construct tailor-made algorithms in specific applications.In essence, the facial decomposition method constructs a non-redundant list of all faces of the polyhedral set P ? R ⁿ . Each face is characterized by a linear program in a given affine subspace of R ⁿ . This list is conveniently displayed in a tree structure which represents the set of nodes to be searched (typically for optimality).     

On-line algorithms for networks of temporal constraints

We consider a semi-dynamic setting for the Temporal Constraint Satisfaction Problem (TCSP), where we are requested to maintain the path-consistency of a network under a sequence of insertions of new (further) constraints between pairs of variables. We show how to maintain the path-consistency in O(nR³) amortized time on a sequence of Θ(n²) insertions, where n is the number of vertices of the network and R is its range, defined as the maximum size of the minimum interval containing all the intervals of a single constraint.Furthermore we extend our algorithms to deal with more general temporal networks where variables can be points and/or intervals and constraints can also be defined on pairs of different kinds of variables. For such cases our algorithms maintain their performance. Finally, we adapt our algorithms to also maintain the arc-consistency of such generalized networks in O(R) amortized time for Θ(n²) insertions.     

Better upper bounds on the QOBDD size of integer multiplication

We show that the middle bit of the multiplication of two n-bit integers can be computed by an ordered binary decision diagram (OBDD) of size less than 2.8·2^6n/5. This improves the previously known upper bound of by Woelfel (New Bounds on the OBDD-size of integer multiplication via Universal Hashing, J. Comput. System Sci. 71(4) (2005) 520-534). The experimental results suggest that our exponent of 6n/5 is optimal or at least very close to optimal. A general upper bound of O(2^3n/2) on the OBDD size of each output bit of the multiplication is also presented.     

On finding a large number of 3D points with a small diameter

Given a set S of n points in R³, we wish to decide whether S has a subset of size at least k with Euclidean diameter at most r. It is unknown whether this decision problem is NP-hard. The two closely related optimization problems, (i) finding a largest subset of diameter at most r, and (ii) finding a subset of the smallest diameter of size at least k, were recently considered by Afshani and Chan. For maximizing the size, they presented several polynomial-time algorithms with constant approximation factors, the best of which has a factor of . For maximizing the diameter, they presented a polynomial-time approximation scheme. In this paper, we present improved approximation algorithms for both optimization problems. For maximizing the size, we present two algorithms: the first one improves the approximation factor to 2.5 and the running time by an O(n) factor; the second one improves the approximation factor to 2 and the running time by an O(n²) factor. For minimizing the diameter, we improve the running time of the PTAS from O(nlogn+2^O(1/ε3)n) to O(nlogn+2^{O(1/(ε1.5logε))}n).     

An O(n2) simplex algorithm for a class of linear programs with tree structure

In connection with the optimal design of centralized circuit-free networks linear 0–1 programming problems arise which are related to rooted trees. For each problem the variables correspond to the edges of a given rooted tree T. Each path from a leaf to the root of T, together with edge weights, defines a linear constraint, and a global linear objective is to be maximized. We consider relaxations of such problems where the variables are not restricted to 0 or 1 but are allowed to vary continouosly between these bounds. The values of the optimal solutions of such relaxations may be used in a branch and bound procedure for the original 0–1 problem. While in [10] a primal algorithm for these relaxations is discussed, in this paper, we deal with the dual linear program and present a version of the simplex algorithm for its solution which can be implemented to run in time O(n²). For balanced trees T this time can be reduced to O(n log n).     

On defining sets of vertices of the hypercube by linear inequalities

This paper shows that for any subset S of vertices of the n-dimensional hypercube, ind(S)≤2^n?1, where ind(S) is the minimum number of linear inequalities needed to define S. Furthermore, for any k in the range 1≤k≤2^n?1, there is an S with ind(S) = k, with the defining inequalities taken as canonical cuts. Other related results are included, and all are proven by explicit constructions of the sets S or explicit definitions of such sets by linear inequalities.The paper is aimed at researchers in bivalent programming, since it provides upper bounds on the performance of algorithms which combine several linear constraints into one, even when the given constraints have a particularly simple form.