On computational search for optimistic solutions in bilevel problems

The linear-linear and quadratic-linear bilevel programming problems are considered. Their optimistic statement is reduced to a nonconvex mathematical programming problem with the bilinear structure. Approximate algorithms of local and global search in the obtained problems are proposed. The results of computational solving randomly generated test problems are given and analyzed.     

The computational complexity of graph problems with succinct multigraph representation

The complexity of graph problems is investigated when the graphs are presented asvertex multiplicity graphs. In this presentation an independent set of vertices which are connected in the same way with the remaining vertices of the graph can be described by giving only one vertex and the size of the independent set in binary. Using this succinct graph presentation one can expect that the complexity of graph problems can blow up exponentially. In fact, it is shown that the RNC-problems UNARY NETWORK FLOW and PERFECT MATCHING becomeP-complete, that the NP-complete problems CHLIQUE, MAXIMUM INDEPENDENT SET and CHROMATIC NUMBER remain NP-complete and that aP-complete version of the CIRCUIT VALUE problem becomes PSPACE-complete.Supported in part by DFG Grant WA 594/1-1.     

Combinatorial flexibility problems and their computational complexity

The concept of flexibility—originated in the context of heat exchanger networks—is associated with a substructure which guarantees the performance of the original structure, in a given range of possible states. We extend this concept to combinatorial optimization problems, and prove several computational complexity results in this new framework.Under some monotonicity conditions, we prove that a combinatorial optimization problem polynomially transforms to its associated flexibility problem, but that the converse need not be true.In order to obtain polynomial flexibility problems, we have to restrict ourselves to combinatorial optimization problems on matroids. We also prove that, when relaxing in different ways the matroid structure, the flexibility problems become NP-complete. This fact is shown by proving the NP-completeness of the flexibility problems associated with the Shortest Path, Minimum Cut and Weighted Matching problems.     

Solving large quadratic assignment problems on computational grids

The quadratic assignment problem (QAP) is among the hardest combinatorial optimization problems. Some instances of size n = 30 have remained unsolved for decades. The solution of these problems requires both improvements in mathematical programming algorithms and the utilization of powerful computational platforms. In this article we describe a novel approach to solve QAPs using a state-of-the-art branch-and-bound algorithm running on a federation of geographically distributed resources known as a computational grid. Solution of QAPs of unprecedented complexity, including the nug30, kra30b, and tho30 instances, is reported. Received: September 29, 2000 / Accepted: June 5, 2001?Published online October 2, 2001     

The computational complexity of basic decision problems in 3-dimensional topology

We study the computational complexity of basic decision problems of 3-dimensional topology, such as to determine whether a triangulated 3-manifold is irreducible, prime, ∂-irreducible, or homeomorphic to a given 3-manifold M. For example, we prove that the problem to recognize whether a triangulated 3-manifold is homeomorphic to a 3-sphere, or to a 2-sphere bundle over a circle, or to a real projective 3-space, or to a handlebody of genus g, is decidable in nondeterministic polynomial time (NP) of size of the triangulation. We also show that the problem to determine whether a triangulated orientable 3-manifold is irreducible (or prime) is in PSPACE and whether it is ∂-irreducible is in coNP. The proofs improve and extend arguments of prior author’s article on the recognition problem for the 3-sphere.      

The computational complexity and approximability of a series of geometric covering problems

We consider a system of three ordinary first-order differential equations known in the theory of nuclear magnetism as the Bloch equations. The system contains four dimensionless parameters as coefficients. Equilibrium states and the dependence of their stability on these parameters are investigated. The possibility of the appearance of two stable equilibrium states is discovered. The equations are integrable in the absence of dissipation. For the problem with small dissipation far from equilibrium, approximate solutions are constructed by the method of averaging.     

The complexity of multiple wordlength assignment

This note discusses the multiple wordlength assignment problem for the design of custom digital signal processing (DSP) parallel processors. It is demonstrated that this assignment problem is NP-hard.     

The zero pivot phenomenon in transportation and assignment problems and its computational implications

Transportation and assignment models have been widely used in many applications. Their use was motivated, among other reasons, by the existence of efficient solution methods and their occurrence as sub-problems in the solution of combinatorial problems. A previous study [10] observed that, in large-scale Transportation and Assignment Problems, 95 percent of the pivots were zero or degenerate pivots. This study investigates the ratio of zero pivots to the total number of pivots and verifies the above observation under conditions of small rim variability. Rules are introduced that pay special attention to the zero pivot phenomenon, and significantly reduce CPU time in both phase-1 (generating the initial basic feasible solution) and in phase-2 (selecting the variable leaving the base and the variable entering the base). When these rules were applied, they reduced the CPU time substantially: a 500×500 assignment problem was solved in 1.3 seconds.Part of this research was done while the author was at IBM Israel Scientific Center.     

