Higher and lower-level knowledge discovery from Pareto-optimal sets

Innovization (innovation through optimization) is a relatively new concept in the field of multi-objective engineering design optimization. It involves the use of Pareto-optimal solutions of a problem to unveil hidden mathematical relationships between variables, objectives and constraint functions. The obtained relationships can be thought of as essential properties that make a feasible solution Pareto-optimal. This paper proposes two major extensions to innovization, namely higher-level innovization and lower-level innovization. While the former deals with the discovery of common features among solutions from different Pareto-optimal fronts, the latter concerns features commonly occurring among solutions that belong to a specified (or preferred) part of the Pareto-optimal front. The knowledge of such lower-level information is extremely beneficial to a decision maker, since it focuses on a preferred set of designs. On the other hand, higher-level innovization reveals interesting knowledge about the general problem structure. Neither of these crucial aspects concerning multi-objective designs has been addressed before, to the authors’ knowledge. We develop methodologies for handling both levels of innovization by extending the authors’ earlier automated innovization algorithm and apply them to two well-known engineering design problems. Results demonstrate that the proposed methodologies are generic and are ready to be applied to other engineering design problems.     

Identifying Pareto-optimal settlements for two-party resource allocation negotiations

We explore models to identify Pareto-optimal outcomes in two-party multiple program resource allocation post-settlement settlement negotiations. The approximation of the contract curve, that is the set of Pareto-optimal outcomes, is also discussed. We consider the case where the parties split a shared hard resource. An application of the models to a resource allocation problem in a Finnish university is also discussed.     

A linear optimization problem to derive relative weights using an interval judgement matrix

In this paper, we propose a new Decision Making model, enabling to assess a finite number of alternatives according to a set of bounds on the preference ratios for the pairwise comparisons between alternatives, that is, an “interval judgement matrix”. In the case in which these bounds cannot be achieved by any assessment vector, we analyze the problem of determining of an efficient or Pareto-optimal solution from a multi-objective optimization problem. This multi-objective formulation seeks for assessment vectors that are near to simultaneously fulfil all the bound requirements imposed by the interval judgement matrix. Our new model introduces a linear optimization problem in order to define a consistency index for the interval matrix. By solving this optimization problem it can be associated a weakly efficient assessment vector to the consistency index in those cases in which the bound requirements are infeasible. Otherwise, this assessment vector fulfils all the bound requirements and has geometrical properties that make it appropriate as a representative assessment vector of the set of feasible weights.     

The Banach algebra l1(S)

Let S be the free semigroup with a finite or countably infinite set of generators plus an identity. It is shown that there is a natural involution 1 on the convolution Banach algebra l¹(S) such that (l¹(S), 1) has a separating family of finite-dimensional star representations. The star representations of the l¹-algebra of some other semigroups are also considered. The spectrum of every element of l¹(S) which is not a scalar multiple of the identity is shown to be a connected set with interior.     

Pareto-optimal reinsurance arrangements under general model settings

In this paper, we study Pareto optimality of reinsurance arrangements under general model settings. We give the necessary and sufficient conditions for a reinsurance contract to be Pareto-optimal and characterize all Pareto-optimal reinsurance contracts under more general model assumptions. We also obtain the sufficient conditions that guarantee the existence of the Pareto-optimal reinsurance contracts. When the losses of an insurer and a reinsurer are both measured by the Tail-Value-at-Risk (TVaR) risk measures, we obtain the explicit forms of the Pareto-optimal reinsurance contracts under the expected value premium principle. For the purpose of practice, we use numerical examples to show how to determine the mutually acceptable Pareto-optimal reinsurance contracts among the available Pareto-optimal reinsurance contracts such that both the insurer’s aim and the reinsurer’s goal can be met under the mutually acceptable Pareto-optimal reinsurance contracts.     

锥有效拟凹集的有效点集的连通性

本文引进了锥有效拟凹集的概念，讨论了R ^m-严格拟凹与R ^m－有效拟凹的关系，证明了一个紧集为锥有效拟凹且其有效点集为闭集时，这个有效点集是连通的。     

On 3-Steiner simplicial orderings

Let G be a connected graph and S a nonempty set of vertices of G. A Steiner tree for S is a connected subgraph of G containing S that has a minimum number of edges. The Steiner interval for S is the collection of all vertices in G that belong to some Steiner tree for S. Let k≥2 be an integer. A set X of vertices of G is k-Steiner convex if it contains the Steiner interval of every set of k vertices in X. A vertex x∈X is an extreme vertex of X if X?{x} is also k-Steiner convex. We call such vertices k-Steiner simplicial vertices. We characterize vertices that are 3-Steiner simplicial and give characterizations of two classes of graphs, namely the class of graphs for which every ordering produced by Lexicographic Breadth First Search is a 3-Steiner simplicial ordering and the class for which every ordering of every induced subgraph produced by Maximum Cardinality Search is a 3-Steiner simplicial ordering.     

Steiner intervals and Steiner geodetic numbers in distance-hereditary graphs

