제약 최적화에서 Simplex·Interior Point·유전 알고리즘을 고르는 법
제약 최적화 문제의 선형성·볼록성·이산성을 기준으로 Simplex, Interior Point, 유전 알고리즘의 적용 조건과 운영 관점을 정리한다.
2026-08-14 · 최초 발행 2024-04-29
문제 구조가 해법을 결정한다
제약 최적화는 목적함수를 최소화하거나 최대화하면서 등식 및 부등식 제약을 만족하는 해를 찾는 문제다. 변수는 연속형일 수도 이산형일 수도 있고, 목적함수와 제약식은 선형 또는 비선형일 수 있다. 볼록성 여부도 전역 최적해를 보장할 수 있는지에 직접 영향을 준다.
라그랑지안과 KKT 조건은 최적성의 성질을 규정하는 데 쓰인다. 이중성(Duality)은 최적값의 경계를 해석하는 수단이며, 정규성 조건(CQ)이 성립하는지도 함께 확인해야 한다.
문제는 대체로 다음 성격으로 나뉜다.
- 목적함수와 제약이 모두 선형식이면 LP 또는 MILP로 정식화한다.
- 목적함수 또는 제약에 비선형이 포함되면 볼록성에 따라 전역 최적성 보장 가능성이 달라진다.
- 불확실성이나 이산성이 크면 강건·확률적 최적화, 조합최적화, 메타휴리스틱을 함께 검토한다.
선형 구조에는 Simplex를 우선 검토한다
Simplex는 다면체의 꼭짓점 사이를 피벗 이동하며 목적함수를 개선한다. Phase I/II 절차로 가용해를 찾고 최적화하며, 이중성 해석을 바탕으로 민감도 분석도 수행할 수 있다.
대규모 선형 문제에서 평균적으로 빠르게 수렴하고, 희소 행렬 구조를 잘 활용한다. 다만 퇴화(degeneracy)가 발생하면 싸이클링을 막기 위해 블랜드 규칙 등을 적용해야 한다. 스케일링과 프리솔브도 수치 안정성에 영향을 준다.
등식 제약은 슬랙 또는 서플러스 변수로 변환하며, 비가용 해와 무한 해도 탐지할 수 있다.
Interior Point는 비선형 제약을 KKT 시스템으로 다룬다
Interior Point는 장벽(barrier) 함수와 프라이멀-듀얼 뉴턴 단계를 이용해 KKT 시스템을 반복적으로 푼다. 희소 LDLᵀ 같은 선형대수 처리와 선조건자 품질이 성능을 좌우한다.
볼록 문제에서는 전역 최적성을 보장할 수 있지만, 비볼록 문제에서는 국소 최적해로 수렴할 수 있다. 라인서치와 트러스트-리전 조합은 수렴 안정성을 높이는 데 사용된다.
불평등 제약은 장벽 함수로 반영하고, 등식 제약은 KKT 시스템에 직접 넣는다. 초기 실내점(feasible interior)의 품질도 중요한 변수다.
유전 알고리즘은 복잡한 탐색 공간에서 제약을 설계한다
유전 알고리즘은 개체 코딩, 적합도 평가, 선택, 교차, 돌연변이를 반복하며 해를 진화시킨다. 교차율·변이율·선택압으로 탐색과 활용의 균형을 조절한다.
제약은 패널티(벌점), 수리(repair), 우선규칙(feasibility-first)을 조합해 처리할 수 있다. 비미분 목적함수, 이산 변수, 복잡한 제약이 얽힌 문제에서 유용하다.
수렴에는 확률적 변동이 있으므로 시드 고정과 다중 시작을 권장한다. 계산 비용을 줄이려면 개체 평가를 병렬화하거나 서로게이트 모델과 결합할 수 있다.
기법별로 달라지는 성능과 운영 부담
| 방법 | 성능 | 확장성 | 일관성 | 안정성 | 운영 편의 |
|---|---|---|---|---|---|
| Simplex | 선형 대규모에 고속 수렴 | 희소 대규모 LP에 우수 | 결정적 해 재현성 높음 | 퇴화 시 조심 필요 | 모델링 용이, 도구 풍부 |
| Interior Point | 볼록 NLP에 준최신 고성능 | 희소 KKT에 강함 | 초기화 의존 낮음(볼록) | 수치 선형대수 품질 중요 | 튜닝 중간 난이도 |
| Genetic Algorithms | 전역 탐색 강점, 국소정교화 필요 | 개체 병렬화로 수평 확장 | 확률적 변동 있음 | 잡음/비미분에 강인 | 파라미터·제약 처리 설계 필요 |
생산 계획부터 스케줄링까지의 적용 범위
생산 믹스, 수송 문제, 네트워크 플로우에는 LP(Simplex)를 적용할 수 있으며, 이산 의사결정이 섞이면 MILP를 병용한다.
포트폴리오의 분산-수익 균형처럼 Quadratic/Convex 구조를 가진 문제에는 Interior Point가 적합하다. 거래비용이나 밴드 제약을 추가한 경우에도 활용할 수 있다.
공정 조건과 엔지니어링 설계 변수에 비선형 제약이 걸리면 Interior Point 또는 GA를 검토한다. 목적함수가 멀티모달이면 GA와 로컬 서치를 결합하는 하이브리드 방식이 후보가 된다. 작업 스케줄과 하이퍼파라미터 튜닝처럼 이산·비미분 목적을 다룰 때도 GA를 사용할 수 있으며, 이 경우 repair 연산을 제약 위반 최소화에 맞춰 설계한다.
모델링부터 운영화까지의 반복 경로
입력 단계에서는 목표와 KPI를 정의하고, 변수와 제약을 목록화한다. 데이터 범위·단위·불확실성도 명시해야 한다.
처리 단계에서는 선형성·볼록성·이산성을 판정한 뒤 Simplex, Interior Point, GA 또는 하이브리드 방식을 선택한다. 이어 스케일링·정규화·프리솔브를 적용하고, 초기해 또는 초기집단과 파라미터 튜닝 계획을 정한다. 실행 중에는 수렴 상태와 정지 기준을 확인한다.
출력은 최적해뿐 아니라 라그랑주 승수, 민감도, 시나리오 분석을 포함한 보고로 이어진다.
비가용(Infeasible) 상태에서는 제약 완화, 슬랙 변수 도입, 데이터 정합성 재점검이 필요하다. 무한(Unbounded) 상태라면 목적함수 또는 제약의 경계 조건을 추가한다. 수렴하지 않으면 스케일링, 초기화, 알고리즘 선택이나 하이브리드 구성을 다시 검토한다.
Python으로 확인하는 접근 방식
전제조건: Python 3.10+, numpy 1.24+, scipy 1.11+, deap 1.3.1 설치 필요.
생산 믹스를 위한 LP(Simplex)
# env: python=3.10, numpy>=1.24, scipy>=1.11
import numpy as np
from scipy.optimize import linprog
# maximize 3x + 5y -> minimize -3x -5y
c = [-3, -5]
A = [[1, 0], [0, 2], [3, 2]] # <=
b = [4, 12, 18]
bounds = [(0, None), (0, None)]
# HiGHS Dual Simplex 사용(실제 Simplex)
res = linprog(c, A_ub=A, b_ub=b, bounds=bounds, method="highs-ds")
assert res.success, f"LP 실패: {res.message}"
print("최적값:", -res.fun, "해:", res.x, "shadow prices:", res.ineqlin.marginals)infeasible/unbounded 상황에서는 res.status를 확인하고 모델의 경계와 슬랙 변수를 다시 점검한다.
장벽 기반 trust-constr로 푸는 NLP(Interior Point)
# env: scipy>=1.11
import numpy as np
from scipy.optimize import minimize, NonlinearConstraint, Bounds
# Rosenbrock 변형: min f(x,y) = (1-x)^2 + 100(y - x^2)^2
def f(v): x,y = v; return (1-x)**2 + 100*(y - x**2)**2
# 제약: x*y >= 1 -> g(v) = x*y - 1 >= 0
def g(v): x,y = v; return x*y - 1
nlc = NonlinearConstraint(g, 0, np.inf)
bnds = Bounds([0.1, 0.1], [3.0, 3.0]) # 실내점 유도
x0 = np.array([0.5, 2.5])
res = minimize(f, x0, method="trust-constr", constraints=[nlc], bounds=bnds,
options=dict(verbose=0, maxiter=500))
assert res.success, f"NLP 실패: {res.message}"
print("최적값:", res.fun, "해:", res.x)trust-constr는 장벽 기반 내부점 접근법 구현이다. 비볼록 문제에서는 국소해가 나올 수 있으므로 다중 초기화 탐색을 권장한다. 대규모 또는 산업환경에서는 IPOPT 등 전문 솔버 사용을 검토한다.
페널티 제약을 넣은 GA
# env: deap==1.3.1, numpy>=1.24, random
import random, numpy as np
from deap import base, creator, tools
random.seed(42)
# 목적: f(x,y) 최소화, 제약: x+y >= 3
def obj(ind):
x, y = ind
f = (x-1)**2 + (y-2)**2
penalty = max(0.0, 3 - (x + y)) * 100.0
return (f + penalty,)
creator.create("FitnessMin", base.Fitness, weights=(-1.0,))
creator.create("Individual", list, fitness=creator.FitnessMin)
toolbox = base.Toolbox()
toolbox.register("attr_float", random.uniform, 0.0, 5.0)
toolbox.register("individual", tools.initRepeat, creator.Individual, toolbox.attr_float, 2)
toolbox.register("population", tools.initRepeat, list, toolbox.individual)
toolbox.register("evaluate", obj)
toolbox.register("mate", tools.cxBlend, alpha=0.5)
toolbox.register("mutate", tools.mutGaussian, mu=0, sigma=0.3, indpb=0.2)
toolbox.register("select", tools.selTournament, tournsize=3)
pop = toolbox.population(n=60)
NGEN, CXPB, MUTPB = 80, 0.7, 0.3
for gen in range(NGEN):
offspring = tools.selTournament(pop, len(pop), tournsize=3)
offspring = list(map(toolbox.clone, offspring))
for c1, c2 in zip(offspring[::2], offspring[1::2]):
if random.random() < CXPB:
toolbox.mate(c1, c2)
del c1.fitness.values, c2.fitness.values
for mut in offspring:
if random.random() < MUTPB:
toolbox.mutate(mut)
del mut.fitness.values
invalid = [ind for ind in offspring if not ind.fitness.valid]
fits = list(map(toolbox.evaluate, invalid))
for ind, fit in zip(invalid, fits):
ind.fitness.values = fit
pop[:] = tools.selBest(offspring + pop, k=len(pop))
best = tools.selBest(pop, 1)[0]
print("best:", best, "fitness:", obj(best)[0])패널티 설계는 성능을 좌우한다. repair 연산과 제약 우선 선택 규칙을 더하면 수렴 품질을 높일 수 있으며, 시드 고정은 재현성 확보에 도움이 된다.
비용·납기와 운영 표준화에 미치는 영향
도메인과 제약 강도에 따라 비용 절감 520%, 납기 준수율 310%p 향상을 기대할 수 있다. 프리솔브, 스케일링, 희소 선형대수를 적용하면 계산 시간은 1.5~5배 개선될 수 있다.
모델 기반 의사결정은 판단의 일관성과 투명성을 높이고, 시나리오 기반 리스크 대응에도 활용된다. 운영 프로세스를 표준화하고 지식을 자산화하는 효과도 있다.
운영에서 놓치기 쉬운 선택 기준
가능하면 LP 정식화를 먼저 시도하고, 불필요한 비선형 전환은 줄인다. 이산 변수는 MILP를 우선 검토한다. 스케일링과 단위 정규화는 수치 안정성의 기본 조건이다.
볼록 또는 선형 구조가 분명하면 Simplex와 Interior Point 같은 결정적 알고리즘을 우선 사용한다. 비미분·블랙박스·멀티모달 문제라면 GA 또는 GA+로컬서치 하이브리드를 적용한다.
민감도와 그라디언트를 제공할 수 있는 솔버를 선택하면 시나리오 분석을 자동화하기 쉽다. 배치와 온라인을 혼합해 운영할 때는 프리솔브 캐시와 웜스타트도 활용한다. 데이터 불확실성이 있으면 강건 또는 확률적 제약을 도입하고, 과적합을 막기 위해 규제항과 검증 시나리오를 다중화한다.