“Miniaturized” Linearizations for Quadratic 0/1 Problems

In order to solve a quadratic 0/1 problem, some techniques, consisting in deriving a linear integer formulation, are used. Those techniques, called “linearization”, usually involve a huge number of additional variables. As a consequence, the exact resolution of the linear model is, in general, very difficult. Our aim, in this paper, is to propose “economical” linear models. Starting from an existing linearization (typically the so-called “classical linearization”), we find a new linearization with fewer variables. The resulting model is called “Miniaturized” linearization. Based on this approach, we propose a new linearization scheme for which numerical tests have been performed.     

Convex programming with single separable constraint and bounded variables

In this paper a minimization problem with convex objective function subject to a separable convex inequality constraint “≤” and bounded variables (box constraints) is considered. We propose an iterative algorithm for solving this problem based on line search and convergence of this algorithm is proved. At each iteration, a separable convex programming problem with the same constraint set is solved using Karush-Kuhn-Tucker conditions. Convex minimization problems subject to linear equality/ linear inequality “≥” constraint and bounds on the variables are also considered. Numerical illustration is included in support of theory.     

Hamilton cycles in highly connected and expanding graphs

In this paper we prove a sufficient condition for the existence of a Hamilton cycle, which is applicable to a wide variety of graphs, including relatively sparse graphs. In contrast to previous criteria, ours is based on two properties only: one requiring expansion of “small” sets, the other ensuring the existence of an edge between any two disjoint “large” sets. We also discuss applications in positional games, random graphs and extremal graph theory.     

Conditional lexicographic orders in constraint satisfaction problems

The lexicographically-ordered CSP (“lexicographic CSP” or “LO-CSP” for short) combines a simple representation of preferences with the feasibility constraints of ordinary CSPs. Preferences are defined by a total ordering across all assignments, such that a change in assignment to a given variable is more important than any change in assignment to any less important variable. In this paper, we show how this representation can be extended to handle conditional preferences in two ways. In the first, for each conditional preference relation, the parents have higher priority than the children in the original lexicographic ordering. In the second, the relation between parents and children need not correspond to the importance ordering of variables. In this case, by obviating the “overwhelming advantage” effect with respect to the original variables and values, the representational capacity is significantly enhanced. For problems of the first type, any of the algorithms originally devised for ordinary LO-CSPs can also be used when some of the domain orderings are dependent on assignments to “parent” variables. For problems of the second type, algorithms based on lexical orders can be used if the representation is augmented by variables and constraints that link preference orders to assignments. In addition, the branch-and-bound algorithm originally devised for ordinary LO-CSPs can be extended to handle CSPs with conditional domain orderings.     

On the nonresonance property of linear differential-algebraic systems

We consider a system of linear ordinary differential equations in which the coefficient matrix multiplying the derivative of the unknown vector function is identically singular. For systems with constant and variable coefficients, we obtain nonresonance criteria (criteria for bounded-input bounded-output stability). For single-input control systems, we consider the problem of synthesizing a nonresonant system in the stationary and nonstationary cases. An arbitrarily high unsolvability index is admitted. The analysis is carried out under assumptions providing the existence of a so-called “equivalent form” with separated “algebraic” and “differential” components.     

Approximation Schemes for Functional Optimization Problems

Approximation schemes for functional optimization problems with admissible solutions dependent on a large number d of variables are investigated. Suboptimal solutions are considered, expressed as linear combinations of n-tuples from a basis set of simple computational units with adjustable parameters. Different choices of basis sets are compared, which allow one to obtain suboptimal solutions using a number n of basis functions that does not grow “fast” with the number d of variables in the admissible decision functions for a fixed desired accuracy. In these cases, one mitigates the “curse of dimensionality,” which often makes unfeasible traditional linear approximation techniques for functional optimization problems, when admissible solutions depend on a large number d of variables. Marcello Sanguineti was partially supported by a PRIN grant from the Italian Ministry for University and Research (project “Models and Algorithms for Robust Network Optimization”).     

