A note on formulations for the A-partition problem on hypergraphs

Let H = (V, E) be an undirected hypergraph and AC. We consider the problem of finding a minimum cost partition of V that separates every pair of nodes in A. We consider three formulations of the problem and show that the theoretical lower bounds to the integer optimal objective value provided by the LP-relaxations in all three cases are identical. We describe our empiical findings with each formulation.     

Extended formulations for the A-cut problem

LetG=(V, E) be an undirected graph andA⊆V. We consider the problem of finding a minimum cost set of edges whose deletion separates every pair of nodes inA. We consider two extended formulations using both node and edge variables. An edge variable formulation has previously been considered for this problem (Chopra and Rao (1991), Cunningham (1991)). We show that the LP-relaxations of the extended formulations are stronger than the LP-relaxation of the edge variable formulation (even with an extra class of valid inequalities added). This is interesting because, while the LP-relaxations of the extended formulations can be solved in polynomial time, the LP-relaxation of the edge variable formulation cannot. We also give a class of valid inequalities for one of the extended formulations. Computational results using the extended formulations are performed.     

A dynamic programming based reduction procedure for the multidimensional 0–1 knapsack problem

This paper presents a preprocessing procedure for the 0–1 multidimensional knapsack problem. First, a non-increasing sequence of upper bounds is generated by solving LP-relaxations. Then, a non-decreasing sequence of lower bounds is built using dynamic programming. The comparison of the two sequences allows either to prove that the best feasible solution obtained is optimal, or to fix a subset of variables to their optimal values. In addition, a heuristic solution is obtained. Computational experiments with a set of large-scale instances show the efficiency of our reduction scheme. Particularly, it is shown that our approach allows to reduce the CPU time of a leading commercial software.     

Worst-case analysis of a dynamic channel assignment strategy

We consider the problem of channel assignment in cellular networks with arbitrary reuse distance. We show upper and lower bounds for the competitive ratio of a previously proposed and widely studied version of dynamic channel assignment, which we refer to as the greedy algorithm. We study two versions of this algorithm: one that performs reassignment of channels, and one that never reassigns channels to calls. For reuse distance 2, we show tight bounds on the competitive ratio of both versions of the algorithm. For reuse distance 3, we show non-trivial lower bounds for both versions of the algorithm.     

Reformulation and a Lagrangian heuristic for lot sizing problem on parallel machines

We consider the capacitated lot sizing problem with multiple items, setup time and unrelated parallel machines. The aim of the article is to develop a Lagrangian heuristic to obtain good solutions to this problem and good lower bounds to certify the quality of solutions. Based on a strong reformulation of the problem as a shortest path problem, the Lagrangian relaxation is applied to the demand constraints (flow constraint) and the relaxed problem is decomposed per period and per machine. The subgradient optimization method is used to update the Lagrangian multipliers. A primal heuristic, based on transfers of production, is designed to generate feasible solutions (upper bounds). Computational results using data from the literature are presented and show that our method is efficient, produces lower bounds of good quality and competitive upper bounds, when compared with the bounds produced by another method from the literature and by high-performance MIP software.     

Improved lower bounds for the early/tardy scheduling problem with no idle time

In this paper, we consider the single machine earliness/tardiness scheduling problem with no idle time. Two of the lower bounds previously developed for this problem are based on Lagrangean relaxation and the multiplier adjustment method, and require an initial sequence. We investigate the sensitivity of the lower bounds to the initial sequence, and experiment with different dispatch rules and some dominance conditions. The computational results show that it is possible to obtain improved lower bounds by using a better initial sequence. The lower bounds are also incorporated in a branch-and-bound algorithm, and the computational tests show that one of the new lower bounds has the best performance for larger instances.     

On the complexity of the satisfiability problem for a system of functional Boolean equations

We consider functional Boolean equations and the satisfiability problem for them, which amounts to the following: Does there exist a Boolean function satisfying a given functional equation? We establish upper and lower bounds for the complexity of the satisfiability problem for a system of functional Boolean equations. This justifies the impossibility of its solution by any method substantially simpler than the brute-force search.     

Integer-friendly formulations for the r-separation problem

In this paper, we consider different formulations for the r-separation problem, where the objective is to choose as as many points as possible from a given set of points subject to the constraint that no two selected points can be closer than r units to one another. Our goal is to devise a mathematical programming formulation with an LP-relaxation which yields integer solutions with great frequency. We consider six different formulations of the r-separation problem. We show that the LP-relaxations of the most obvious formulations will yield fractional results in all instances of the problem if an optimal solution contains fewer than half of the given points. To build computationally effective formulations for the r-separation problem, we write dense constraints with unit right-hand-sides. The LP formulation that performs the best in our computational tests almost always finds 0–1 solutions to the problem.     

Computing closely matching upper and lower bounds on textile nesting problems

We consider an industrial cutting problem in textile manufacturing and report on algorithms for computing cutting images and lower bounds on waste for this problem. For the upper bounds we use greedy strategies based on hodographs and global optimization based on simulated annealing. For the lower bounds we use branch-and-bound methods for computing optimal solutions of placement subproblems that determine the performance of the overall subproblem. The upper bounds are computed in less than an hour on a common-day workstation and are competitive in quality with results obtained by human nesters. The lower bounds take a few hours to compute and are within 0.4% of the upper bound for certain types of clothing (e.g., for pants).     

On a generalisation of a Lehmer problem

We consider a generalisation of the classical Lehmer problem about the distribution of modular inverses in arithmetic progression, introduced by E. Alkan, F. Stan and A. Zaharescu. Using bounds for multiplicative character sums instead of bounds for Kloosterman sums traditionally applied to this kind of problem, we improve their results in several directions.     

