Problems, Models and Complexity. Part I: Theory

The meaning of the term problem in operations research (OR) deviates from the understanding in the theoretical computer sciences: While an OR problem is often conceived to be stated or represented by model formulations, a computer-science problem can be viewed as a mapping from encoded instances to solutions. Such a computer-science problem turns out to be rather similar to an OR model formulation. This ambiguity may cause difficulties if the computer-science theory of computational complexity is applied in the OR context. In OR, a specific model formulation is commonly used in the analysis of the underlying problem and the results obtained for this model are simply lifted to the problem level. But this may lead to erroneous results, if the model used is not appropriate for such an analysis of the problem.To resolve this issue, we first suggest a new precise formal definition of the term problem which is identified with an equivalence class of models describing it. Afterwards, a new definition is suggested for the size of a model which depends on the assumed encoding scheme. Only models which exhibit a minimal size with respect to a reasonable encoding scheme finally turn out to be suitable for the model-based complexity analysis of an OR problem. Therefore, the appropriate choice (or if necessary the construction) of a suitable representative of an OR problem becomes an important theoretical aspect of the modelling process.     

Most probable explanations in Bayesian networks: Complexity and tractability

One of the key computational problems in Bayesian networks is computing the maximal posterior probability of a set of variables in the network, given an observation of the values of another set of variables. In its most simple form, this problem is known as the MPE-problem. In this paper, we give an overview of the computational complexity of many problem variants, including enumeration variants, parameterized problems, and approximation strategies to the MPE-problem with and without additional (neither observed nor explained) variables. Many of these complexity results appear elsewhere in the literature; other results have not been published yet. The paper aims to provide a fairly exhaustive overview of both the known and new results.     

A method of estimating computational complexity based on input conditions for N-vehicle problem

This paper proposes a method of estimating computational complexity of problem through analyzing its input condition for N-vehicle exploration problem. The N-vehicle problem is firstly formulated to determine the optimal replacement in the set of permutations of 1 to N. The complexity of the problem is factorial of N （input scale of problem）. To balance accuracy and efficiency of general algorithms, this paper mentions a new systematic algorithm design and discusses correspondence between complexity of problem and its input condition, other than just putting forward a uniform approximation algorithm as usual. This is a new technique for analyzing computation of NP problems. The method of corresponding is then presented. We finally carry out a simulation to verify the advantages of the method： 1） to decrease computation in enumeration; 2） to efficiently obtain computational complexity for any N-vehicle case; 3） to guide an algorithm design for any N-vehicle case according to its complexity estimated by the method.     

Monotonic bounds in multistage mixed-integer stochastic programming

Multistage stochastic programs bring computational complexity which may increase exponentially with the size of the scenario tree in real case problems. For this reason approximation techniques which replace the problem by a simpler one and provide lower and upper bounds to the optimal value are very useful. In this paper we provide monotonic lower and upper bounds for the optimal objective value of a multistage stochastic program. These results also apply to stochastic multistage mixed integer linear programs. Chains of inequalities among the new quantities are provided in relation to the optimal objective value, the wait-and-see solution and the expected result of using the expected value solution. The computational complexity of the proposed lower and upper bounds is discussed and an algorithmic procedure to use them is provided. Numerical results on a real case transportation problem are presented.     

Generating Functions for Computing the Myerson Value

The complexity of a computational problem is the order of computational resources which are necessary and sufficient to solve the problem. The algorithm complexity is the cost of a particular algorithm. We say that a problem has polynomial complexity if its computational complexity is a polynomial in the measure of input size. We introduce polynomial time algorithms based in generating functions for computing the Myerson value in weighted voting games restricted by a tree. Moreover, we apply the new generating algorithm for computing the Myerson value in the Council of Ministers of the European Union restricted by a communication structure.     

A combinatorial problem related to sparse systems of equations

Nowadays sparse systems of equations occur frequently in science and engineering. In this contribution we deal with sparse systems common in cryptanalysis. Given a cipher system, one converts it into a system of sparse equations, and then the system is solved to retrieve either a key or a plaintext. Raddum and Semaev proposed new methods for solving such sparse systems common in modern ciphers which are combinations of linear layers and small S-boxes. It turns out that the solution of a combinatorial MaxMinMax problem provides an upper bound on the average computational complexity of those methods. In this paper we initiate the study of a linear algebra variation of the MaxMinMax problem. The complexity bound proved in this paper significantly overcomes conjectured complexity bounds for Gröbner basis type algorithms.     

The part families problem in flexible manufacturing systems

