A new parallel algorithm is presented for the 0/1 knapsack problem. On a hypercube of n processors, the algorithm runs in time O(mc(log n)/n), where m is the number of objects and c is the knapsack size. The best prev...
详细信息
A new parallel algorithm is presented for the 0/1 knapsack problem. On a hypercube of n processors, the algorithm runs in time O(mc(log n)/n), where m is the number of objects and c is the knapsack size. The best previous known hypercube algorithm takes time O(mc/n+c log n+c/sup 2/). The new algorithm has been implemented on the Connection Machine and experimental results show that it performs very well for a wide range of problem sizes.< >
Key algorithms and properties of 1-d IC layout compaction are presented. In particular, the spacing constraint formulation problem is mapped into the vertical visibility graph construction problem, whose time complexi...
详细信息
Key algorithms and properties of 1-d IC layout compaction are presented. In particular, the spacing constraint formulation problem is mapped into the vertical visibility graph construction problem, whose time complexity is O(n log n) if element swappings are not considered. This approach generates enough constraints for the later automatic jogging purposes, while maintaining graph sparsity. The graph solution algorithm is made event-driven to achieve O(n/sup 1.5/ log n) expected running time. For hierarchical module assembly. a simple port abstraction method is used with O(n/sup 1.5/ log n) worst-case time complexity that allows cells to stretch and pitch match. The speed involvement is due to a transformation to ensure all weights are nonpositive, where the fast Dijkstra's longest path algorithm call be used. A reverse transformation is required to obtain the solution. An integrated leaf cell compaction and module assembly algorithm was proved to be free from the xy interlock problem. The module assembly problem was established as an integer linear programming problem where there is no known fast algorithm. A heuristic method is used instead to explore layout hierarchy as a practical solution with high speed, low memory and minor area penalties.< >
Two methods are developed and evaluated for shunt VAr planning. These methods are capable of sizing and siting shunt VAr at optimum cost and with greater reliability. The methods utilize the generalized Benders decomp...
详细信息
Two methods are developed and evaluated for shunt VAr planning. These methods are capable of sizing and siting shunt VAr at optimum cost and with greater reliability. The methods utilize the generalized Benders decomposition (GBD) technique to decompose the VAr problem into two subproblems. The first level of the problem solves an optimal power flow problem by scheduling control variables including existing VAr sources. The two methods for the second-level discrete allocation process use a branch-and-bound enumeration technique and a mixed-integer linear programming technique. The constraints include security while minimizing the total investment cost. Tests on the IEEE 14-bus system have shown both algorithms to be robust and fast.< >
Timed event-graphs, a special class of timed Petri nets, are used for modelling and analyzing job-shop systems. The modelling allows the steady-state performance of the system to be evaluated under a deterministic and...
详细信息
Timed event-graphs, a special class of timed Petri nets, are used for modelling and analyzing job-shop systems. The modelling allows the steady-state performance of the system to be evaluated under a deterministic and cyclic production process. Given any fixed processing times, the productivity (i.e., production rate) of the system can be determined from the initial state. It is shown in particular that, given any desired product mix, it is possible to start the system with enough jobs in process so that some machines will be fully utilized in steady-state. These machines are called bottleneck machines, since they limit the throughput of the system. In that case, the system works at the maximal rate and the productivity is optimal. The minimal number of jobs in process allowing optimal functioning of the system is further specified as an integer linear programming problem. An efficient heuristic algorithm is developed to obtain a near-optimal solution.< >
A combinatorial optimization technique has been developed and applied to the scheduling problem in data path synthesis. The cost function is minimized using a gradient-like method, and constraints are satisfied by a n...
详细信息
A combinatorial optimization technique has been developed and applied to the scheduling problem in data path synthesis. The cost function is minimized using a gradient-like method, and constraints are satisfied by a new technique analogous to the combination of the penalty method and the feasible direction method used for nonlinear optimization. To overcome the drawbacks of assigning operations to control steps one at a time, this technique assigns all the operations to control steps simultaneously. Experimental results show that this method is as good as or better than other published methods.< >
Two new register allocation concepts are presented. One is the concept of the profit of allocation, which minimizes the number of registers and the interconnection cost simultaneously. The other is the concept of cutt...
详细信息
Two new register allocation concepts are presented. One is the concept of the profit of allocation, which minimizes the number of registers and the interconnection cost simultaneously. The other is the concept of cutting lifetime segment, which reduces the number of registers to a minimum. A global register allocation optimal algorithm (GRAOA), which obtains an optimal number of registers and near-optimal interconnection cost, is presented. This algorithm takes O(TR/sup 3/), where T is the number of slices and R is the minimum number of registers needed.< >
A technique for application of correctness-preserving transformations to designs, described in an existing hardware description language, is presented. A program transformation technique based on integerlinear progra...
详细信息
A technique for application of correctness-preserving transformations to designs, described in an existing hardware description language, is presented. A program transformation technique based on integer linear programming (LP) is used to calculate automatically the structure description of the transformed design given the original designs' description and a transformation description. This technique is used for refining designs towards efficient implementations. It has been applied to the design of a systolic FIR filter and a parameterized multiplier-accumulator module used in the Cathedral-II silicon compilation system.< >
Given a bidirected graphG and a vectorb of positive integral node-weights, an integerlinear program IP is defined on (G, b). IP generalizes the node packing problem on a node-weighted (undirected) graph in the sense ...
详细信息
Given a bidirected graphG and a vectorb of positive integral node-weights, an integerlinear program IP is defined on (G, b). IP generalizes the node packing problem on a node-weighted (undirected) graph in the sense that it reduces to the latter whenG is undirected. A polynomial time algorithm is given that recognizes whether CP (the linear program obtained by relaxing the integrality constraints of IP) has an integral optimal solution. Also an efficient method for solving the linearprogramming dual of CP is described.
We consider integer linear programming problems with a fixed coefficient matrix and varying objective function and right-hand-side vector. Among our results, we show that, for any optimal solution to a linear program ...
详细信息
We consider integer linear programming problems with a fixed coefficient matrix and varying objective function and right-hand-side vector. Among our results, we show that, for any optimal solution to a linear program max{wx: Ax≤b}, the distance to the nearest optimal solution to the corresponding integer program is at most the dimension of the problem multiplied by the largest subdeterminant of the integral matrixA. Using this, we strengthen several integerprogramming ‘proximity’ results of Blair and Jeroslow; Graver; and Wolsey. We also show that the Chvátal rank of a polyhedron {x: Ax≤b} can be bounded above by a function of the matrixA, independent of the vectorb, a result which, as Blair observed, is equivalent to Blair and Jeroslow's theorem that ‘each integerprogramming value function is a Gomory function.’
暂无评论