New lower bounds for the three-dimensional orthogonal bin packing problem

In this paper, we consider the three-dimensional orthogonal bin packing problem, which is a generalization of the well-known bin packing problem. We present new lower bounds for the problem from a combinatorial point of view and demonstrate that they theoretically dominate all previous results from the literature. The comparison is also done concerning asymptotic worst-case performance ratios. The new lower bounds can be more efficiently computed in polynomial time. In addition, we study the non-oriented model, which allows items to be rotated.     

Residual a posteriori error estimates for a 3D mortar finite-element method: the Stokes system

We consider a non-conforming domain decomposition techniquefor the discretization of the three-dimensional Stokes equationsby the mortar finite-element method. Relying on the velocity–pressureformulation of the system, we perform the numerical analysisof residual error indicators for this problem and we prove thatthe error estimators provide upper and lower bounds for theenergy norm of the mortar finite-element solution.     

Static arbitrage bounds on basket option prices

We consider the problem of computing upper and lower bounds on the price of an European basket call option, given prices on other similar options. Although this problem is hard to solve exactly in the general case, we show that in some instances the upper and lower bounds can be computed via simple closed-form expressions, or linear programs. We also introduce an efficient linear programming relaxation of the general problem based on an integral transform interpretation of the call price function. We show that this relaxation is tight in some of the special cases examined before.     

On the optimal control of arrivals to a single queue with arbitrary feedback delay

We consider a problem of admission control to a single queue in discrete time. The controller has access to k step old queue lengths only, where k can be arbitrary. The problem is motivated, in particular, by recent advances in high-speed networking where information delays have become prominent. We formulate the problem in the framework of Completely Observable Controlled Markov Chains, in terms of a multi-dimensional state variable. Exploiting the structure of the problem, we show that under appropriate conditions, the multi-dimensional Dynamic Programming Equation (DPE) can be reduced to a unidimensional one. We then provide simple computable upper and lower bounds to the optimal value function corresponding to the reduced unidimensional DPE. These upper and lower bounds, along with a certain relationship among the parameters of the problem, enable us to deduce partially the structural features of the optimal policy. Our approach enables us to recover simply, in part, the recent results of Altman and Stidham, who have shown that a multiple-threshold-type policy is optimal for this problem. Further, under the same relationship among the parameters of the problem, we provide easily computable upper bounds to the multiple thresholds and show the existence of simple relationships among these upper bounds. These relationships allow us to gain very useful insights into the nature of the optimal policy. In particular, the insights obtained are of great importance for the problem of actually computing an optimal policy because they reduce the search space enormously. This revised version was published online in June 2006 with corrections to the Cover Date.     

The variable neighborhood search for the two machine flow shop problem with a passive prefetch

We consider the two machine flow shop scheduling problem with passive loading of the buffer on the second machine. To compute lower bounds for the global optimum, we present four integer linear programming formulations of the problem. Three local search methods with variable neighborhoods are developed for obtaining upper bounds. Some new large neighborhood is designed. Our methods use this neighborhood along with some other well-known neighborhoods. For computational experiments, we present a new class of test instances with known global optima. Computational results indicate a high efficiency of the proposed approach for the new class of instances as well as for other classes of instances of the problem.     

Bounds on stochastic convex allocation problems

We consider a stochastic convex program arising in a certain resource allocation problem. The uncertainty is in the demand for a resource which is to be allocated among several competing activities under convex inventory holding and shortage costs. The problem is cast as a two–period stochastic convex program and we derive tight upper and lower bounds to the problem using marginal distributions of the demands, which may be stochastically dependent. It turns out that these bounds are tighter than the usual bounds in the literature which are based on limited moment information of the underlying random variables. Numerical examples illustrate the bounds.     

Hierarchical Allocation

We consider a simple hierarchical planning process with two levels, dealing with allocation of products of facilities. When solving the aggregate problem at the higher level, detailed data are not known but upper and lower bounds are available.In the suggested planning procedure, aggregate plans are chosen by maximizing worst or best case performance with respect to these bounds.     

Semiparametric Estimation of the State of a Dynamical System with Small Noise

We consider the problem of estimation of the state of a perturbed dynamical system by observing the trajectory of a diffusion process with known small diffusion coefficient. The drift coefficient is supposed to be an unknown regular function. Asymptotic minimax lower bounds for the risk of any estimator of the state are derived and the notion of efficiency is introduced. The naïve estimator for this problem is proposed and its basic properties are discussed. It emerges that this estimator is asymptotically efficient.     

A resource investment problem with time/resource trade-offs

In this study, we consider a Resource Investment Problem with time/resource trade-offs in project networks. We assume that there is a single renewable resource and the processing requirement of an activity can be reduced by investing extra resources. Our aim is to minimize the maximum resource usage, hence, the total amount invested for the single resource, while meeting the pre-specified deadline. We formulate the problem as a mixed integer linear model and find optimal solutions for small-sized problem instances. For large-sized problem instances, we propose a heuristic solution procedure. We develop several lower bounds and use them to evaluate the performance of our heuristic procedure. The results of our computational experiments have revealed the satisfactory behaviour of our optimality properties, lower bounds and heuristic procedure.     

Online scheduling of parallel jobs on two machines is 2-competitive

We consider online scheduling of parallel jobs on parallel machines. For the problem with two machines and the objective of minimizing the makespan, we show that 2 is a tight lower bound on the competitive ratio. For the problem with m machines, we derive lower bounds using an ILP formulation.