The minimum spanning tree problem with fuzzy costs

In this paper the minimum spanning tree problem in a given connected graph is considered. It is assumed that the edge costs are not precisely known and they are specified as fuzzy intervals. Possibility theory is applied to characterize the optimality of edges of the graph and to choose a spanning tree under fuzzy costs.     

Two-dimensional molecular sieves: structure design by computer simulations

Nanoporous molecular networks formed spontaneously by organic molecules adsorbed on solid substrates are promising materials for future nanotechnological applications related to separation and catalysis. With their unique ordered structure comprising nanocavities of a regular shape planar networks can be treated as 2D analogs of bulk nanoporous materials. In this report we demonstrate how the Monte Carlo simulation method can be effectively used to predict morphology of self-assembled porous molecular architectures based on structural properties of a building block. The simulated results refer to the assemblies created by cross-shaped organic molecules which are stabilized by different intermolecular interactions, including hydrogen bonding and van der Waals interactions. It is demonstrated that tuning of size and aspect ratio of the building block enables the creation of largely diversified extended structures comprising pores of a square and rectangular shape. Our theoretical predictions can be helpful in custom design of functional adsorbed overlayers for controlled deposition, sensing and separation of guest molecules.     

The robust shortest path problem in series-parallel multidigraphs with interval data

In this paper the robust shortest path problem in edge series-parallel multidigraphs with interval costs is examined. The maximal regret criterion is applied to calculate the optimal solution. It is shown that this problem is NP-hard. A pseudopolynomial algorithm for the studied problem is constructed.     

On combinatorial optimization problems on matroids with uncertain weights

In this paper the combinatorial optimization problem on weighted matroid is considered. It is assumed that the weights in the problem are ill-known and they are modeled as fuzzy intervals. The optimality of solutions and the optimality of elements are characterized. This characterization is performed in the setting of possibility theory. A method of choosing a solution under uncertainty is also proposed.     

Bottleneck combinatorial optimization problems with uncertain costs and the OWA criterion

In this paper a class of bottleneck combinatorial optimization problems with uncertain costs is discussed. The uncertainty is modeled by specifying a discrete scenario set containing a finite number of cost vectors, called scenarios. In order to choose a solution the Ordered Weighted Averaging aggregation operator (OWA for short) is applied. The OWA operator generalizes traditional criteria in decision making under uncertainty such as the maximum, minimum, average, median, or Hurwicz criterion. New complexity and approximation results in this area are provided. These results are general and remain valid for many problems, in particular for a wide class of network problems.     

The 0-1 knapsack problem with fuzzy data

The 0-1 knapsack problem with imprecise profits and imprecise weights of items is considered. The imprecise parameters are modeled as fuzzy intervals. A method of choosing a solution under the uncertainty is proposed and two methods for solving the constructed models are provided.     

On Multifunctionals in the Musielak-Orlicz Spaces of Multifunctions

We introduce the notions of X_d,s(x),φ-linear multifunctional and X_d,s(x),φ-linear continuous multifunctional. We generalize the theorems on linear bounded functionals in the Musielak-Orlicz space.     

Approximating a two-machine flow shop scheduling under discrete scenario uncertainty

This paper deals with the two machine permutation flow shop problem with uncertain data, whose deterministic counterpart is known to be polynomially solvable. In this paper, it is assumed that job processing times are uncertain and they are specified as a discrete scenario set. For this uncertainty representation, the min-max and min-max regret criteria are adopted. The min-max regret version of the problem is known to be weakly NP-hard even for two processing time scenarios. In this paper, it is shown that the min-max and min-max regret versions of the problem are strongly NP-hard even for two scenarios. Furthermore, the min-max version admits a polynomial time approximation scheme if the number of scenarios is constant and it is approximable with performance ratio of 2 and not (4/3 − ?)-approximable for any ? > 0 unless P = NP if the number of scenarios is a part of the input. On the other hand, the min-max regret version is not at all approximable even for two scenarios.     

Possibilistic bottleneck combinatorial optimization problems with ill-known weights

In this paper a general bottleneck combinatorial optimization problem with uncertain element weights modeled by fuzzy intervals is considered. A possibilistic formalization of the problem and solution concepts in this setting, which lead to compute robust solutions under fuzzy weights, are given. Some algorithms for finding a solution according to the introduced concepts and evaluating optimality of solutions and elements are provided. These algorithms are polynomial for bottleneck combinatorial optimization problems with uncertain element weights, if their deterministic counterparts are polynomially solvable.