Mixed and Pure Integer Programming Problems

Mixed Integer Programming

所有的 Mixed Integer Programming（混合整数问题，即变量里既有离散整数，又有连续变量）可以表述成如下的形式：

• 如果 $n_0=n$，此时 $\bold{x}$ 为整数，称为 Pure Integer Programming.
• 如果一个解 $\bold x$ 满足所有的 $g_j(\bold{x}), h_k(\bold{x})$ 条件和整数约束条件，那么称 $\bold x$ 为 Integer Feasible 的.
  • 如果 $g_j, h_k$ 满足但是整数约束条件不满足，那么称 $\bold{x}$ 为 Continuous Feasible 的

我们已经知道如何解决全是连续变量的问题了。所以一个可行的思路就是把整数变量消除掉，然后当作连续变量的问题进行处理。

Branch-and-Bound Method

我们把搜索空间按照整数变量进行划分，例如 $x_i\in\Z$，则可以把所有的可行解分成两类：$x_i\le T$, $x_i\gt T$. 显然，由于 $x_i$ 的范围并不同，所以这两个解空间互不相交。

Generic Algorithm

Genetic Algorithm 是遗传算法的一种，遗传算法的核心是 “survival of the fittest”. 我们首先需要把 design variable 表示成 chromosome code (genetic code)

Genetic Algorithm 的流程可以概括为下：

graph TB;
A((Begin)) --> B[Initialize Population of 1st generation]
B --> C[Fitness Evaluation]
C --> D{"Termination
Condition Satisfied?"}
D --> |Yes| E[Stop]
D --> |No| F[Selection]
F --> G[Crossover/Mutation]
G --> H[Populate next Generation]
H --> C

Initialization of Population

• Population size
• Randomly generated individuals

Selection

• Selection Method:
  1. Roulette Wheel Selection
  2. Stochastic Remainder Method
  3. Tournament Selection
• Mating Pool

Reproduction

• Mating
  • Crossover
  • Probability of Crossover
• Mutation
  • Probability of Mutation
• genetic operations (crossover and mutation)
• genetic operators (crossover and mutation operators)
• parents and offspring (children)
• create population of the next generation

Termination of Procedures

• The total (cumulative) number of generations has reached a prescribed maximum.
• When no significant improvement has been achieved over some number of generations.
• When some (desired) target fitness value has been attained
• Convergence of designs (similarity among designs within the population and/or across generations)
• Total amount of computational resources consumed has reached some pre-defined limit