A fuzzy closeness approach to fuzzy multi-attribute decision making

The aim of this paper is to develop a new fuzzy closeness (FC) methodology for multi-attribute decision making (MADM) in fuzzy environments, which is an important research field in decision science and operations research. The TOPSIS method based on an aggregating function representing “closeness to the ideal solution” is one of the well-known MADM methods. However, while the highest ranked alternative by the TOPSIS method is the best in terms of its ranking index, this does not mean that it is always the closest to the ideal solution. Furthermore, the TOPSIS method presumes crisp data while fuzziness is inherent in decision data and decision making processes, so that fuzzy ratings using linguistic variables are better suited for assessing decision alternatives. In this paper, a new FC method for MADM under fuzzy environments is developed by introducing a multi-attribute ranking index based on the particular measure of closeness to the ideal solution, which is developed from the fuzzy weighted Minkowski distance used as an aggregating function in a compromise programming method. The FC method of compromise ranking determines a compromise solution, providing a maximum “group utility” for the “majority” and a minimum individual regret for the “opponent”. A real example of a personnel selection problem is examined to demonstrate the implementation process of the method proposed in this paper.     

Towards a new theory of confirmation

Any sequence of events can be “explained” by any of an infinite number of hypotheses. Popper describes the “logic of discovery” as a process of choosing from a hierarchy of hypotheses the first hypothesis which is not at variance with the observed facts. Blum and Blum formalized these hierarchies of hypotheses as hierarchies of infinite binary sequences and imposed on them certain decidability conditions. In this paper we also consider hierarchies of infinite binary sequences but we impose only the most elementary Bayesian considerations. We use the structure of such hierarchies to define “confirmation”. We then suggest a definition of probability based on the amount of confirmation a particular hypothesis (i.e. pattern) has received. We show that hypothesis confirmation alone is a sound basis for determining probabilities and in particular that Carnap’s logical and empirical criteria for determining probabilities are consequences of the confirmation criterion in appropriate limiting cases.     

Unclad emperors: A case of mistaken identity

I am ready to rest my case. In summary, I will simply provide the two paragraphs of the conclusion of my “Trivial Mathematics” paper that Koblitz did not quote. In the social science literature, much reasoning takes place about magnitudes without any help from mathematical formalisms, but solely in terms of ordinary language. As the illustrations [in “Trivial Mathematics”] suggest, a good deal of this reasoning makes implicit use of the properties of ordinal variables and monotonic transformations. In both the social science and natural science literatures, much reasoning is also done from diagrams, without concern for the exact forms of the functions depicted or the cardinal values of variables. This reasoning appears also to make use of only the ordinal properties of the magnitudes depicted in the diagrams. One can argue that a great deal of everyday “commonsense” reasoning, when it is concerned with magnitudes, is, implicitly, reasoning about ordinal relations.     

Statistical hydrodynamics of magnetic fluids. I. the nonequilibrium statistical operator method

The Zubarev nonequilibrium statistical operator is used to describe the generalized hydrodynamic state of a magnetic fluid in an external magnetic field. The magnetic fluid is modeled with “liquid-state” and “magnetic” subsystems described using the classical and quantum statistics methods respectively. Equations of the generalized statistical hydrodynamics for a magnetic fluid in a nonhomogeneous external magnetic field with the Heisenberg spin interaction are derived for “liquid-state” and “magnetic” subsystems characterized by different nonequilibrium temperatures. These equations can be used to describe both the weakly and strongly nonequilibrium states. Some limiting cases are analyzed in which the variables of one of the subsystems can be formally neglected. Translated from Teoreticheskaya i Matematicheskaya Fizika. Vol. 115, No. 1, pp. 132–153, April, 1998.     

Suitable-portfolio investors,nondominated frontier sensitivity,and the effect of multiple objectives on standard portfolio selection

