Extremal values of global tolerances in combinatorial optimization with an additive objective function

The currently adopted notion of a tolerance in combinatorial optimization is defined referring to an arbitrarily chosen optimal solution, i.e., locally. In this paper we introduce global tolerances with respect to the set of all optimal solutions, and show that the assumption of nonembededdness of the set of feasible solutions in the provided relations between the extremal values of upper and lower global tolerances can be relaxed. The equality between globally and locally defined tolerances provides a new criterion for the multiplicity (uniqueness) of the set of optimal solutions to the problem under consideration.     

Theoretical analysis of discrete contact problems with Coulomb friction

A discrete model of the two-dimensional Signorini problem with Coulomb friction and a coefficient of friction F depending on the spatial variable is analysed. It is shown that a solution exists for any F and is globally unique if F is sufficiently small. The Lipschitz continuity of this unique solution as a function of F as well as a function of the load vector f is obtained. Furthermore, local uniqueness of solutions for arbitrary F > 0 is studied. The question of existence of locally Lipschitz-continuous branches of solutions with respect to the coefficient F is converted to the question of existence of locally Lipschitz-continuous branches of solutions with respect to the load vector f. A condition guaranteeing the existence of locally Lipschitz-continuous branches of solutions in the latter case and results for determining their directional derivatives are given. Finally, the general approach is illustrated on an elementary example, whose solutions are calculated exactly.     

An interactive method as an aid in solving multi-objective mathematical programming problems

In this paper, an interactive method is presented as an aid in solving multi-objective programming problems. It is assumed that the m objective functions are real-valued functions of the decision variables which are themselves constrained to some compact and nonempty set. The overall utility function is assumed to be unknown explicitly to the decision-maker but is assumed to be a real-valued, unimodal function defined on the m-tuples of feasible values of the objective functions and monotone nondecreasing in each argument. The decision-maker is required only to provide yes or no answers to questions regarding the desirability of increase or decrease in objective function values of solutions that he will not accept as optimal. Convergence of the method is indicated and a numerical example is presented in order to demonstrate its applicability.     

The Choquet integral representability of comonotonically additive functionals in locally compact spaces

We give an alternative and direct approach to the Choquet integral representability of a comonotonically additive, bounded, monotone functional I defined on the space of all continuous, real-valued functions on a locally compact space X with compact support and on the space of all continuous, real-valued functions on X vanishing at infinity. To this end, we introduce the notion of the asymptotic translatability of the functional I and show that this simple notion is equivalent to the Choquet integral representability of I with respect to a monotone measure on X with appropriate regularity.     

On the adjustment problem for linear programs

We propose a generalization of the inverse problem which we will call the adjustment problem. For an optimization problem with linear objective function and its restriction defined by a given subset of feasible solutions, the adjustment problem consists in finding the least costly perturbations of the original objective function coefficients, which guarantee that an optimal solution of the perturbed problem is also feasible for the considered restriction. We describe a method of solving the adjustment problem for continuous linear programming problems when variables in the restriction are required to be binary.     

Parameterisation algorithms for the integer linear programs in binary variables

In this paper we consider the integer programmiing problem: minimize z(x) = c · x subject to Ax?b,x binary.Roodman appended the objective function z(x) to the body of the constraints and presented a modified version of the Balas additive algorithm by which each fathomed partial solution is attributed to the constraint which caused the fathoming. Exploiting this information, he conducted (a) ranging analysis, i.e. calculating bounds on the values of the parameters which leave the original optimal solution unchanged, and (b) parameter change analysis, i.e. determining new optimal solutions (if any) for revised values of the parameters outside the ranging bounds.We extend Roodman's results and construct parametric functions of the following form. Let Σ be any parameter of c or b or A, and replace Σ by Σ(λ) = Σ + λ. Then, holding every other parameter of the program fixed, and varying λ in the set of real numbers we construct the parametric function $\text{z}{}^1\text{(Σ(λ))}$ which matches non-overlapping intervals of λ with optimal solutions. This replaces by exact bounds in the linear programming sense, the bounds underestimated by Roodman's ranging analysis. It also determines optimal solutions for any values of λ, rather than for a revised set of values. Finally some results of computational experience are presented.     

Dirichlet problem on locally finite graphs

In this paper, we study the existence and uniqueness of solutions to the vertex-weighted Dirichlet problem on locally finite graphs. Let B be a subset of the vertices of a graph G. The Dirichlet problem is to find a function whose discrete Laplacian on G?B and its values on B are given. Each infinite connected component of G?B is called an end of G relative to B. If there are no ends, then there is a unique solution to the Dirichlet problem. Such a solution can be obtained as a limit of an averaging process or as a minimizer of a certain functional or as a limit-solution of the heat equation on the graph. On the other hand, we show that if G is a locally finite graph with l ends, then the set of solutions of any Dirichlet problem, if non-empty, is at least l-dimensional.     

