Discrete Optimum Design

Mixed Variables, Branch-and-Bound, and Adaptive Discrete Search

Reference: Jasbir Singh Arora, Introduction to Optimum Design, 4th ed., Academic Press, 2017, Ch. 15.

이 장에서는 continuous variables와 discrete variables가 함께 나타나는 optimum design problem을 정리한다. Available thickness, integer component count, material choice, catalog section처럼 실제 설계에서 자연스럽게 발생하는 discreteness를 수학적으로 표현하고, full enumeration의 조합 폭발을 피하기 위한 branch-and-bound method를 살펴본다. 이어서 continuous relaxation, binary encoding, dynamic rounding, neighborhood search, linked variables, adaptive discrete search의 적용 조건과 한계를 비교한다.


Types of Discrete Variables

  • Discrete variable: 주어진 finite set의 값만 선택할 수 있는 variable이다.
  • Integer variable: integer values만 허용되는 discrete variable이다.
  • Binary variable: $0$ 또는 $1$만 갖는 discrete variable이다.
  • Linked discrete variable: 하나의 선택이 material properties나 section properties처럼 여러 parameters를 동시에 결정하는 variable이다.

Integer variable은 discrete variable의 특수한 경우이다. 반면 catalog choice는 allowable values가 일정한 간격을 갖지 않을 수 있으며, linked choice는 선택된 항목에 포함된 properties를 서로 독립적으로 변경할 수 없다.


Mixed-Variable Optimum Design

$n_d$개의 discrete variables와 $n-n_d$개의 continuous variables를 갖는 mixed-variable optimum design problem, MV-OPT를

\[\begin{aligned} \underset{x\in\mathbb{R}^n}{\operatorname{minimize}}\quad & f(x) \\ \text{subject to}\quad & h_j(x)=0, && j=1,\ldots,p, \\ & g_k(x)\leq0, && k=1,\ldots,m, \\ & x_i\in D_i, && i=1,\ldots,n_d, \\ & x_{iL}\leq x_i\leq x_{iU}, && i=n_d+1,\ldots,n \end{aligned}\]

로 정의한다. 각 discrete set은

\[D_i = \left\{ d_{i1},d_{i2},\ldots,d_{iq_i} \right\}\]

이고 $q_i$는 $i$th variable의 allowable values 수이다. Integer, binary, catalog, material-choice problems를 모두 이 형식에 포함할 수 있다.


Classification of MV-OPT Problems

Chapter 15는 functions의 regularity와 nondiscrete evaluation 가능 여부에 따라 문제를 다섯 종류로 구분한다.

  1. MV-OPT 1: Functions가 twice continuously differentiable하고 discrete variables를 intermediate nondiscrete values에서 평가할 수 있다.
  2. MV-OPT 2: Functions가 일부 points에서 nondifferentiable이지만 nondiscrete values에서 function evaluation은 가능하다.
  3. MV-OPT 3: 일부 variables는 solution process 중에도 반드시 discrete values만 가져야 한다.
  4. MV-OPT 4: Discrete choice가 여러 linked parameters를 동시에 결정한다.
  5. MV-OPT 5: 순서나 조합 자체가 design인 purely discrete combinatorial problem이다.

Continuous relaxation, gradient, linearization을 이용하는 methods는 주로 MV-OPT 1에 적용된다. Nondiscrete point에서 functions를 정의할 수 없거나 variables가 linked되어 있으면 gradient-based continuous method를 직접 적용할 수 없다.


Combinatorial Growth

모든 discrete combinations를 평가하는 full enumeration의 경우 필요한 combinations 수는

\[N_c = \prod_{i=1}^{n_d}q_i\]

이다. 모든 variables가 각각 $q$개의 allowable values를 가지면

\[N_c=q^{n_d}\]

이므로 problem size는 discrete variables 수에 대해 exponentially 증가한다.

Full enumeration은 finite search이므로 모든 combinations를 평가할 수 있다면 global discrete optimum을 찾는다. 그러나 practical problem에서는 계산량이 너무 크므로, 대부분의 methods는 일부 combinations만 명시적으로 평가하고 나머지를 논리적으로 제거하는 implicit enumeration을 사용한다.