A Steiner tree for a set S of vertices in a connected graph G is a connected subgraph of G with a smallest number of edges that contains S. The Steiner interval I(S) of S is the union of all the vertices of G that belong to some Steiner tree for S. If S={u,v}, then I(S)=I[u,v] is called the interval between u and v and consists of all vertices that lie on some shortest u-v path in G. The smallest cardinality of a set S of vertices such that ?_u,v∈SI[u,v]=V(G) is called the geodetic number and is denoted by g(G). The smallest cardinality of a set S of vertices of G such that I(S)=V(G) is called the Steiner geodetic number of G and is denoted by sg(G). We show that for distance-hereditary graphs g(G)?sg(G) but that g(G)/sg(G) can be arbitrarily large if G is not distance hereditary. An efficient algorithm for finding the Steiner interval for a set of vertices in a distance-hereditary graph is described and it is shown how contour vertices can be used in developing an efficient algorithm for finding the Steiner geodetic number of a distance-hereditary graph.     

Connectedness of the efficient set in strictly quasiconcave vector maximization

In this paper, the concepts of quasiconcave set and strictly quasiconcave set are introduced. By using these concepts, we get a new sufficient condition for the efficient outcome set to be connected. This leads to the connectedness of the efficient solution set in strictly quasiconcave vector maximization under the mild condition that the efficient frontier is closed.The authors would like to thank Professor E. U. Choo and the referees for their many valuable comments and helpful suggestions.     

Routing sets in the integer lattice

A set of vertices S in a graph G is a routing set if it ensures some kind of connectivity between all pairs of vertices outside of S. Additional constraints may apply; a connected dominating set, for instance, is a special case of a routing set. We determine the size of a minimum routing set in subgraphs of the integer lattice, as well as (asymptotically) for the lattice itself.     

Connectedness of the Efficient Set for Three-Objective Quasiconcave Maximization Problems

For three-objective maximization problems involving continuous, semistrictly quasiconcave functions over a compact convex set, it is shown that the set of efficient solutions is connected. With that, an open problem stated by Choo, Schaible, and Chew in 1985 is solved.     

Strategic robust supply chain design based on the Pareto-optimal tradeoff between efficiency and risk

The strategic design of a robust supply chain has to determine the configuration of the supply chain so that its performance remains of a consistently high quality for all possible future conditions. The current modeling techniques often only consider either the efficiency or the risk of the supply chain. Instead, we define the strategic robust supply chain design as the set of all Pareto-optimal configurations considering simultaneously the efficiency and the risk, where the risk is measured by the standard deviation of the efficiency. We model the problem as the Mean–Standard Deviation Robust Design Problem (MSD-RDP). Since the standard deviation has a square root expression, which makes standard maximization algorithms based on mixed-integer linear programming non-applicable, we show the equivalency to the Mean–Variance Robust Design Problem (MV-RDP). The MV-RDP yields an infinite number of mixed-integer programming problems with quadratic objective (MIQO) when considering all possible tradeoff weights. In order to identify all Pareto-optimal configurations efficiently, we extend the branch-and-reduce algorithm by applying optimality cuts and upper bounds to eliminate parts of the infeasible region and the non-Pareto-optimal region. We show that all Pareto-optimal configurations can be found within a prescribed optimality tolerance with a finite number of iterations of solving the MIQO. Numerical experience for a metallurgical case is reported.     

Inequalities of Nordhaus-Gaddum type for doubly connected domination number

A set S of vertices of a connected graph G is a doubly connected dominating set if every vertex not in S is adjacent to some vertex in S and the subgraphs induced by S and V−S are connected. The doubly connected domination numberγ_cc(G) is the minimum size of such a set. We prove that when G and are both connected of order n, and we describe the two infinite families of extremal graphs achieving the bound.     

The weak McShane integral

We present a weaker version of the Fremlin generalized McShane integral (1995) for functions defined on a σ-finite outer regular quasi Radon measure space (S,Σ, T, µ) into a Banach space X and study its relation with the Pettis integral. In accordance with this new method of integration, the resulting integral can be expressed as a limit of McShane sums with respect to the weak topology. It is shown that a function f from S into X is weakly McShane integrable on each measurable subset of S if and only if it is Pettis and weakly McShane integrable on S. On the other hand, we prove that if an X-valued function is weakly McShane integrable on S, then it is Pettis integrable on each member of an increasing sequence (S _l ) _l?1 of measurable sets of finite measure with union S. For weakly sequentially complete spaces or for spaces that do not contain a copy of c ₀, a weakly McShane integrable function on S is always Pettis integrable. A class of functions that are weakly McShane integrable on S but not Pettis integrable is included.     

Pareto-optimal contracts for a supply chain with satisficing objectives

We analyse a decentralized supply chain consisting of a supplier and a retailer, each with a satisficing objective, that is, to maximize the probability of achieving a predetermined target profit. The supply chain is examined under two types of commonly used contracts: linear tariff contracts (including wholesale price contracts as special cases) and buy-back contracts. First, we identify the Pareto-optimal contract(s) for each contractual form. In particular, it is shown that there is a unique wholesale price that is Pareto optimal for both contractual types. Second, we evaluate the performance of the Pareto-optimal contracts. In contrast to the well-known results for a supply chain with the traditional expected profit objectives, we show that wholesale price contracts can coordinate the supply chain whereas buy-back contracts cannot. This provides an additional justification for the popularity of wholesale price contracts besides their simplicities and lower administration costs.     