Momentum estimates and ergodicity for the 3D stochastic cubic Ginzburg-Landau equation with degenerate noise

In this paper, we consider the ergodicity of invariant measures for the stochastic Ginzburg-Landau equation with degenerate random forcing. First, we show the existence and pathwise uniqueness of strong solutions with H¹-initial data, and then the existence of an invariant measure for the Feller semigroup by the Krylov-Bogoliubov method. Then in the case of degenerate additive noise, using the notion of asymptotically strong Feller property, we prove the uniqueness of invariant measures for the transition semigroup.     

Stability of capture into parametric autoresonance

We consider nonlinear elliptic second-order variational inequalities with degenerate (with respect to the spatial variable) and anisotropic coefficients and L ¹-data. We study the cases where the set of constraints belongs to a certain anisotropic weighted Sobolev space and to a larger function class. In the first case, some new properties of T-solutions and shift T-solutions of the investigated variational inequalities are established. Moreover, the notion of W ^1,1-regular T-solution is introduced, and a theorem of existence and uniqueness of such a solution is proved. In the second case, we introduce the notion of T-solution of the variational inequalities under consideration and establish conditions of existence and uniqueness of such a solution.     

Balancing of simple assembly lines under variations of task processing times

One of the simple assembly line balancing problems (SALBPs), known as SALBP-E, is considered. It consists in assigning a given set V={1,2,??,n} of elementary tasks to linearly ordered workstations with respect to precedence and capacity restrictions while minimizing the following product: number of used workstations × working time on the most loaded one. The stability of feasible and optimal solutions for this problem with regard to possible variations of the processing time of certain tasks is investigated. Two heuristic procedures finding a compromise between the efficiency and the considered stability measure of studied solutions are suggested and evaluated on known benchmarks.     

Maximal and supremal tolerances in multiobjective linear programming

Let a multiobjective linear programming problem and any efficient solution be given. Tolerance analysis aims to compute interval tolerances for (possibly all) objective function coefficients such that the efficient solution remains efficient for any perturbation of the coefficients within the computed intervals. The known methods either yield tolerances that are not the maximal possible ones, or they consider perturbations of weights of the weighted sum scalarization only. We focus directly on perturbations of the objective function coefficients, which makes the approach independent on a scalarization technique used. In this paper, we propose a method for calculating the supremal tolerance (the maximal one need not exist). The main disadvantage of the method is the exponential running time in the worst case. Nevertheless, we show that the problem of determining the maximal/supremal tolerance is NP-hard, so an efficient (polynomial time) procedure is not likely to exist. We illustrate our approach on examples and present an application in transportation problems. Since the maximal tolerance may be small, we extend the notion to individual lower and upper tolerances for each objective function coefficient. An algorithm for computing maximal individual tolerances is proposed.     

On accuracy,robustness and tolerances in vector Boolean optimization

A Boolean programming problem with a finite number of alternatives where initial coefficients (costs) of linear payoff functions are subject to perturbations is considered. We define robust solution as a feasible solution which for a given set of realizations of uncertain parameters guarantees the minimum value of the worst-case relative regret among all feasible solutions. For the Pareto optimality principle, an appropriate definition of the worst-case relative regret is specified. It is shown that this definition is closely related to the concept of accuracy function being recently intensively studied in the literature. We also present the concept of robustness tolerances of a single cost vector. The tolerance is defined as the maximum level of perturbation of the cost vector which does not destroy the solution robustness. We present formulae allowing the calculation of the robustness tolerance obtained for some initial costs. The results are illustrated with several numerical examples.     

On uniqueness of fractional powers of multi-valued linear operators and the incomplete Cauchy problem

We obtain uniqueness of additive families {A _t } _t>0 of fractional powers of a multi-valued sectorial linear operator A ?? A ₁ in a Banach space, satisfying a certain kind of continuity with respect to the exponent and a spectral property, from uniqueness of the solutions of the second-order incomplete Cauchy problem associated with A. We show the close relationship between the multiplicativity and the uniqueness of fractional powers.     

On nonatomicity for non-additive functions

The notion of nonatomicity for set functions plays a key role in classical measure theory and its applications. For classical measures taking values in finite dimensional Banach spaces, it guarantees the connectedness of range. Even just replacing σ-additivity with finite additivity for measures requires some stronger nonatomicity property for the same conclusion to hold. In the present paper, we deal with non-additive functions – called ‘s-outer’ and ‘quasi-triangular’ – defined on rings and taking values in Hausdorff topological spaces. No algebraic structure is required on their target spaces. In this context, we make use of a notion of strong nonatomicity involving just the behavior of functions on ultrafilters of their underlying Boolean domains. This notion is proved to be equivalent to that proposed in earlier contributions concerning Lyapunov-types theorems in additive and non-additive frameworks. Thus, in particular, our analysis allows to generalize, improve and unify several known results on this topic.     