Discrete Optimum

Discrete feasible set을

\[\mathcal{F}_D = \left\{ x: h(x)=0,\; g(x)\leq0,\; x_i\in D_i \right\}\]

라 하자. Global discrete optimum $x^{\star}$는

\[f(x^{\star}) \leq f(x), \qquad \forall x\in\mathcal{F}_D\]

를 만족한다.

Discrete point에서는 arbitrarily small feasible perturbation이 존재하지 않을 수 있다. 따라서 optimum에서 inequality constraint가 active일 필요가 없으며, continuous KKT conditions만으로 discrete optimality를 판정할 수 없다. Allowable values의 spacing이 넓을수록 continuous optimum과 discrete optimum의 차이도 커질 수 있다.


Continuous Relaxation

MV-OPT 1에서는 먼저 discrete restrictions를 제거하고

\[x_i\in \left[ \min D_i,\max D_i \right], \qquad i=1,\ldots,n_d\]

로 바꾼 continuous relaxation을 풀 수 있다. Minimization problem에서 relaxed feasible set은 original discrete feasible set을 포함하므로

\[f_{\mathrm{relax}}^{\star} \leq f_D^{\star}.\]

즉 continuous optimum value는 discrete optimum value의 lower bound이다. Feasible discrete design $\hat{x}$를 알고 있다면

\[f_{\mathrm{relax}}^{\star} \leq f_D^{\star} \leq f(\hat{x})\]

가 되어 lower and upper bounds를 동시에 얻는다.

Continuous solution은 search의 starting point와 lower bound를 제공하지만, componentwise nearest rounding이 optimum을 보장하지는 않는다. Rounding 후 constraints가 violated될 수 있고, high nonlinearity 또는 widely separated allowable values에서는 discrete optimum이 continuous solution의 neighborhood에 없을 수 있다.


Branch-and-Bound Concepts

Branch-and-bound method, BBM은 search tree의 일부 nodes만 조사하는 implicit enumeration method이다.

  • Node: 일부 discrete assignments 또는 추가 bounds가 지정된 subproblem이다.
  • Branching: 한 node를 mutually exclusive subproblems로 분할한다.
  • Lower bound: 해당 node 아래에서 얻을 수 있는 objective value의 하한이다.
  • Incumbent: 현재까지 찾은 가장 좋은 feasible discrete design이다.
  • Upper bound: Minimization에서 incumbent objective value이다.
  • Fathoming: 현재 node가 더 좋은 feasible completion을 만들 수 없다고 판단하여 제거하는 과정이다.

Purely discrete problem에서는 node마다 functions를 평가하고 discrete assignments를 추가한다. Nondiscrete evaluation이 가능한 문제에서는 각 node의 continuous relaxation을 풀어 stronger lower bound를 얻는다.


Branching from a Relaxed Solution

Node relaxation의 solution에서

\[d_{ij} < x_i^{\mathrm{relax}} < d_{i,j+1}\]

인 discrete variable을 선택한다. 이 node를

\[x_i\leq d_{ij}\]

와

\[x_i\geq d_{i,j+1}\]

을 각각 추가한 두 child nodes로 나눈다. 두 branches는 current nondiscrete interval을 제거하지만 allowable discrete values는 제거하지 않는다.

Branching variable을 선택하는 기준으로는 nearest discrete value까지의 거리, fixing에 따른 cost increase, 또는 빠르게 좋은 incumbent를 만들 가능성을 사용할 수 있다. 좋은 incumbent를 일찍 찾을수록 upper bound가 작아져 더 많은 nodes를 제거할 수 있다.


Bounding and Fathoming

각 node $\mathcal{N}$의 continuous relaxation value를 $L(\mathcal{N})$, incumbent upper bound를 $U$라 하자. Node는 다음 경우 fathom된다.

  1. Node relaxation이 infeasible이다.
  2. Relaxed solution이 discrete feasible solution이며 incumbent를 갱신할 수 있다.
  3. Bound가
\[L(\mathcal{N})\geq U\]

를 만족한다.

