An accelerated approach for solving fuzzy relation equations with a linear objective function

In literature, the optimization model with a linear objective function subject to fuzzy relation equations has been converted into a 0-1 integer programming problem by Fang and Li (1999). They proposed a jump-tracking branch-and-bound method to solve this 0-1 integer programming problem. In this paper, we propose an upper bound for the optimal objective value. Based on this upper bound and rearranging the structure of the problem, we present a backward jump-tracking branch-and-bound scheme for solving this optimization problem. A numerical example is provided to illustrate our scheme. Furthermore, testing examples show that the performance of our scheme is superior to the procedure in the paper by Fang and Li. Several testing examples show that our initial upper bound is sharp.     

Adversary lower bounds for nonadaptive quantum algorithms

We present two general methods for proving lower bounds on the query complexity of nonadaptive quantum algorithms. Both methods are based on the adversary method of Ambainis. We show that they yield optimal lower bounds for several natural problems, and we challenge the reader to determine the nonadaptive quantum query complexity of the “1-to-1 versus 2-to-1” problem and of Hidden Translation.In addition to the results presented at Wollic 2008 in the conference version of this paper, we show that the lower bound given by the second method is always at least as good (and sometimes better) as the lower bound given by the first method. We also compare these two quantum lower bounds to probabilistic lower bounds.     

Property Testing Lower Bounds via Communication Complexity

We develop a new technique for proving lower bounds in property testing, by showing a strong connection between testing and communication complexity. We give a simple scheme for reducing communication problems to testing problems, thus allowing us to use known lower bounds in communication complexity to prove lower bounds in testing. This scheme is general and implies a number of new testing bounds, as well as simpler proofs of several known bounds. For the problem of testing whether a Boolean function is k-linear (a parity function on k variables), we achieve a lower bound of ??(k) queries, even for adaptive algorithms with two-sided error, thus confirming a conjecture of Goldreich (2010a). The same argument behind this lower bound also implies a new proof of known lower bounds for testing related classes such as k-juntas. For some classes, such as the class of monotone functions and the class of s-sparse GF(2) polynomials, we significantly strengthen the best known bounds.     

Computationally efficient solution of the multi-item, capacitated lot-sizing problem

The problem of multi-item, single-level, dynamic lotsizing in the presence of a single capacitated resource is addressed. A model based on variable redefinition is developed leading to a solution strategy based on a branch-and-bound search with sharp low bounds. The multi-item low bound problems are solved by column generation with the capacity constraints as the linking constraints. The resulting subproblems separate into as many single-item, uncapacitated lotsizing problems as there are items. These subproblems are solved as shortest-path problems. Good upper bounds are also generated by solving an appropriate minimum-cost network flow problem at each node of the branch-and-bound tree. The resulting solution scheme is very efficient in terms of computation time. Its efficiency is demonstrated by computational testing on a ste of benchmark problem instances and is attributable to the sharpness of the lower bounds, the efficiency with which the low bound problems are solved and the frequent generation of good upper bounds; all of which leading to a high exclusion rate.     

On the complexity of a two-point boundary value problem in different settings

We study the complexity of a two-point boundary value problem. We concentrate on the linear problem of order k with separated boundary conditions. Right-hand side functions are assumed to be r times differentiable with all derivatives bounded by a constant. We consider three models of computation: deterministic with standard and linear information, randomized and quantum. In each setting, we construct an algorithm for solving the problem, which allows us to establish upper complexity bounds. In the deterministic setting, we show that the use of linear information gives us a speed-up of at least one order of magnitude compared with the standard information. For randomized algorithms, we show that the speed-up over standard deterministic algorithms is by 1/2 in the exponent. For quantum algorithms, we can achieve a speed-up by one order of magnitude. We also provide lower complexity bounds. They match upper bounds in the deterministic setting with the standard information, and almost match upper bounds in the randomized and quantum settings. In the deterministic setting with the linear information, a gap still remains between the upper and lower complexity bounds.     

A new branch-and-bound algorithm for standard quadratic programming problems