In standard portfolio theory, an investor is typically taken as having one stochastic objective, to maximize the random variable of portfolio return. But in this paper, we focus on investors whose purpose is to build, more broadly, a “suitable portfolio” taking additional concerns into account. Such investors would have additional stochastic and deterministic objectives that might include liquidity, dividends, number of securities in a portfolio, social responsibility, and so forth. To accommodate such investors, we develop a multiple criteria portfolio selection formulation, corroborate its appropriateness by examining the sensitivity of the nondominated frontier to various factors, and observe the conversion of the nondominated frontier to a nondominated surface. Furthermore, multiple criteria enable us to provide an explanation as to why the “market portfolio,” so often found deep below the nondominated frontier, is roughly where one would expect it to be with multiple criteria. After commenting on solvability issues, the paper concludes with the idea that what is the “modern portfolio theory” of today might well be interpreted as a projection onto two-space of a real multiple criteria portfolio selection problem from higher dimensional space. M. Hirschberger: Research conducted while a Visiting Scholar at the Department of Banking and Finance, Terry College of Business, University of Georgia, October 2003–March 2004.     

A multiclass network with non-linear, non-convex, non-monotonic stability conditions

We consider a stochastic queueing network with fixed routes and class priorities. The vector of class sizes forms a homogeneous Markov process of countable state space Z⁶ ₊. The network is said “stable” (resp.“unstable”) if this Markov process is ergodic (resp. transient). The parameters are the traffic intensities of the different classes. An unusual condition of stability is obtained thanks to a new argument based on the characterization of the “essential states”. The exact stability conditions are then detected thanks to an associated fluid network: we identify a zone of the parameter space in which diverging, fluid paths appear. In order to show that this is a zone of instability (and that the network is stable outside this zone), we resort to the criteria of ergodicity and transience proved by Malyshev and Menshikov for reflected random walks in Z⁶ ₊ (Malyshev and Menshikov, 1981). Their approach allows us to neglect some “pathological” fluid paths that perturb the dynamics of the fluid model. The stability conditions thus determined have especially unusual characteristics: they have a quadratic part, the stability domain is not convex, and increasing all the service rates may provoke instability (Theorem 1.1 and section 7). This revised version was published online in June 2006 with corrections to the Cover Date.     

Integrated fuzzy AHP and fuzzy VIKOR model for supplier selection in an agile and modular virtual enterprise

In this ever-changing world, organizations need to outsource parts of their processes for having agile response to market’s needs and varying demands. Because of temporal nature of virtual enterprises (VE’s), the situation of outsourcing process in this kind of organizations is a vital situation. The main idea of this paper aims to present a decision-making framework for specific area that is appropriated for complex states. Its contribution is developing a fuzzy VlseKriterijumska Optimizacija I Kompromisno Resenje (VIKOR) method and combining it with fuzzy analytic hierarchy process (AHP). This extension suitable for decision-making situations which is faced with mixture appraisement that simultaneously regarded to both “group utility” or majority and “individual regret” of the opponent. The Integrated and developed model suits to inconsistent conditions that we face to collection of criteria and subcriteria that should satisfy some of them collectively and simultaneously and in other attainment of some individual criteria is desirable. This framework then extended to a case study with varied criteria for outsourcing process.     

Hyperbolic balance laws: Riemann invariants and the generalized Riemann problem

