共查询到20条相似文献,搜索用时 562 毫秒
1.
E. O. Stepanov 《Journal of Mathematical Sciences》2006,132(4):522-552
We consider a continuous optimization model of a one-dimensional connected transportation network under the assumption that
the cost of transportation with the use of network is negligible in comparison with the cost of transportation without it.
We investigate the connections between this problem and its important special case, the minimization of the average distance
functional. For the average distance minimization problem we formulate a number of conditions for the partial geometric regularity
of a solution in ℝn with an arbitrary dimension n ⩾ 2. The corresponding results are applied to solutions to the general optimization problem.
Bibliography: 26 titles. Illustrations: 1 Figure.
__________
Translated from Problemy Matematicheskogo Analiza, No. 31, 2005, pp. 129–157. 相似文献
2.
We address an important issue in knowledge discovery using neural networks that has been left out in a recent article “Knowledge discovery using a neural network simultaneous optimization algorithm on a real world classification problem” by Sexton et al. [R.S. Sexton, S. McMurtrey, D.J. Cleavenger, Knowledge discovery using a neural network simultaneous optimization algorithm on a real world classification problem, European Journal of Operational Research 168 (2006) 1009–1018]. This important issue is the generation of comprehensible rule sets from trained neural networks. In this note, we present our neural network rule extraction algorithm that is very effective in discovering knowledge embedded in a neural network. This algorithm is particularly appropriate in applications where comprehensibility as well as accuracy are required. For the same data sets used by Sexton et al. our algorithm produces accurate rule sets that are concise and comprehensible, and hence helps validate the claim that neural networks could be viable alternatives to other data mining tools for knowledge discovery. 相似文献
3.
We discuss how a new pricing scheme can be integrated within a communication network. The pricing scheme is based on the availability
of end-to-end communications, and is an alternative to congestion pricing, which is not applicable when communication capacity
is higher than demand (as happens in most communication backbone networks). We also investigate how, based on this scheme,
an optimization algorithm for updating the network topology can be applied. The network update problem is modeled as a combinatorial
optimization problem, which is approximately solved using a Genetic Algorithm. The good results obtained in a case study show
that the method is robust and can be applied even when end-to-end availability measures can only be computed approximately
(in this case, using a Monte Carlo method).
This research is part of the PAIR associated research project, supported by the INRIA, France, and has also received the support
of ECOS-Sud, under Action U03E02. The participation of Pablo Rodríguez was supported by the French Embassy in Uruguay as part
of the French Ministère des Affaires étrangères scientific cooperation program; and by the “Programa de Jóvenes Investigadores”
of CSIC, UDELAR, Uruguay. 相似文献
4.
M. M. Ali 《Journal of Global Optimization》2006,35(1):27-52
In a competitive market investors in a data network need to give utmost considerations on profitability. They must have clear
picture of the size, growth rate and demand for different services. However, the investors’ budget may be limited, and therefore
the speed at which the network is rolled out, must be carefully planned to ensure that they can meet profitability targets.
We model first the roll out order as combinatorial optimization problems and then extend them as continuous optimization problems.
We then implement these models in a practical problem. Numerical studies suggested that the optimization problems have multiple
local minima. Therefore, a global optimization technique is used to obtain the global minimum for the continuous variable
problem and a combinatorial optimization technique is used to solve the discrete variable problem. Optimal financial indicators
are obtained to assess the commercial viability of the network. Finally, we demonstrate that the solution of these optimization
problems can provide an investment policy to the investors in data networks.
*This network is a combined telephone and data network such as VIP (Voice over Internet Protocol).
M. M. Ali: Visitor at the Institute for Mathematics and its Applications, University of Minnesota, USA. 相似文献
5.
Stefano Benati 《Computational Management Science》2006,3(4):271-284
Project networks – or PERT networks – can be characterized by random completion times of activities and positive or negative cash flows throughout the project. In these cases the decision maker’s problem consists of determining a feasible activities schedule, to maximize the project financial value, where the financial value is measured by the net present value (npv) of cash flows.The analysis of these networks is a difficult computational task for the following reason. First, suppose that a schedule is fixed using a heuristic rule. Then the expected npv is calculated. But, due to stochastic job completion times, this problem belongs to the ♯-P complete difficulty class, e.g. problems that involve finding all the Hamiltonian cycles in a network. The problem is such that evaluating one project alone is not sufficient, but the optimal one has to be selected. This involves a further increase in computational time.This paper proposes a stochastic optimization model to determine a heuristic scheduling rule, that provides an approximate solution to finding the optimal project npv. A feature of this approach is that the scheduling rule is completely deterministic and defined when the project begins. Therefore an upper bound of the expected npv, that is an optimistic estimate, can be calculated through linear programming and a lower bound, that is a pessimistic estimate, can be calculated using simulation before the project begins. 相似文献
6.
This study concerns the equilibrium behavior of a general class of Markov network processes that includes a variety of queueing
networks and networks with interacting components or populations. The focus is on determining when these processes have product
form stationary distributions. The approach is to relate the marginal distributions of the process to the stationary distributions
of “node transition functions” that represent the nodes in isolation operating under certain fictitious environments. The
main result gives necessary and sufficient conditions on the node transition functions for the network process to have a product
form stationary distribution. This result yields a procedure for checking for a product form distribution and obtaining such
a distribution when it exits. An important subclass of networks are those in which the node transition rates have Poisson
arrival components. In this setting, we show that the network process has a product form distribution and is “biased locally
balanced” if and only if the network is “quasi-reversible” and certain traffic equations are satisfied. Another subclass of
networks are those with reversible routing. We weaken the known sufficient condition for such networks to be product form.
We also discuss modeling issues related to queueing networks including time reversals and reversals of the roles of arrivals
and departures. The study ends by describing how the results extend to networks with multi-class transitions.
This revised version was published online in June 2006 with corrections to the Cover Date. 相似文献
7.
Gauss—Seidel type relaxation techniques are applied in the context of strictly convex pure networks with separable cost functions.
The algorithm is an extension of the Bertsekas—Tseng approach for solving the linear network problem and its dual as a pair
of monotropic programming problems. The method is extended to cover the class of generalized network problems. Alternative
internal tactics for the dual problem are examined. Computational experiments —aimed at the improved efficiency of the algorithm
— are presented.
This research was supported in part by National Science Foundation Grant No. DCR-8401098-A0l. 相似文献
8.
Alexander L. Stolyar 《Queueing Systems》2006,54(3):203-220
In Stolyar (Queueing Systems 50 (2005) 401–457) a dynamic control strategy, called greedy primal-dual (GPD) algorithm, was
introduced for the problem of maximizing queueing network utility subject to stability of the queues, and was proved to be
(asymptotically) optimal. (The network utility is a concave function of the average rates at which the network generates several
“commodities.”) Underlying the control problem of Stolyar (Queueing Systems 50 (2005) 401–457) is a convex optimization problem
subject to a set of linear constraints.
In this paper we introduce a generalized GPD algorithm, which applies to the network control problem with additional convex (possibly non-linear) constraints on the average commodity rates. The underlying optimization problem in this case is a convex
problem subject to convex constraints. We prove asymptotic optimality of the generalized GPD algorithm. We illustrate key
features and applications of the algorithm on simple examples.
AMS Subject Classifications: 90B15 · 90C25 · 60K25 · 68M12 相似文献
9.
The paper introduces a new approach to analyze the stability of neural network models without using any Lyapunov function. With the new approach, we investigate the stability properties of the general gradient-based neural network model for optimization problems. Our discussion includes both isolated equilibrium points and connected equilibrium sets which could be unbounded. For a general optimization problem, if the objective function is bounded below and its gradient is Lipschitz continuous, we prove that (a) any trajectory of the gradient-based neural network converges to an equilibrium point, and (b) the Lyapunov stability is equivalent to the asymptotical stability in the gradient-based neural networks. For a convex optimization problem, under the same assumptions, we show that any trajectory of gradient-based neural networks will converge to an asymptotically stable equilibrium point of the neural networks. For a general nonlinear objective function, we propose a refined gradient-based neural network, whose trajectory with any arbitrary initial point will converge to an equilibrium point, which satisfies the second order necessary optimality conditions for optimization problems. Promising simulation results of a refined gradient-based neural network on some problems are also reported. 相似文献
10.
A brief historical introduction to Euler's formula for polyhedra,topology, graph theory and networks
Lokenath Debnath 《International Journal of Mathematical Education in Science & Technology》2013,44(6):769-785
This article is essentially devoted to a brief historical introduction to Euler's formula for polyhedra, topology, theory of graphs and networks with many examples from the real-world. Celebrated Königsberg seven-bridge problem and some of the basic properties of graphs and networks for some understanding of the macroscopic behaviour of real physical systems are included. We also mention some important and modern applications of graph theory or network problems from transportation to telecommunications. Graphs or networks are effectively used as powerful tools in industrial, electrical and civil engineering, communication networks in the planning of business and industry. Graph theory and combinatorics can be used to understand the changes that occur in many large and complex scientific, technical and medical systems. With the advent of fast large computers and the ubiquitous Internet consisting of a very large network of computers, large-scale complex optimization problems can be modelled in terms of graphs or networks and then solved by algorithms available in graph theory. Many large and more complex combinatorial problems dealing with the possible arrangements of situations of various kinds, and computing the number and properties of such arrangements can be formulated in terms of networks. The Knight's tour problem, Hamilton's tour problem, problem of magic squares, the Euler Graeco-Latin squares problem and their modern developments in the twentieth century are also included. 相似文献
11.
Many algorithms for linearly constrained optimization problems proceed by solving a sequence of subproblems. In these subproblems,
the number of variables is implicitly reduced by using the linear constraints to express certain ‘basic’ variables in terms
of other variables. Difficulties may arise, however, if degeneracy is present; that is, if one or more basic variables are
at lower or upper bounds. In this situation, arbitrarily small movements along a feasible search direction in the reduced
problem may result in infeasibilities for basic variables in the original problem. For such cases, the search direction is
typically discarded, a new reduced problem is formed and a new search direction is computed. Such a process may be extremely
costly, particularly in large-scale optimization where degeneracy is likely and good search directions can be expensive to
compute. This paper is concerned with a practical method for ensuring that directions that are computed in the reduced space
are actually feasible in the original problem. It is based on a generalization of the ‘maximal basis’ result first introduced
by Dembo and Klincewicz for large nonlinear network optimization problems.
Research supported in part by NSF Grant ECS-8119513 and DOT Research Grant CT-06-0011. 相似文献
12.
The complete topology design problem of survivable mesh-based transport networks is to address simultaneously design of network
topology, working path routing, and spare capacity allocation based on span-restoration. Each constituent problem in the complete
design problem could be formulated as an Integer Programming (IP) and is proved to be
NP\mathcal{NP}
-hard. Due to a large amount of decision variables and constraints involved in the IP formulation, to solve the problem directly
by exact algorithms (e.g. branch-and-bound) would be impractical if not impossible. In this paper, we present a two-level
evolutionary approach to address the complete topology design problem. In the low-level, two parameterized greedy heuristics
are developed to jointly construct feasible solutions (i.e., closed graph topologies satisfying all the mesh-based network
survivable constraints) of the complete problem. Unlike existing “zoom-in”-based heuristics in which subsets of the constraints
are considered, the proposed heuristics take all constraints into account. An estimation of distribution algorithm works on
the top of the heuristics to tune the control parameters. As a result, optimal solution to the considered problem is more
likely to be constructed from the heuristics with the optimal control parameters. The proposed algorithm is evaluated experimentally
in comparison with the latest heuristics based on the IP software CPLEX, and the “zoom-in”-based approach on 28 test networks
problems. The experimental results demonstrate that the proposed algorithm is more effective in finding high-quality topologies
than the IP-based heuristic algorithm in 21 out of 28 test instances with much less computational costs, and performs significantly
better than the “zoom-in”-based approach in 19 instances with the same computational costs. 相似文献
13.
Dorit S. Hochbaum 《Annals of Operations Research》2007,153(1):257-296
Nonlinear optimization algorithms are rarely discussed from a complexity point of view. Even the concept of solving nonlinear
problems on digital computers is not well defined. The focus here is on a complexity approach for designing and analyzing
algorithms for nonlinear optimization problems providing optimal solutions with prespecified accuracy in the solution space.
We delineate the complexity status of convex problems over network constraints, dual of flow constraints, dual of multi-commodity,
constraints defined by a submodular rank function (a generalized allocation problem), tree networks, diagonal dominant matrices,
and nonlinear knapsack problem’s constraint. All these problems, except for the latter in integers, have polynomial time algorithms
which may be viewed within a unifying framework of a proximity-scaling technique or a threshold technique. The complexity of many of these algorithms is furthermore best possible in that it matches lower bounds on the
complexity of the respective problems.
In general nonseparable optimization problems are shown to be considerably more difficult than separable problems. We compare
the complexity of continuous versus discrete nonlinear problems and list some major open problems in the area of nonlinear
optimization.
An earlier version of this paper appeared in 4OR, 3:3, 171–216, 2005. 相似文献
14.
M. V. Lomonosov 《Combinatorica》1983,3(2):207-218
We consider the two-commodity flow problem and give a good characterization of the optimum flow if the augmented network (with
both source-sink edges added) is planar. We show that max flow ≧ min cut −1, and describe the structure of those networks
for which equality holds. 相似文献
15.
The paper investigates model reduction techniques that are based on a nonlocal quasi-continuum-like approach. These techniques
reduce a large optimization problem to either a system of nonlinear equations or another optimization problem that are expressed
in a smaller number of degrees of freedom. The reduction is based on the observation that many of the components of the solution
of the original optimization problem are well approximated by certain interpolation operators with respect to a restricted
set of representative components. Under certain assumptions, the “optimize and interpolate” and the “interpolate and optimize”
approaches result in a regular nonlinear equation and an optimization problem whose solutions are close to the solution of
the original problem, respectively. The validity of these assumptions is investigated by using examples from potential-based
and electronic structure-based calculations in Materials Science models. A methodology is presented for using quasi-continuum-like
model reduction for real-space DFT computations in the absence of periodic boundary conditions. The methodology is illustrated
using a basic Thomas–Fermi–Dirac case study. 相似文献
16.
S. Raghavan Daliborka Stanojević 《Journal of Mathematical Modelling and Algorithms》2013,12(4):407-428
In this paper, we present an exact solution procedure for the design of two-layer wavelength division multiplexing (WDM) optical networks with wavelength changers and bifurcated flows. This design problem closely resembles the traditional multicommodity flow problem, except that in the case of WDM optical networks, we are concerned with the routing of multiple commodities in two network layers. Consequently, the corresponding optimization models have to deal with two types of multicommodity variables defined for each of the network layers. The proposed procedure represents one of the first branch-and-price algorithms for a general WDM optical network setting with no assumptions on the number of logical links that can be established between nodes in the network. We apply our procedure in a computational study with four different network configurations. Our results show that for the three tested network configurations our branch-and-price algorithm provides solutions that are on average less than 5 % from optimality. We also provide a comparison of our branch-and-price algorithm with two simple variants of the upper bounding heuristic procedure HLDA that is commonly used for WDM optical network design. 相似文献
17.
T. Antczak 《Journal of Optimization Theory and Applications》2007,132(1):71-87
In this paper, the η-approximation method introduced by Antczak (Ref. 1) for solving a nonlinear constrained mathematical
programming problem involving invex functions with respect to the same function η is extended. In this method, a so-called
η-approximated optimization problem associated with the original mathematical programming problems is constructed; moreover,
an η-saddle point and an η-Lagrange function are defined. By the help of the constructed η-approximated optimization problem,
saddle-point criteria are obtained for the original mathematical programming problem. The equivalence between an η-saddle
point of the η-Lagrangian of the associated η-approximated optimization problem and an optimal solution in the original mathematical
programming problem is established. 相似文献
18.
Implementation of scatter search for multi-objective optimization: a comparative study 总被引:2,自引:0,他引:2
Interest in the design of efficient meta-heuristics for the application to combinatorial optimization problems is growing
rapidly. The optimal design of water distribution networks is an important optimization problem which consists of finding
the best way of conveying water from the sources to the users, thus satisfying their requirements. The efficient design of
looped networks is a much more complex problem than the design of branched ones, but their greater reliability can compensate
for the increase in cost when closing some loops. Mathematically, this is a non-linear optimization problem, constrained to
a combinatorial space, since the diameters are discrete and it has a very large number of local solutions. Many works have
dealt with the minimization of the cost of the network but few have considered their cost and reliability simultaneously.
The aim of this paper is to evaluate the performance of an implementation of Scatter Search in a multi-objective formulation
of this problem. Results obtained in three benchmark networks show that the method here proposed performs accurately well
in comparison with other multi-objective approaches also implemented. 相似文献
19.
This paper presents a co-evolutionary particle swarm optimization (PSO) algorithm, hybridized with noising metaheuristics,
for solving the delay constrained least cost (DCLC) path problem, i.e., shortest-path problem with a delay constraint on the
total “cost” of the optimal path. The proposed algorithm uses the principle of Lagrange relaxation based aggregated cost.
It essentially consists of two concurrent PSOs for solving the resulting minimization-maximization problem. The main PSO is
designed as a hybrid PSO-noising metaheuristics algorithm for efficient global search to solve the minimization part of the
DCLC-Lagrangian relaxation by finding multiple shortest paths between a source-destination pair. The auxiliary/second PSO
is a co-evolutionary PSO to obtain the optimal Lagrangian multiplier for solving the maximization part of the Lagrangian relaxation
problem. For the main PSO, a novel heuristics-based path encoding/decoding scheme has been devised for representation of network
paths as particles. The simulation results on several networks with random topologies illustrate the efficiency of the proposed
hybrid algorithm for the constrained shortest path computation problems. 相似文献
20.
This paper concerns a system of nonlinear wave equations describing the vibrations of a 3-dimensional network of elastic strings.The authors derive the equations and appropriate nodal conditions,determine equilibrium solutions,and,by using the methods of quasilinear hyperbolic systems,prove that for tree networks the natural initial,boundary value problem has classical solutions existing in neighborhoods of the "stretched" equilibrium solutions.Then the local controllability of such networks near such equilibrium configurations in a certain specified time interval is proved.Finally,it is proved that,given two different equilibrium states satisfying certain conditions,it is possible to control the network from states in a small enough neighborhood of one equilibrium to any state in a suitable neighborhood of the second equilibrium over a suffciently large time interval. 相似文献