In this paper we propose convex and LP bounds for standard quadratic programming (StQP) problems and employ them within a branch-and-bound approach. We first compare different bounding strategies for StQPs in terms both of the quality of the bound and of the computation times. It turns out that the polyhedral bounding strategy is the best one to be used within a branch-and-bound scheme. Indeed, it guarantees a good quality of the bound at the expense of a very limited computation time. The proposed branch-and-bound algorithm performs an implicit enumeration of all the KKT (stationary) points of the problem. We compare different branching strategies exploiting the structure of the problem. Numerical results on randomly generated problems (with varying density of the underlying convexity graph) are reported which show the effectiveness of the proposed approach, in particular in limiting the growth of the number of nodes in the branch-and-bound tree as the density of the underlying graph increases.     

Approximate branch-and-bound global optimization using B-spline hypervolumes

This paper presents a B-spline-based branch-and-bound algorithm for unconstrained global optimization. The key components of the branch-and-bound, a well-known algorithm paradigm for global optimization, are a subdivision scheme and a bound calculation scheme. For these schemes, we first introduce a B-spline hypervolume to approximate an objective function defined in a design space, where the approximation is based on Latin-hypercube sampling points. We then describe a proposed algorithm for finding global solutions approximately within a prescribed tolerance. The algorithm includes two procedures that are performed iteratively until all stopping conditions are satisfied. One involves subdivision into mutually disjoint subspaces and computation of their bound information, both of which are accomplished by using B-spline hypervolumes. The other updates a search tree that represents a hierarchical structure of subdivided subspaces during the solution process. Finally, we examine the computational performance of the proposed algorithm on various test problems that cover most of the difficulties encountered in global optimization. The results show that the proposed algorithm is complete without using heuristics and has good potential for application in large-scale NP-hard optimization.     

A comparison of lower bounds for the single-machine early/tardy problem

This paper considers the single-machine early/tardy problem. The paper presents a procedure that integrates a timetabling algorithm into a lower bound for jobs not included in a partial sequence. The paper also shows how two lower bounds that were developed previously for the problem can be improved. The lower bounds are tested on problems of various sizes and parameters for the distribution of due dates. The results show that the lower bounds are able to increase the efficiency of a branch-and-bound algorithm.     

Lower Bounds for Randomized Exclusive Write PRAMs

In this paper we study the question: How useful is randomization in speeding up Exclusive Write PRAM computations? Our results give further evidence that randomization is of limited use in these types of computations. First we examine a compaction problem on both the CREW and EREW PRAM models, and we present randomized lower bounds which match the best deterministic lower bounds known. (For the CREW PRAM model, the lower bound is asymptotically optimal.) These are the first nontrivial randomized lower bounds known for the compaction problem on these models. We show that our lower bounds also apply to the problem of approximate compaction. Next we examine the problem of computing boolean functions on the CREW PRAM model, and we present a randomized lower bound which improves on the previous best randomized lower bound for many boolean functions, including the OR function. (The previous lower bounds for these functions were asymptotically optimal, but we improve the constant multiplicative factor.) We also give an alternate proof for the randomized lower bound on PARITY, which was already optimal to within a constant additive factor. Lastly, we give a randomized lower bound for integer merging on an EREW PRAM which matches the best deterministic lower bound known. In all our proofs, we use the Random Adversary method, which has previously only been used for proving lower bounds on models with Concurrent Write capabilities. Thus this paper also serves to illustrate the power and generality of this method for proving parallel randomized lower bounds. Received October 2, 1995, and in final form January 29, 1997.     

Complexity of solving the Subset Sum problem with the branch-and-bound method with domination and cardinality filtering

We obtain an exact upper bound on the complexity of solving the Subset Sum problem with a variation of the branch-and-bound method of a special form. Complexity is defined as the number of subproblems considered in the process of solving the original problem. Here we reduce the enumeration by using the domination relation. We construct an instance of the Subset Sum problem on which our bound is realized. The resulting bound is asymptotically twice smaller than the exact upper bound on the complexity of solving this problem with a standard version of the branch-and-bound method.     

