Search results for "COMPLEXITY"
showing 10 items of 1094 documents
A fast heuristic for solving the D1EC coloring problem
2010
In this paper we propose an efficient heuristic for solving the Distance-1 Edge Coloring problem (D1EC) for the on-the-fly assignment of orthogonal wireless channels in wireless as soon as a topology change occurs. The coloring algorithm exploits the simulated annealing paradigm, i.e., a generalization of Monte Carlo methods for solving combinatorial problems. We show that the simulated annealing-based coloring converges fast to a sub optimal coloring scheme even for the case of dynamic channel allocation. However, a stateful implementation of the D1EC scheme is needed in order to speed-up the network coloring upon topology changes. In fact, a stateful D1EC reduces the algorithm’s convergen…
Resource allocation for OFDMA systems with multi-cell joint transmission
2012
This paper considers the downlink resource allocation of a coordinated multi-cell cluster in OFDMA systems with universal frequency reuse. Multi-cell joint transmission is considered via zero-forcing precoding. Furthermore, joint optimization of the user selection and power allocation across multiple subchannels and multiple cells is studied. The objective is to maximize the weighted sum rate under per-base-station power constraints. Based on general duality theory, two iterative resource allocation algorithms are proposed and compared with the optimal solution, which requires an exhaustive search of all possible combinations of users over all subchannels. Simulation results show that the t…
Data-Driven Pump Scheduling for Cost Minimization in Water Networks
2021
Pumps consume a significant amount of energy in a water distribution network (WDN). With the emergence of dynamic energy cost, the pump scheduling as per user demand is a computationally challenging task. Computing the decision variables of pump scheduling relies over mixed integer optimization (MIO) formulations. However, MIO formulations are NP-hard in general and solving such problems is inefficient in terms of computation time and memory. Moreover, the computational complexity of solving such MIO formulations increases exponentially with the size of the WDN. As an alternative, we propose a data-driven approach to estimate the decision variables of pump scheduling using deep neural netwo…
Combined K-Best sphere decoder based on the channel matrix condition number
2008
It is known that sphere decoding (SD) methods can provide maximum-likelihood (ML) detection over Gaussian MIMO channels with lower complexity than the exhaustive search. Channel matrix condition number represents an important influence on the performance of usual detectors. Throughout this paper, two particular cases of a SD method called K-Best carry out a combined detection in order to reduce the computational complexity with predictable performance degradation. Algorithm selection is based on channel matrix condition number thresholding. K-Best is a suboptimal SD algorithm for finding the ML solution of a detection problem. It is based on a fixed complexity tree search, set by a paramete…
A Simplified Analytical Approach for Optimal Planning of Distributed Generation in Electrical Distribution Networks
2019
DG-integrated distribution system planning is an imperative issue since the installing of distributed generations (DGs) has many effects on the network operation characteristics, which might cause significant impacts on the system performance. One of the most important characteristics that mostly varies because of the installation of DG units is the power losses. The parameters affecting the value of the power losses are number, location, capacity, and power factor of the DG units. In this paper, a new analytical approach is proposed for optimally installing DGs to minimize power loss in distribution networks. Different parameters of DG are considered and evaluated in order to achieve a hig…
Field estimation in wireless sensor networks using distributed kriging
2012
In this paper, we tackle the problem of spatial interpolation for distributed estimation in Wireless Sensor Networks by using a geostatistical technique called kriging. We present a novel Distributed Iterative Kriging Algorithm (DIKA) which is composed of two main phases. First, the spatial dependence of the field is exploited by calculating semivariograms in an iterative way. Second, the kriging system of equations is solved by an initial set of nodes in a distributed manner, providing some initial interpolation weights to each node. In our algorithm, the estimation accuracy can be improved by iteratively adding new nodes and updating appropriately the weights, which leads to a reduction i…
A challenging family of automata for classical minimization algorithms
2010
In this paper a particular family of deterministic automata that was built to reach the worst case complexity of Hopcroft's state minimization algorithm is considered. This family is also challenging for the two other classical minimization algorithms: it achieves the worst case for Moore's algorithm, as a consequence of a result by Berstel et al., and is of at least quadratic complexity for Brzozowski's solution, which is our main contribution. It therefore constitutes an interesting family, which can be useful to measure the efficiency of implementations of well-known or new minimization algorithms.
Team Theory and Person-by-Person Optimization with Binary Decisions
2012
In this paper, we extend the notion of person-by-person (pbp) optimization to binary decision spaces. The novelty of our approach is the adaptation to a dynamic team context of notions borrowed from the pseudo-boolean optimization field as completely local-global or unimodal functions and submodularity. We also generalize the concept of pbp optimization to the case where groups of $m$ decisions makers make joint decisions sequentially, which we refer to as $m$b$m$ optimization. The main contribution is a description of sufficient conditions, verifiable in polynomial time, under which a pbp or an $m$b$m$ optimization algorithm converges to the team-optimum. As a second contribution, we prese…
A contribution on the optimization strategies based on moving least squares approximation for sheet metal forming design
2012
Computer-aided procedures to design and optimize forming processes are, nowadays, crucial research topics since industrial interest in costs and times reduction is always increasing. Many researchers have faced this research challenge with various approaches. Response surface methods (RSM) are probably the most known approaches since they proved their effectiveness in the recent years. With a peculiar attention to sheet metal forming process design, RSM should offer the possibility to reduce the number of numerical simulations which in many cases means to reduce design times and complexity. Actually, the number of direct problems (FEM simulations) to be solved in order to reach good functio…
A branch-and-cut algorithm for the pallet loading problem
2005
We propose a branch-and-cut algorithm for the pallet loading problem. The 0-1 formulation proposed by Beasley for cutting problems is adapted to the problem, adding new constraints and new procedures for variable reduction. We then take advantage of the relationship between this problem and the maximum independent set problem to use the partial linear description of its associated polyhedron. Finally, we exploit the specific structure of our problem to define the solution graph and to develop efficient separation procedures. We present computational results for the complete sets Cover I (up to 50 boxes) and Cover II (up to 100 boxes).