31 resultados para combinatorial optimisation

em Indian Institute of Science - Bangalore - Índia


Relevância:

20.00% 20.00%

Publicador:

Resumo:

The paper presents, in three parts, a new approach to improve the detection and tracking performance of a track-while-scan radar. Part 1 presents a review of the current status of the subject. Part 2 details the new approach. It shows how a priori information provided by the tracker can be used to improve detection. It also presents a new multitarget tracking algorithm. In the present Part, analytical derivations are presented for assessing, a priori, the performance of the TWS radar system. True track initiation, false track initiation, true track continuation and false track deletion characteristics have been studied. It indicates how the various thresholds can be chosen by the designer to optimise performance. Simulation results are also presented.

Relevância:

20.00% 20.00%

Publicador:

Resumo:

Experimental characterization of high dimensional dynamic systems sometimes uses the proper orthogonal decomposition (POD). If there are many measurement locations and relatively fewer sensors, then steady-state behavior can still be studied by sequentially taking several sets of simultaneous measurements. The number required of such sets of measurements can be minimized if we solve a combinatorial optimization problem. We aim to bring this problem to the attention of engineering audiences, summarize some known mathematical results about this problem, and present a heuristic (suboptimal) calculation that gives reasonable, if not stellar, results.

Relevância:

20.00% 20.00%

Publicador:

Resumo:

Business processes and application functionality are becoming available as internal web services inside enterprise boundaries as well as becoming available as commercial web services from enterprise solution vendors and web services marketplaces. Typically there are multiple web service providers offering services capable of fulfilling a particular functionality, although with different Quality of Service (QoS). Dynamic creation of business processes requires composing an appropriate set of web services that best suit the current need. This paper presents a novel combinatorial auction approach to QoS aware dynamic web services composition. Such an approach would enable not only stand-alone web services but also composite web services to be a part of a business process. The combinatorial auction leads to an integer programming formulation for the web services composition problem. An important feature of the model is the incorporation of service level agreements. We describe a software tool QWESC for QoS-aware web services composition based on the proposed approach.

Relevância:

20.00% 20.00%

Publicador:

Resumo:

In this paper, the design basis of the conventional Khadi and Village Industries Commission biogas plants has been elucidated. It has been shown that minimisation of the cost of the gas holder alone leads to the narrow and deep digesters of conventional plants. If instead, the total capital cost of the gas holder plus digester is minimised, the optimisation leads to wide and shallow digesters, which are less expensive. To test this alternative, two prototype plants have been designed, constructed and operated. These plants are not only 25–40% cheaper, but their performance is actually slightly better than the conventional plants.

Relevância:

20.00% 20.00%

Publicador:

Resumo:

A simplicial complex is said to satisfy complementarity if exactly one of each complementary pair of nonempty vertex-sets constitutes a face of the complex.

Relevância:

20.00% 20.00%

Publicador:

Resumo:

The aim of logic synthesis is to produce circuits which satisfy the given boolean function while meeting timing constraints and requiring the minimum silicon area. Logic synthesis involves two steps namely logic decomposition and technology mapping. Existing methods treat the two as separate operation. The traditional approach is to minimize the number of literals without considering the target technology during the decomposition phase. The decomposed expressions are then mapped on to the target technology to optimize the area, Timing optimization is carried out subsequently, A new approach which treats logic decomposition and technology maping as a single operation is presented. The logic decomposition is based on the parameters of the target technology. The area and timing optimization is carried out during logic decomposition phase itself. Results using MCNC circuits are presented to show that this method produces circuits which are 38% faster while requiring 14% increase in area.

Relevância:

20.00% 20.00%

Publicador:

Resumo:

The optimisation is reported on the design of unbalanced magnetron (UBM) sputtering cathodes. For the study, a planar circular cathode backed by a double-coil electromagnet (compatible for a 100 mm diameter target) was developed. The variation of the structure and strength of the magnetic field in front of the target was investigated for different current combinations in the electromagnetic coils, and its effect on the sputtering process was analysed. The observations on the magnetic field geometry revealed some interesting features, such as the balancing point of the fields along the axis (null-point), and the zero axial region over the target surface (B-z = 0 ring). The positions of both could be controlled by adjusting the ratio of the electric current in the coils. The magnetic field null-point could be used as a reference for the region of homogeneous film growth. The B-z = 0 ring was the location where the glow discharge concentrated (or where the maximum target erosion occurred). The diameter of the ring determined the area covered by the discharge and thus the sputtering efficiency. The optimum substrate position can be fixed according to the position of the null-point and optimisation of sputtering can be achieved by adjusting the diameter of the B-z = 0 ring. The results of this study should be helpful in the designing of an ideal UBM using permanent magnets as well as electromagnets. (C) 1999 Elsevier Science Ltd. All rights reserved.

Relevância:

20.00% 20.00%

Publicador:

