The formulation of some allocation and connection problems as integer programs

Melvin A. Breuer

Naval Research Logistics Quarterly, 1966, vol. 13, issue 1, 83-95

Abstract: In this paper a component placement problem and a digital computer backboard wiring problem are formulated as integer linear programs. The component placement problem consists of making a unique assignment of components to column positions such that wireability is maximized. The backboard wiring problem consists of three interrelated subproblems, namely, the placement, the connection, and the routing problems. The placement and connection problems are combined and solved as one, thereby giving the optimal circuit connections as well as minimizing the total lead length. It is shown that under certain assumptions, the number of inequalities and variables in the problem can be greatly reduced. Further simplifying assumptions lead to a near optimal solution. Examples of other allocation problems to which the models presented here are applicable are given. The following concepts are formulated as linear inequalities: (1) the absolute magnitude of the difference between two variables; (2) minimize the minimum function of a set of functions; and (3) counting the number of (0, 1) adjacent component pairs in a vector.

Date: 1966
References: Add references at CitEc
Citations:

Downloads: (external link)
https://doi.org/10.1002/nav.3800130107

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wly:navlog:v:13:y:1966:i:1:p:83-95

Access Statistics for this article

More articles in Naval Research Logistics Quarterly from John Wiley & Sons
Bibliographic data for series maintained by Wiley Content Delivery ().