The Generalized Riemann Problem (GRP) for a nonlinear hyperbolic system of m balance laws (or alternatively “quasi-conservative” laws) in one space dimension is now well-known and can be formulated as follows: Given initial-data which are analytic on two sides of a discontinuity, determine the time evolution of the solution at the discontinuity. In particular, the GRP numerical scheme (second-order high resolution) is based on an analytical evaluation of the first time derivative. It turns out that this derivative depends only on the first-order spatial derivatives, hence the initial data can be taken as piecewise linear. The analytical solution is readily obtained for a single equation (m = 1) and, more generally, if the system is endowed with a complete (coordinate) set of Riemann invariants. In this case it can be “diagonalized” and reduced to the scalar case. However, most systems with m > 2 do not admit such a set of Riemann invariants. This paper introduces a generalization of this concept: weakly coupled systems (WCS). Such systems have only “partial set” of Riemann invariants, but these sets are weakly coupled in a way which enables a “diagonalized” treatment of the GRP. An important example of a WCS is the Euler system of compressible, nonisentropic fluid flow (m = 3). The solution of the GRP discussed here is based on a careful analysis of rarefaction waves. A “propagation of singularities” argument is applied to appropriate Riemann invariants across the rarefaction fan. It serves to “rotate” initial spatial slopes into “time derivative”. In particular, the case of a “sonic point” is incorporated easily into the general treatment. A GRP scheme based on this solution is derived, and several numerical examples are presented. Special attention is given to the “acoustic approximation” of the analytical solution. It can be viewed as a proper linearization (different from the approach of Roe) of the nonlinear system. The resulting numerical scheme is the simplest (second-order, high-resolution) generalization of the Godunov scheme.     

Ols parameter estimation for a linear paired confluent model

We investigate OLS parameter estimation for a linear paired model in the case of a passive experiment with errors in both variables. The explicit form of the OLS estimates is obtained, their equivalence to maximum likelihood estimates is demonstrated in the presence of normal errors, and estimate consistency is proved. The OLS estimates are compared analytically and numerically with known parameter estimates of “direct,” “orthogonal,” and “diagonal” regression models.     

Weakly Gibbsian representations for joint measures of quenched lattice spin models

Can the joint measures of quenched disordered lattice spin models (with finite range) on the product of spin-space and disorder-space be represented as (suitably generalized) Gibbs measures of an “annealed system”? - We prove that there is always a potential (depending on both spin and disorder variables) that converges absolutely on a set of full measure w.r.t. the joint measure (“weak Gibbsianness”). This “positive” result is surprising when contrasted with the results of a previous paper [K6], where we investigated the measure of the set of discontinuity points of the conditional expectations (investigation of “a.s. Gibbsianness”). In particular we gave natural “negative” examples where this set is even of measure one (including the random field Ising model). Further we discuss conditions giving the convergence of vacuum potentials and conditions for the decay of the joint potential in terms of the decay of the disorder average over certain quenched correlations. We apply them to various examples. From this one typically expects the existence of a potential that decays superpolynomially outside a set of measure zero. Our proof uses a martingale argument that allows to cut (an infinite-volume analogue of) the quenched free energy into local pieces, along with generalizations of Kozlov's constructions. Received: 11 November 1999 / Revised version: 18 April 2000 / Published online: 22 November 2000 RID="*" ID="*" Work supported by the DFG Schwerpunkt `Wechselwirkende stochastische Systeme hoher Komplexit?t'     

A matrix solution of the pentagon equation with anticommuting variables

We construct a solution of the pentagon equation with anticommuting variables on two-dimensional faces of tetrahedra. In this solution, matrix coordinates are assigned to tetrahedron vertices. Because matrix multiplication is noncommutative, this provides a “more quantum” topological field theory than in our previous works.     

About an Optimal Visiting Problem

In this paper we are concerned with the optimal control problem consisting in minimizing the time for reaching (visiting) a fixed number of target sets, in particular more than one target. Such a problem is of course reminiscent of the famous “Traveling Salesman Problem” and brings all its computational difficulties. Our aim is to apply the dynamic programming technique in order to characterize the value function of the problem as the unique viscosity solution of a suitable Hamilton–Jacobi equation. We introduce some “external” variables, one per target, which keep in memory whether the corresponding target is already visited or not, and we transform the visiting problem in a suitable Mayer problem. This fact allows us to overcome the lacking of the Dynamic Programming Principle for the originary problem. The external variables evolve with a hysteresis law and the Hamilton–Jacobi equation turns out to be discontinuous