Resumo:

Combinatorial exchanges are double sided marketplaces with multiple sellers and multiple buyers trading with the help of combinatorial bids. The allocation and other associated problems in such exchanges are known to be among the hardest to solve among all economic mechanisms. In this paper, we develop computationally efficient iterative auction mechanisms for solving combinatorial exchanges. Our mechanisms satisfy Individual-rationality (IR) and budget-nonnegativity (BN) properties. We also show that our method is bounded and convergent. Our numerical experiments show that our algorithm produces good quality solutions and is computationally efficient.

Relevância:

20.00% 20.00%

Publicador:

Resumo:

Combinatorial exchanges are double sided marketplaces with multiple sellers and multiple buyers trading with the help of combinatorial bids. The allocation and other associated problems in such exchanges are known to be among the hardest to solve among all economic mechanisms. It has been shown that the problems of surplus maximization or volume maximization in combinatorial exchanges are inapproximable even with free disposal. In this paper, the surplus maximization problem is formulated as an integer linear programming problem and we propose a Lagrangian relaxation based heuristic to find a near optimal solution. We develop computationally efficient tâtonnement mechanisms for clearing combinatorial exchanges where the Lagrangian multipliers can be interpreted as the prices of the items set by the exchange in each iteration. Our mechanisms satisfy Individual-rationality and Budget-nonnegativity properties. The computational experiments performed on representative data sets show that the proposed heuristic produces a feasible solution with negligible optimality gap.

Relevância:

20.00% 20.00%

Publicador:

Resumo:

We prove a lower bound of Omega(1/epsilon (m + log(d - a)) where a = [log(m) (1/4epsilon)] for the hitting set size for combinatorial rectangles of volume at least epsilon in [m](d) space, for epsilon is an element of [m(-(d-2)), 2/9] and d > 2. (C) 2002 Elsevier Science B.V. All rights reserved.

Relevância:

20.00% 20.00%

Publicador:

Resumo:

Composite coatings containing quasicrystalline (QC) phases in Al-Cu-Fe alloys were prepared by laser cladding using a mixture of the elemental powders. Two substrates, namely pure aluminum and an Al-Si alloy were used. The clad layers were remelted at different scanning velocities to alter the growth conditions of different phases. The process parameters were optimized to produce quasicrystalline phases. The evolution of the microstructure in the coating layer was characterized by detailed microstructural investigation. The results indicate presence of quasicrystals in the aluminum substrate. However, only approximant phase could be observed in the substrate of Al-Si alloys. It is shown that there is a significant transport of Si atoms from the substrate to the clad layer during the cladding and remelting process. The hardness profiles of coatings on aluminum substrate indicate a very high hardness. The coating on Al-Si alloy, on the other hand, is ductile and soft. The fracture toughness of the hard coating on aluminum was obtained by nano-indentation technique. The K1C value was found to be 1.33 MPa m1/2 which is typical of brittle materials.

Relevância:

20.00% 20.00%

Publicador:

Resumo:

Web services are now a key ingredient of software services offered by software enterprises. Many standardized web services are now available as commodity offerings from web service providers. An important problem for a web service requester is the web service composition problem which involves selecting the right mix of web service offerings to execute an end-to-end business process. Web service offerings are now available in bundled form as composite web services and more recently, volume discounts are also on offer, based on the number of executions of web services requested. In this paper, we develop efficient algorithms for the web service composition problem in the presence of composite web service offerings and volume discounts. We model this problem as a combinatorial auction with volume discounts. We first develop efficient polynomial time algorithms when the end-to-end service involves a linear workflow of web services. Next we develop efficient polynomial time algorithms when the end-to-end service involves a tree workflow of web services.

Relevância:

20.00% 20.00%

Publicador:

Resumo:

An elementary combinatorial Tanner graph construction for a family of near-regular low density parity check (LDPC) codes achieving high girth is presented. These codes are near regular in the sense that the degree of a left/right vertex is allowed to differ by at most one from the average. The construction yields in quadratic time complexity an asymptotic code family with provable lower bounds on the rate and the girth for a given choice of block length and average degree. The construction gives flexibility in the choice of design parameters of the code like rate, girth and average degree. Performance simulations of iterative decoding algorithm for the AWGN channel on codes designed using the method demonstrate that these codes perform better than regular PEG codes and MacKay codes of similar length for all values of Signal to noise ratio.

Relevância:

20.00% 20.00%

Publicador:

Resumo:

We look at graphical descriptions of block codes known as trellises, which illustrate connections between algebra and graph theory, and can be used to develop powerful decoding algorithms. Trellis sizes for linear block codes are known to grow exponentially with the code parameters. Of considerable interest to coding theorists therefore, are more compact descriptions called tail-biting trellises which in some cases can be much smaller than any conventional trellis for the same code . We derive some interesting properties of tail-biting trellises and present a new decoding algorithm.