Scheduling two-machine no-wait open shops to minimize makespan

This paper examines the problem of scheduling two-machine no-wait open shops to minimize makespan. The problem is known to be strongly NP-hard. An exact algorithm, based on a branch-and-bound scheme, is developed to optimally solve medium-size problems. A number of dominance rules are proposed to improve the search efficiency of the branch-and-bound algorithm. An efficient two-phase heuristic algorithm is presented for solving large-size problems. Computational results show that the branch-and-bound algorithm can solve problems with up to 100 jobs within a reasonable amount of time. For large-size problems, the solution obtained by the heuristic algorithm has an average percentage deviation of 0.24% from a lower bound value.     

On the performance of MaxSAT and MinSAT solvers on 2SAT-MaxOnes

We analyze and compare two solvers for Boolean optimization problems: WMaxSatz, a solver for Partial MaxSAT, and MinSatz, a solver for Partial MinSAT. Both MaxSAT and MinSAT are similar, but previous results indicate that when solving optimization problems using both solvers, the performance is quite different on some cases. For getting insights about the differences in the performance of the two solvers, we analyze their behaviour when solving 2SAT-MaxOnes problem instances, given that 2SAT-MaxOnes is probably the most simple, but NP-hard, optimization problem we can solve with them. The analysis is based first on the study of the bounds computed by both algorithms on some particular 2SAT-MaxOnes instances, characterized by the presence of certain particular structures. We find that the fraction of positive literals in the clauses is an important factor regarding the quality of the bounds computed by the algorithms. Then, we also study the importance of this factor on the typical case complexity of Random-p 2SAT-MaxOnes, a variant of the problem where instances are randomly generated with a probability p of having positive literals in the clauses. For the case p=0, the performance results indicate a clear advantage of MinSatz with respect to WMaxSatz, but as we consider positive values of p WMaxSatz starts to show a better performance, although at the same time the typical complexity of Random-p 2SAT-MaxOnes decreases as p increases. We also study the typical value of the bound computed by the two algorithms on these sets of instances, showing that the behaviour is consistent with our analysis of the bounds computed on the particular instances we studied first.     

A branch-and-bound algorithm for single machine scheduling with quadratic earliness and tardiness penalties

This paper considers the problem of scheduling a single machine, in which the objective function is to minimize the weighted quadratic earliness and tardiness penalties and no machine idle time is allowed. We develop a branch and bound algorithm involving the implementation of lower and upper bounding procedures as well as some dominance rules. The lower bound is designed based on a lagrangian relaxation method and the upper bound includes two phases, one for constructing initial schedules and the other for improving them. Computational experiments on a set of randomly generated instances show that one of the proposed heuristics, used as an upper bound, has an average gap less than 1.3% for instances optimally solved. The results indicate that both the lower and upper bounds are very tight and the branch-and-bound algorithm is the first algorithm that is able to optimally solve problems with up to 30 jobs in a reasonable amount of time.     

Branch-and-bound algorithm for the maximum triangle packing problem

This work addresses the problem of finding the maximum number of unweighted vertex-disjoint triangles in an undirected graph G. It is a challenging NP-hard combinatorial problem and it is well-known to be APX-hard. A branch-and-bound algorithm which uses a lower bound based on neighborhood degree is presented. A naive upper bound is proposed as well as another one based on a surrogate relaxation of the related integer linear program which is analogous to a multidimensional knapsack problem. Further, a Greedy Search algorithm and a genetic algorithm are described to improve the lower bound. A computational comparison of lower bounds, branch-and-bound algorithm and CPLEX solver is provided using randomly generated benchmarks and well-known DIMACS implementation challenges. The empirical study shows that the branch-and-bound finds the optimal triangle packing solution for small randomly generated MTP instances (up to 100 vertices and 200 triangles) and some DIMACS graphs. For some larger instances and DIMACS challenges graphs, we remark that our lower bound outperforms CPLEX solver regarding the triangle packing solution and the computation time.     