Multistage bilevel programming problems

In this article, we first examine some modeling scenarios for a multistage bilevel programming problem and develop the solution techniques based on certain reformulations of the original problem. The optimality conditions obtained for a class of multistage problems are given in terms of the second order subdifferentials of Mordukhovich.     

The computational complexity of the criticality problems in a network with interval activity times

The paper analyzes the criticality in a network with interval activities duration times. A natural generalization of the criticality notion (for a path, an activity and an event) for the case of network with interval activity duration times is given. The computation complexity of five problems linked to the introduced criticality notion is presented.     

The computational complexity of the pooling problem

The pooling problem is an extension of the minimum cost flow problem defined on a directed graph with three layers of nodes, where quality constraints are introduced at each terminal node. Flow entering the network at the source nodes has a given quality, at the internal nodes (pools) the entering flow is blended, and then sent to the terminal nodes where all entering flow streams are blended again. The resulting flow quality at the terminals has to satisfy given bounds. The objective is to find a cost-minimizing flow assignment that satisfies network capacities and the terminals’ quality specifications. Recently, it was proved that the pooling problem is NP-hard, and that the hardness persists when the network has a unique pool. In contrast, instances with only one source or only one terminal can be formulated as compact linear programs, and thereby solved in polynomial time. In this work, it is proved that the pooling problem remains NP-hard even if there is only one quality constraint at each terminal. Further, it is proved that the NP-hardness also persists if the number of sources and the number of terminals are no more than two, and it is proved that the problem remains hard if all in-degrees or all out-degrees are at most two. Examples of special cases in which the problem is solvable by linear programming are also given. Finally, some open problems, which need to be addressed in order to identify more closely the borderlines between polynomially solvable and NP-hard variants of the pooling problem, are pointed out.     

The computational complexity of evolutionarily stable strategies

The concept of evolutionarily stable strategies (ESS) has been central to applications of game theory in evolutionary biology, and it has also had an influence on the modern development of game theory. A regular ESS is an important refinement the ESS concept. Although there is a substantial literature on computing evolutionarily stable strategies, the precise computational complexity of determining the existence of an ESS in a symmetric two-player strategic form game has remained open, though it has been speculated that the problem is -hard. In this paper we show that determining the existence of an ESS is both -hard and -hard, and that the problem is contained in , the second level of the polynomial time hierarchy. We also show that determining the existence of a regular ESS is indeed -complete. Our upper bounds also yield algorithms for computing a (regular) ESS, if one exists, with the same complexities.     

The computational complexity of multi-level linear programs

We show that (L+1)-level linear programs are as difficult as levelL of the polynomial-time hierarchy, even if one only considers problems with unique optimal solutions.Dedicated to Robert Jeroslow (1942–1988)     

Polynomial complexity algorithms for computational problems in the theory of algebraic curves

It is proved that the classical algorithm for constructing Newton-Puiseux expansions for the roots of polynomials using the method of Newton polygons is of polynomial complexity in the notation length of the expansion coefficients. This result is used, in the case of a ground field of characteristic O, to construct polynomial-time algorithms for factoring polynomials over fields of formal power series, and for fundamental computational problems in the theory of algebraic curves, such as curve normalization.Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova Akademii Nauk SSSR, Vol. 176, pp. 127–150, 1989.     

Scheduling problems with position dependent job processing times: computational complexity results

In this paper, we analyse single machine scheduling problems with learning and aging effects to minimize one of the following objectives: the makespan with release dates, the maximum lateness and the number of late jobs. The phenomena of learning and aging are modeled by job processing times described by non-increasing (learning) or non-decreasing (aging) functions dependent on the number of previously processed jobs, i.e., a job position in a sequence. We prove that the considered problems are strongly NP-hard even if job processing times are described by simple linear functions dependent on a number of processed jobs. Additionally, we show a property of equivalence between problems with learning and aging models. We also prove that if the function describing decrease/increase of a job processing time is the same for each job then the problems with the considered objectives are polynomially solvable even if the function is arbitrary. Therefore, we determine the boundary between polynomially solvable and strongly NP-hard cases.     

Infeasible-interior-point algorithm for a class of nonmonotone complementarity problems and its computational complexity

This paper presents an infeasible-interior-point algorithm for a class of nonmonotone complementarity problems, and analyses its convergence and computational complexity. The results indicate that the proposed algorithm is a polynomial-time one.     

Reducibility of bilevel programming problems to vector optimization problems

Reductions are studied of the bilevel programming problems to vector (multicriteria) optimization problems. A general framework is proposed for constructing these reductions. Some particular cases of bilevel problems are considered.