세 번째 조건에서는 해당 node의 어떠한 completion도 incumbent보다 작은 objective value를 가질 수 없다. 모든 nodes가 fathom되면 search가 종료된다.

Linear 또는 convex problem에서 node subproblems를 globally 풀면 BBM은 global discrete optimum을 보장한다. General nonlinear nonconvex problem에서 local minimizer만 사용하면 node bound가 valid global lower bound가 아닐 수 있으므로, true global solution이 포함된 branch를 너무 일찍 제거할 수 있다.


Binary Encoding of Discrete Choices

Discrete variable $x_i\in D_i$에 대하여 binary selectors

\[z_{ij}\in\{0,1\}, \qquad j=1,\ldots,q_i\]

를 정의한다. One-hot constraints

\[x_i = \sum_{j=1}^{q_i}z_{ij}d_{ij}, \qquad \sum_{j=1}^{q_i}z_{ij}=1\]

을 사용하면 정확히 하나의 allowable value가 선택된다.

Linear discrete problem은 이 substitution을 통해 0-1 programming problem으로 변환할 수 있다. 표현은 명확하지만

\[\sum_{i=1}^{n_d}q_i\]

개의 binary variables가 필요하므로 allowable sets가 크면 formulation size가 크게 증가한다.


Sequential Linearization

MV-OPT 1에서는 current point $x^{(k)}$에서 nonlinear functions를 linearize하여 discrete linear subproblem을 반복할 수 있다.

\[f\!\left(x^{(k)}+\Delta x\right) \approx f\!\left(x^{(k)}\right) + \nabla f\!\left(x^{(k)}\right)^T\Delta x,\] \[g_i\!\left(x^{(k)}+\Delta x\right) \approx g_i\!\left(x^{(k)}\right) + \nabla g_i\!\left(x^{(k)}\right)^T\Delta x.\]

Linearized subproblem은 integer or binary programming method로 풀고, 새 point에서 functions를 다시 linearize한다. Continuous optimum을 먼저 계산하고 그 neighborhood의 allowable values만 남기면 subproblem을 줄일 수 있다.

이 방법은 derivatives와 nondiscrete function evaluations가 필요하다. 또한 local linear model과 restricted neighborhood에 의존하므로 general nonlinear problem에서 global discrete optimum을 보장하지 않는다.


Dynamic Rounding-Off

모든 variables를 한 번에 nearest values로 rounding하면 infeasibility와 large objective increase가 발생할 수 있다. Dynamic rounding은 variables를 순차적으로 고정하고 매 단계에서 continuous problem을 다시 푼다.

  1. 모든 design variables를 continuous로 취급하여 NLP를 푼다.
  2. Solution이 모두 discrete이면 종료한다.
  3. 각 unfixed variable을 neighboring discrete values로 perturb하고 Lagrangian value의 변화를 평가한다.
  4. 가장 작은 penalty를 갖는 variable과 discrete value를 선택하여 고정한다.
  5. Reduced continuous problem을 다시 풀고 반복한다.

한 번에 한 variable을 고정하면 최대 $n_d-1$개의 additional continuous problems가 필요하다. 여러 variables를 동시에 고정하면 계산량은 줄지만 잘못된 early assignment를 수정하기 어려워진다. 이 방법은 feasible discrete solution을 찾을 수 있지만 global optimality guarantee는 없다.


$n_d$와 $q_i$가 작으면 discrete variables를 가능한 값으로 고정한 뒤, 각 combination에서 remaining continuous variables를 최적화할 수 있다. 이 방식은 discrete-variable gradients가 필요 없고 구현이 단순하지만 combinations가 증가하면 full enumeration과 같은 한계를 갖는다.

큰 problem에서는 continuous solution 주변의 reduced sets

\[\widetilde{D}_i \subset D_i\]

만 선택하고

\[\widetilde{\mathcal{F}}_D = \widetilde{D}_1 \times\cdots\times \widetilde{D}_{n_d}\]

에서 search한다. Half-bandwidth $r$을 사용하면 current discrete value 주변의 약 $2r$개 allowable values로 search를 제한할 수 있다.

Reduced neighborhood search는 계산량을 크게 줄이지만