On almost rc-Lindelöf sets

In [4], Dlaska introduced the class of almost rc-Lindelöf sets and studied some basic properties of such sets. In this paper, we obtain further results concerning almost rc-Lindelöf sets. We also introduce new concepts to obtain several mapping properties concerning almost rc-Lindelöf sets and almost rc-Lindelöf spaces. The property of being an almost rc-Lindelöf set is invariant under functions which are slightly continuous and weakly θ-irresolute. It is also shown that the property of being an almost rc-Lindelöf space is inverse invariant under functions which are weakly almost open, ω-regular open, and whose fibers are S-sets.     

Geodetic and Steiner geodetic sets in 3-Steiner distance hereditary graphs

Let G be a connected graph and S⊆V(G). Then the Steiner distance of S, denoted by d_G(S), is the smallest number of edges in a connected subgraph of G containing S. Such a subgraph is necessarily a tree called a Steiner tree for S. The Steiner interval for a set S of vertices in a graph, denoted by I(S) is the union of all vertices that belong to some Steiner tree for S. If S={u,v}, then I(S) is the interval I[u,v] between u and v. A connected graph G is 3-Steiner distance hereditary (3-SDH) if, for every connected induced subgraph H of order at least 3 and every set S of three vertices of H, d_H(S)=d_G(S). The eccentricity of a vertex v in a connected graph G is defined as e(v)=max{d(v,x)|x∈V(G)}. A vertex v in a graph G is a contour vertex if for every vertex u adjacent with v, e(u)?e(v). The closure of a set S of vertices, denoted by I[S], is defined to be the union of intervals between pairs of vertices of S taken over all pairs of vertices in S. A set of vertices of a graph G is a geodetic set if its closure is the vertex set of G. The smallest cardinality of a geodetic set of G is called the geodetic number of G and is denoted by g(G). A set S of vertices of a connected graph G is a Steiner geodetic set for G if I(S)=V(G). The smallest cardinality of a Steiner geodetic set of G is called the Steiner geodetic number of G and is denoted by sg(G). We show that the contour vertices of 3-SDH and HHD-free graphs are geodetic sets. For 3-SDH graphs we also show that g(G)?sg(G). An efficient algorithm for finding Steiner intervals in 3-SDH graphs is developed.     

On finding an envy-free Pareto-optimal division

This paper describes an algorithm to find an (α-)envy-free Pareto-optimal division in the case of a finite number of homogeneous infinitely divisible goods and linear utility functions. It is used to find an allocation in the classical cake division problem that is almost Pareto-optimal and α-envy-free.     

On the characterization of Pareto-optimal solutions in bicriterion optimization

For bicriterion optimization involving objective functionsf ₁ andf ₂ defined on a decision spaceX, a condition is presented under which the Pareto-optimal points can be characterized as solutions of the scalar optimization problems: Minimizef ₁(x), subject tof ₂(x),x X, which ranges over a certain interval. Using this condition, it is shown how the Pareto-optimal points can be so characterized in both convex and nonconvex situations.The author gratefully acknowledges Dr. Ivan Singer, Institute of Mathematics, Rumanian Academy of Sciences, Bucharest, Rumania, for pointing out the relevance of Remark 7 in Ref. 7 to the results of this note.     

The upper connected geodetic number and forcing connected geodetic number of a graph

For a connected graph G of order p≥2, a set S⊆V(G) is a geodetic set of G if each vertex v∈V(G) lies on an x-y geodesic for some elements x and y in S. The minimum cardinality of a geodetic set of G is defined as the geodetic number of G, denoted by g(G). A geodetic set of cardinality g(G) is called a g-set of G. A connected geodetic set of G is a geodetic set S such that the subgraph G[S] induced by S is connected. The minimum cardinality of a connected geodetic set of G is the connected geodetic number of G and is denoted by g_c(G). A connected geodetic set of cardinality g_c(G) is called a g_c-set of G. A connected geodetic set S in a connected graph G is called a minimal connected geodetic set if no proper subset of S is a connected geodetic set of G. The upper connected geodetic number is the maximum cardinality of a minimal connected geodetic set of G. We determine bounds for and determine the same for some special classes of graphs. For positive integers r,d and n≥d+1 with r≤d≤2r, there exists a connected graph G with , and . Also, for any positive integers 2≤a<b≤c, there exists a connected graph G such that g(G)=a, g_c(G)=b and . A subset T of a g_c-set S is called a forcing subset for S if S is the unique g_c-set containing T. A forcing subset for S of minimum cardinality is a minimum forcing subset of S. The forcing connected geodetic number of S, denoted by f_c(S), is the cardinality of a minimum forcing subset of S. The forcing connected geodetic number of G, denoted by f_c(G), is f_c(G)=min{f_c(S)}, where the minimum is taken over all g_c-sets S in G. It is shown that for every pair a,b of integers with 0≤a≤b−4, there exists a connected graph G such that f_c(G)=a and g_c(G)=b.