Quantitative stability of full random two-stage stochastic programs with recourse

In this paper, we consider quantitative stability analysis for two-stage stochastic linear programs when recourse costs, the technology matrix, the recourse matrix and the right-hand side vector are all random. For this purpose, we first investigate continuity properties of parametric linear programs. After deriving an explicit expression for the upper bound of its feasible solutions, we establish locally Lipschitz continuity of the feasible solution sets of parametric linear programs. These results are then applied to prove continuity of the generalized objective function derived from the full random second-stage recourse problem, from which we derive new forms of quantitative stability results of the optimal value function and the optimal solution set with respect to the Fortet–Mourier probability metric. The obtained results are finally applied to establish asymptotic behavior of an empirical approximation algorithm for full random two-stage stochastic programs.     

Interactive Polyhedral Outer Approximation (IPOA) strategy for general multiobjective optimization problems

We propose an interactive polyhedral outer approximation (IPOA) method to solve a broad class of multiobjective optimization problems (MOP) with, possibly, nonlinear and nondifferentiable objective and constraint functions, and with continuous or discrete decision variables. During the interactive optimization phase, the method progressively constructs a polyhedral approximation of the decision-maker’s (DM’s) unknown preference structure and a polyhedral outer-approximation of the feasible set of MOP. The piecewise linear approximation of the DM’s preferences also provides a mechanism for testing the consistency of the DM’s assessments and removing inconsistencies; it also allows post-optimality analysis. All the feasible trial solutions are non-dominated (efficient, or Pareto-optimal) so preference assessments are made in the context of non-dominated alternatives only. Upper and lower bounds on the yet unknown optimal value are produced at every iteration, allowing terminating the search prematurely at a good-enough solution and providing information about the closeness of this solution to the optimal solution. The IPOA method includes a preliminary phase in which a limited probe of the efficient set is conducted in order to find a good initial trial solution for the interactive phase. The computational requirements of the algorithm are relatively simple. The results of an extensive computational study are reported.     

Two-Sided Pareto Front Approximations

A new approach to derive Pareto front approximations with evolutionary computations is proposed here. At present, evolutionary multiobjective optimization algorithms derive a discrete approximation of the Pareto front (the set of objective maps of efficient solutions) by selecting feasible solutions such that their objective maps are close to the Pareto front. However, accuracy of such approximations is known only if the Pareto front is known, which makes their usefulness questionable. Here we propose to exploit also elements outside feasible sets to derive pairs of such Pareto front approximations that for each approximation pair the corresponding Pareto front lies, in a certain sense, in-between. Accuracies of Pareto front approximations by such pairs can be measured and controlled with respect to distance between elements of a pair. A rudimentary algorithm to derive pairs of Pareto front approximations is presented and the viability of the idea is verified on a limited number of test problems.     

Existence and uniqueness of martingale solutions for SDEs with rough or degenerate coefficients

In this paper we extend recent results on the existence and uniqueness of solutions of ODEs with non-smooth vector fields to the case of martingale solutions, in the Stroock-Varadhan sense, of SDEs with non-smooth coefficients. In the first part we develop a general theory, which roughly speaking allows to deduce existence, uniqueness and stability of martingale solutions for Ld-almost every initial condition x whenever existence and uniqueness is known at the PDE level in the L^∞-setting (and, conversely, if existence and uniqueness of martingale solutions is known for Ld-a.e. initial condition, then existence and uniqueness for the PDE holds). In the second part of the paper we consider situations where, on the one hand, no pointwise uniqueness result for the martingale problem is known and, on the other hand, well-posedness for the Fokker-Planck equation can be proved. Thus, the theory developed in the first part of the paper is applicable. In particular, we will study the Fokker-Planck equation in two somehow extreme situations: in the first one, assuming uniform ellipticity of the diffusion coefficients and Lipschitz regularity in time, we are able to prove existence and uniqueness in the L²-setting; in the second one we consider an additive noise and, assuming the drift b to have BV regularity and allowing the diffusion matrix a to be degenerate (also identically 0), we prove existence and uniqueness in the L^∞-setting. Therefore, in these two situations, our theory yields existence, uniqueness and stability results for martingale solutions.     

Multi-Objective Interactive Programming

This paper proposes a method for finding optimal, or near optimal, solutions for problems involving m objective functions, where there is an overall criterion which is a weighted sum of the m objective functions, but where the weights are, initially, unknown. The process is an interactive one, beginning with a set within which the actual weighting vector is known to lie, and progressively cutting down the size of the set until an acceptable solution is found. A by-product of the procedure is an iterative method for finding the generators of the polyhedral cones, within which the weighting vector must lie, at each stage.