\[x_D^{\star} \notin \widetilde{\mathcal{F}}_D\]

일 수 있다. 따라서 neighborhood restriction은 efficiency와 global coverage 사이의 trade-off이다.


Linked Discrete Variables

Material 또는 catalog section을 선택하면 density, modulus, strength, area, inertia와 같은 properties가 동시에 정해진다. 하나의 property만 continuous variable로 두면 나머지 properties를 유일하게 복원할 수 없고, 모든 properties를 independent variables로 두면 catalog에 존재하지 않는 조합을 얻을 수 있다.

따라서 catalog index 또는 material type을 하나의 linked discrete variable로 두고, 선택된 table row의 모든 properties를 함께 사용해야 한다. 이러한 mappings는 일반적으로 analytic function으로 표현되지 않으며 choice index에 대해 differentiable하지 않다.

Linked-variable problem에서는 gradient-free discrete search가 직접적으로 적용된다. 다만 catalog ordering, dominance, physical monotonicity와 같은 problem structure를 이용하면 불필요한 choices를 제거하고 search를 줄일 수 있다.


Adaptive procedure는 continuous optimization과 progressive fixing을 결합한다.

  1. 가능하면 continuous relaxation을 푼다.
  2. Allowable discrete value에 가깝고 iteration 동안 변화가 작은 variables를 선택한다.
  3. 선택된 variables를 nearby discrete values로 고정한다.
  4. Remaining variables에 대해 problem을 다시 최적화한다.
  5. Constraint violation과 objective change를 확인하며 모든 variables가 discrete가 될 때까지 반복한다.

Adaptive search는 fixed variables를 제거하므로 subproblem dimension이 점차 감소한다. 또한 매 fixing 뒤 reoptimization을 수행하므로 simultaneous rounding보다 feasibility를 회복하기 쉽다.

그러나 fixing sequence가 달라지면 서로 다른 discrete solutions를 얻을 수 있다. Early decision이 이후 search space를 제한하므로 global optimality guarantee는 없으며, final design은 original constraints에 대해 별도로 검증해야 한다.


Method Selection

  • Full enumeration은 작은 finite problem에서 global solution을 제공하지만 $N_c$가 빠르게 증가한다.
  • Branch-and-bound는 가장 체계적인 implicit enumeration이며 valid bounds가 있을 때 global certificate를 제공한다.
  • Binary formulation은 discrete choices를 algebraic constraints로 바꾸지만 variable 수를 증가시킨다.
  • Sequential linearization은 smooth MV-OPT 1에 적합하지만 local model과 derivatives가 필요하다.
  • Dynamic rounding과 adaptive search는 continuous optimizer를 재사용하기 쉽지만 fixing sequence에 민감하다.
  • Neighborhood search는 continuous solution 부근에서 효율적이지만 distant discrete optimum을 놓칠 수 있다.
  • Linked-variable search는 catalog consistency를 유지해야 하며 independent-property relaxation을 허용해서는 안 된다.


Summary

  • MV-OPT는 continuous variables와 finite-set, integer, binary, linked variables를 하나의 constrained formulation에 포함한다.
  • Full enumeration의 combinations 수는 $N_c=\prod_i q_i$이므로 discrete variables 수에 따라 exponentially 증가한다.
  • Continuous relaxation은 minimization에서 discrete optimum의 lower bound를 제공하지만 direct rounding은 feasibility와 optimality를 보장하지 않는다.
  • BBM은 branching, lower bounds, incumbent upper bound, fathoming으로 search tree를 줄인다.
  • Binary selectors는 $x_i=\sum_jz_{ij}d_{ij}$와 $\sum_jz_{ij}=1$로 discrete choice를 표현한다.
  • Dynamic rounding과 adaptive search는 variables를 순차적으로 고정하고 remaining continuous problem을 반복해서 푼다.
  • Neighborhood restriction은 계산량을 줄이지만 continuous optimum에서 멀리 있는 discrete optimum을 제외할 수 있다.
  • Linked discrete variable은 하나의 catalog choice가 결정하는 모든 dependent properties를 함께 유지해야 한다.