Kolmogorov complexity and combinatorial methods in communication complexity

We introduce a method based on Kolmogorov complexity to prove lower bounds on communication complexity. The intuition behind our technique is close to information theoretic methods.We use Kolmogorov complexity for three different things: first, to give a general lower bound in terms of Kolmogorov mutual information; second, to prove an alternative to Yao’s minmax principle based on Kolmogorov complexity; and finally, to identify hard inputs.We show that our method implies the rectangle and corruption bounds, known to be closely related to the subdistribution bound. We apply our method to the hidden matching problem, a relation introduced to prove an exponential gap between quantum and classical communication. We then show that our method generalizes the VC dimension and shatter coefficient lower bounds. Finally, we compare one-way communication and simultaneous communication in the case of distributional communication complexity and improve the previous known result.     

Heuristic and exact algorithms for the max–min optimization of the multi-scenario knapsack problem

We are concerned with a variation of the standard 0–1 knapsack problem, where the values of items differ under possible S scenarios. By applying the ‘pegging test’ the ordinary knapsack problem can be reduced, often significantly, in size; but this is not directly applicable to our problem. We introduce a kind of surrogate relaxation to derive upper and lower bounds quickly, and show that, with this preprocessing, the similar pegging test can be applied to our problem. The reduced problem can be solved to optimality by the branch-and-bound algorithm. Here, we make use of the surrogate variables to evaluate the upper bound at each branch-and-bound node very quickly by solving a continuous knapsack problem. Through numerical experiments we show that the developed method finds upper and lower bounds of very high accuracy in a few seconds, and solves larger instances to optimality faster than the previously published algorithms.     

Rolling-horizon and fix-and-relax heuristics for the parallel machine lot-sizing and scheduling problem with sequence-dependent set-up costs

In this paper we develop new rolling-horizon and fix-and-relax heuristics for the identical parallel machine lot-sizing and scheduling problem with sequence-dependent set-up costs. Unlike previous papers, our procedures are based on a compact formulation relying on the hypotheses of identical machines. This feature makes our approach suitable for large-scale applications (with hundreds of machines) arising in the textile and fiberglass industries. Moreover, our procedures are shown to provide a feasible solution for any feasible instance. Comparisons with lower bounds provided by a truncated branch-and-bound show that the gap between the best heuristic solution and the lower bound never exceeds 3%.     

Online algorithms for scheduling two parallel machines with a single server

We consider an online scheduling problem on two identical parallel machines with a single server. Jobs arrive one by one and each job has to be loaded by the server before being processed on one of the machines, and unloaded immediately by the server after its processing. Both loading and unloading times are equal to one time unit. The goal is to minimize the makespan. For the variant of the problem involving both loading and unloading operations, we present an online algorithm with competitive ratio of 5/3. For the variant with loading operation only, we show that the competitive ratio of list scheduling is at least 8/5 and provide an improved online algorithm with competitive ratio of 11/7. Finally, we discuss the lower bounds for these problems. We show that both variants have a lower bound of 3/2. Furthermore, we show that the lower bound of the first variant is at least 8/5 if the online algorithm satisfies a certain constraint.     

Lower bounds on precedence-constrained scheduling for parallel processors

We consider two general precedence-constrained scheduling problems that have wide applicability in the areas of parallel processing, high performance compiling, and digital system synthesis. These problems are intractable so it is important to be able to compute tight bounds on their solutions. A tight lower bound on makespan scheduling can be obtained by replacing precedence constraints with release and due dates, giving a problem that can be efficiently solved. We demonstrate that recursively applying this approach yields a bound that is provably tighter than other known bounds, and experimentally shown to achieve the optimal value at least 90.3% of the time over a synthetic benchmark.We compute the best known lower bound on weighted completion time scheduling by applying the recent discovery of a new algorithm for solving a related scheduling problem. Experiments show that this bound significantly outperforms the linear programming-based bound. We have therefore demonstrated that combinatorial algorithms can be a valuable alternative to linear programming for computing tight bounds on large scheduling problems.