Parts grouping into families can be performed in flexible manufacturing systems (FMSs) to simplify two classes of problems: long horizon planning and short horizon planning. In this paper the emphasis is on the part families problem applicable to the short horizon planning. Traditionally, parts grouping was based on classification and coding systems, some of which are reviewed in this paper. To overcome the drawbacks of the classical approach to parts grouping, two new methodologies are developed. The methodologies presented are very easy to implement because they take advantage of the information already stored in the CAD system. One of the basic elements of this system is the algorithm for solving the part families problem. Some of the existing clustering algorithms for solving this problem are discussed. A new clustering algorithm has been developed. The computational complexity and some of the computational results of solving the part families problem are also discussed.     

随机置换的分量与单调重新构组问题的计算等价性

In this note, it is shown that the monotone reconstruction problem is equi-valent to that of sorting, in the sense of computational complexity. In particular from any given sorting algorithm A, an algorithm B for the monotone reconstruc-tion problem can be developed with at most O(m) time and O( m) space cost more than that used in A, and vice versa. As a consequence of this result, it is obtai-ned that the time complexity of the monotone reconstruction problem of n-ele-ment random permutations is O(nlogn).     

Complexity of fuzzy answer set programming under Łukasiewicz semantics

Fuzzy answer set programming (FASP) is a generalization of answer set programming (ASP) in which propositions are allowed to be graded. Little is known about the computational complexity of FASP and almost no techniques are available to compute the answer sets of a FASP program. In this paper, we analyze the computational complexity of FASP under Łukasiewicz semantics. In particular we show that the complexity of the main reasoning tasks is located at the first level of the polynomial hierarchy, even for disjunctive FASP programs for which reasoning is classically located at the second level. Moreover, we show a reduction from reasoning with such FASP programs to bilevel linear programming, thus opening the door to practical applications. For definite FASP programs we can show P-membership. Surprisingly, when allowing disjunctions to occur in the body of rules – a syntactic generalization which does not affect the expressivity of ASP in the classical case – the picture changes drastically. In particular, reasoning tasks are then located at the second level of the polynomial hierarchy, while for simple FASP programs, we can only show that the unique answer set can be found in pseudo-polynomial time. Moreover, the connection to an existing open problem about integer equations suggests that the problem of fully characterizing the complexity of FASP in this more general setting is not likely to have an easy solution.     

A min-max version of Dijkstra's algorithm with application to perturbed optimal control problems

In this paper the computational complexity of a newly developed min-max version of Dijkstra's algorithm for solving the shortest path problem in a directed weighted hypergraph is analyzed. Together with a set oriented discretization of the state space this algorithm provides a new numerical approach for the construction of an optimally stabilizing feedback under perturbations. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Parameterized complexity of spare capacity allocation and the multicost Steiner subgraph problem

We study the computational complexity of the Spare Capacity Allocation problem arising in optical networks that use a shared mesh restoration scheme. In this problem we are given a network with edge capacities and point-to-point demands, and the goal is to allocate two edge-disjoint paths for each demand (a working path and a so-called restoration path, which is activated only if the working path fails) so that the capacity constraints are satisfied and the total cost of the used and reserved bandwidth is minimized. We focus on the setting where we deal with a group of demands together, and select their restoration paths simultaneously in order to minimize the total cost. We investigate how the computational complexity of this problem is affected by certain parameters, such as the number of restoration paths to be selected, or the treewidth of the network graph. To analyze the complexity of the problem, we introduce a generalization of the Steiner Forest problem that we call Multicost Steiner Subgraph. We study its parameterized complexity, and identify computationally easy and hard cases by providing hardness proofs as well as efficient (fixed-parameter tractable) algorithms.     

Stochastic dynamic lot-sizing problem using bi-level programming base on artificial intelligence techniques

Simulation is generally used to study non-deterministic problems in industry. When a simulation process finds the solution to an NP-hard problem, its efficiency is lowered, and computational costs increase. This paper proposes a stochastic dynamic lot-sizing problem with asymmetric deteriorating commodity, in which the optimal unit cost of material and unit holding cost would be determined. This problem covers a sub-problem of replenishment planning, which is NP-hard in the computational complexity theory. Therefore, this paper applies a decision system, based on an artificial neural network (ANN) and modified ant colony optimization (ACO) to solve this stochastic dynamic lot-sizing problem. In the methodology, ANN is used to learn the simulation results, followed by the application of a real-valued modified ACO algorithm to find the optimal decision variables. The test results show that the intelligent system is applicable to the proposed problem, and its performance is better than response surface methodology.     

Relaxed robust second-order-cone programming

In this paper, we propose an approximate optimization model for the robust second-order-cone programming problem with a single-ellipsoid uncertainty set for which the computational complexity is not known yet. We prove that this approximate robust model can be equivalently reformulated as a finite convex optimization problem.     

