Method of and apparatus for determining an optimal solution to a uniform-density layout problem, and medium on which a program for determining the solution is stored

A computer-implemented method of determining a first optimal solution to a first layout problem requiring an optimal layout of a multiplicity of elements in a predetermined region under a first set of conditions, which includes a uniformalization condition such that the multiple elements are distributed in substantially uniform density throughout the predetermined region, as the first optimal solution, comprising the steps of:

• (a) obtaining an initial layout of the multiple elements in the predetermined region;
• (b) analyzing said first layout problem into the uniformalization condition and a second layout problem requiring an optimal layout of the multiple elements in the same predetermined region under a second set of conditions, which comprises the remaining conditions of the first set of conditions other than the uniformalization condition, as a second optimal solution and generating a linear combination of a first objective function, which represents the second set of conditions of said second layout problem, and a second objective function, which represents the uniformalization condition of said first layout problem, as a third objective function, which is assumed to represent the first set of conditions of said first layout problem;
• and
• (c) optimizing the third objective function generated in said step (b) by executing an iterative-improvement algorithm on said third objective function using said initial layout obtained in said step (a) as an initial solution, whereby the first optimal solution to the first layout problem is determined.

An apparatus for determining a first optimal solution to a first layout problem requiring an optimal layout of a multiplicity of elements in a predetermined region under a first set of conditions, which includes a uniformalization condition such that the multiple elements are distributed in substantially uniform density throughout the predetermined region, as the first optimal solution, comprising:

• an objective-function generating section analyzing said first layout problem into the uniformalization condition and a second layout problem requiring an optimal layout of the multiple elements in the same predetermined region under a second set of conditions, which comprises the remaining conditions of the first set of conditions other than the uniformalization condition, as a second optimal solution and generating a linear combination of a first objective function, which represents the second set of conditions of the formulated second layout problem, and a second objective function, which represents the uniformalization condition of the first layout problem, as a third objective function, which is assumed to represent the first set of conditions of the first layout problem;
• and
• an objective-function optimizing section optimizing the third objective function generated by said objective-function generating section, thereby determining the first optimal solution to the first layout problem.

An apparatus for determining a first optimal solution to a first layout problem requiring an optimal layout of a multiplicity of elements in a predetermined region under a first set of conditions, which includes a uniformalization condition such that the multiple elements are distributed in substantially uniform density throughout the predetermined region, as the first optimal solution, comprising:

• an initial-layout obtaining section obtaining an initial layout of the multiple elements in the predetermined region;
• an objective-function generating section analyzing said first layout problem into the uniformalization condition and a second layout problem requiring an optimal layout of the multiple elements in the same predetermined region under a second set of conditions, which comprises the remaining conditions of the first set of conditions other than the uniformalization condition, as a second optimal solution and generating a linear combination of a first objective function, which represents the second set of conditions of the formulated second layout problem, and a second objective function, which represents the uniformalization condition of the first layout problem, as a third objective function, which is assumed to represent the first set of conditions of the first layout problem;
• and
• an iterative-improvement-algorithm executing section optimizing the third objective function generated in said objective-function generating section by executing an iterative-improvement algorithm on the third objective function using the initial layout obtained in said initial-layout obtaining section as an initial solution, thereby determining the first optimal solution to the first layout problem.

A computer-readable storage medium storing a computer program for determining a first optimal solution to a first layout problem requiring an optimal layout of a multiplicity of elements in a predetermined region under a first set of conditions, which includes a uniformalization condition such that the multiple elements are distributed in substantially uniform density throughout the predetermined region, as the first optimal solution, and said program instructs a computer to carry out the following procedures of:

• (A) analyzing said first layout problem into the uniformalization condition and a second layout problem requiring an optimal layout of the multiple elements in the same predetermined region under a second set of conditions, which comprises the remaining conditions of the first set of conditions other than the uniformalization condition, as a second optimal solution and generating a linear combination of a first objective function, which represents the second set of conditions of said second layout problem, and a second objective function, which represents the uniformalization condition of said first layout problem, as a third objective function, which is assumed to represent the first set of conditions of said first layout problem;
• and
• (B) optimizing said third objective function generated in said procedure (A), whereby the first optimal solution to the first layout problem is determined.

A computer-readable storage medium storing a computer program for determining a first optimal solution to a first layout problem requiring an optimal layout of a multiplicity of elements in a predetermined region under a first set of conditions, which includes a uniformalization condition such that the multiple elements are distributed in substantially uniform density throughout the predetermined region, as the first optimal solution, and said program instructs a computer to carry out the following procedures of:

• (a) obtaining an initial layout of the multiple elements in the predetermined region;
• (b) analyzing said first layout problem into the uniformalization condition and a second layout problem requiring an optimal layout of the multiple elements in the same predetermined region under a second set of conditions, which comprises the remaining conditions of the first set of conditions other than the uniformalization condition, as a second optimal solution and generating a linear combination of a first objective function, which represents the second set of conditions of said second layout problem, and a second objective function, which represents the uniformalization condition of said first layout problem, as a third objective function, which is assumed to represent the first set of conditions of said first layout problem;
• and
• (c) optimizing the third objective function generated in said procedure (b) by executing an iterative-improvement algorithm on said third objective function using said initial layout obtained in said procedure (a) as an initial solution, whereby the first optimal solution to the first layout problem is determined.

A computer-implemented method comprising:

• analyzing a first layout problem requiring an optimal layout of a plurality of elements in a predetermined region under a first set of conditions that includes a uniformalization condition, into
• a first objective function defined by the uniformalization condition, and
• a second objective function defined by a second set of conditions, which comprises the remaining conditions of the first set of conditions other than the uniformalization condition;
• generating a linear combination of the first objective function and the second objective function, as a third objective function;
• and
• optimizing the third objective function,
• wherein the uniformalization condition requires that the plurality of elements are distributed in substantially uniform density throughout the predetermined region.

A computer-implemented method comprising:

• analyzing a first problem to layout a plurality of elements under a first set of conditions that includes a uniformalization condition, into
• a first objective function defined by the uniformalization condition, and
• a second objective function defined by a second set of conditions, which comprises the remaining conditions of the first set of conditions other than the uniformalization condition;
• generating a linear combination of the first objective function and the second objective function, as a third objective function;
• and
• optimizing the third objective function.

An apparatus comprising:

• a means for analyzing a first problem to layout a plurality of elements under a first set of conditions that includes a uniformalization condition, into
• a first objective function defined by the uniformalization condition, and
• a second objective function defined by a second set of conditions, which comprises the remaining conditions of the first set of conditions other than the uniformalization condition;
• a means for generating a linear combination of the first objective function and the second objective function, as a third objective function;
• and
• a means for optimizing the third objective function.