A SUPERLINEARLY CONVERGENT TRUST REGION ALGORITHM FOR LC^1 CONSTRAINED OPTIMIZATION PROBLEMS

In this paper, a new trust region algorithm for nonlinear equality constrained LC^1 optimization problems is given. It obtains a search direction at each iteration not by solving a quadratic programming subproblem with a trust region bound, but by solving a system of linear equations. Since the computational complexity of a QP-Problem is in general much larger than that of a system of linear equations, this method proposed in this paper may reduce the computational complexity and hence improve computational efficiency. Furthermore, it is proved under appropriate assumptions that this algorithm is globally and super-linearly convergent to a solution of the original problem. Some numerical examples are reported, showing the proposed algorithm can be beneficial from a computational point of view.     

The Haar Wavelet Analysis of Matrices and Its Applications

It is well known that Fourier analysis or wavelet analysis is a very powerful and useful tool for a function since they convert time-domain problems into frequency-domain problems. Are there similar tools for a matrix? By pairing a matrix to a piecewise function,a Haar-like wavelet is used to set up a similar tool for matrix analyzing, resulting in new methods for matrix approximation and orthogonal decomposition. By using our method, one can approximate a matrix by matrices with different orders. Our method also results in a new matrix orthogonal decomposition, reproducing Haar transformation for matrices with orders of powers of two. The computational complexity of the new orthogonal decomposition is linear. That is, for an m × n matrix, the computational complexity is O(mn). In addition,when the method is applied to k-means clustering, one can obtain that k-means clustering can be equivalently converted to the problem of finding a best approximation solution of a function. In fact, the results in this paper could be applied to any matrix related problems.In addition, one can also employ other wavelet transformations and Fourier transformation to obtain similar results.     

Packing chained items in aligned bins with applications to container transshipment and project scheduling

Bin packing problems are at the core of many well-known combinatorial optimization problems and several practical applications alike. In this work we introduce a novel variant of an abstract bin packing problem which is subject to a chaining constraint among items. The problem stems from an application of container handling in rail freight terminals, but is also of relevance in other fields, such as project scheduling. The paper provides a structural analysis which establishes computational complexity of several problem versions and develops (pseudo-)polynomial algorithms for specific subproblems. We further propose and evaluate simple and fast heuristics for optimization versions of the problem.     

GAUSSIAN PIVOTING METHOD FORSOLVING LINEAR COMPLEMENTARITY PROBLEM

In this paper, a new direct algorithm for solving linear complementarity problem with Z-matrix is proposed. The algorithm exhibits either a solution or its nonexistence after at most n steps (where n is the dimension of the problem) and the computational complexity is at most 1/3n^2 O(n^2)     

Hyperbolic set covering problems with competing ground-set elements

Motivated by a challenging problem arising in wireless network design, we investigate a new nonlinear variant of the set covering problem with hyperbolic objective function. Each ground-set element (user) competes with all its neighbors (interfering users) for a shared resource (the network access time), and the goal is to maximize the sum of the resource share assigned to each ground-set element (the network efficiency) while covering all of them. The hyperbolic objective function privileges covers with limited overlaps among selected subsets. In a sense, this variant lies in between the set partitioning problem, where overlaps are forbidden, and the standard set covering problem, where overlaps are not an issue at all. We study the complexity and approximability of generic and Euclidean versions of the problem, present an efficient Lagrangean relaxation approach to tackle medium-to-large-scale instances, and compare the computational results with those obtained by linearizations.     

一类张量特征值互补问题

矩阵特征值互补问题在力学系统领域有广泛的应用.在本文中,我们提出了一类特殊的四阶张量特征值互补问题,它是矩阵特征值互补问题的推广.我们对该特征值互补问题解的存在性,计算复杂度等性质进行了初步的研究.在一定条件下,我们建立了该互补问题同一类非线性约束优化问题的等价性联系,并由此提出了平移投影幂法来求解该特征值互补问题.     

Reducing factorization of a semiprime number to the integration of highly oscillatory functions

We reduce the problem of factoring a semiprime integer to the problem of (numerically) integrating a certain highly oscillatory function. We provide two algorithms for addressing this problem, one based on the residue theorem and the other on the (extended) Cauchy argument principle. We show that in the former algorithm, computing the residue of the function at a certain pole leads to us obtaining the factors of the semiprime integer. In the latter, we consider a contour integral for which we are able to obtain an analytical solution with several branches. The computational difficulty reduces to that of discovering the branch of the solution which gives the precise integral. We address this problem by numerically computing an upper and a lower bound of the integral and then considering the branch that fits these bounds. The time complexity of the algorithms is left as an open problem.