고급 LP 문제 해결

LP 기술의 성숙도에도 불구하고 일부 사용 사례에는 고급 기술이 필요합니다. 예를 들어 다양한 LP 알고리즘 및 구현을 사용할 수 있으며 각각 장단점이 있습니다. 또한 수치적 불안정성으로 인해 솔버가 속도가 느려지거나 특정 모델의 해결에 실패할 수 있습니다.

이 가이드에서는 LP 솔버의 성능과 안정성을 최대한 활용하는 데 도움이 되는 개념을 소개하고 예를 제공합니다.

개념

이 섹션에서는 LP 솔버의 고급 사용을 위한 주요 개념을 설명합니다. 독자가 LP의 이중성 개념에 익숙하다고 가정합니다.

LP 알고리즘의 제품군

다음 LP 알고리즘 클래스는 OR-Tools를 통해 액세스할 수 있습니다.

  1. 심플렉스 알고리즘은 최초의 실용적인 LP 알고리즘이며 여전히 가장 널리 사용됩니다. 알고리즘은 가능한 영역의 꼭짓점 (코너 포인트)을 따라 진행하며 최적의 솔루션에 도달할 때까지 목표 함수의 값을 반복적으로 개선합니다. 심플렉스 알고리즘에는 두 가지 유형이 있습니다.

    1. 기본 단순형은 기본 실행 가능 영역의 꼭짓점을 따라 단계를 따릅니다. 이 변형은 다양한 목표 함수, 즉 기본 실행 가능 영역이 고정된 일련의 LP 문제를 해결하는 데 특히 효과적입니다.
    2. 이중 심플렉스는 이중 가능한 영역의 꼭짓점을 따라 단계를 실행합니다. 이 변형은 이중 가능한 영역(예: 변수의 경계만 변경되는 경우)이 고정된 일련의 LP 문제를 해결하는 데 특히 효과적입니다. 이러한 이유로 이중 심플렉스는 MIP 솔버에서 광범위하게 사용됩니다.

  2. 배리어 또는 인테리어 포인트 메서드는 LP의 실용적인 알고리즘군입니다. 배리어 방법은 효율적 (다항식 시간) 수렴에 대한 이론적 보장과 실제로 안정적인 성능을 결합하는 방식입니다. 심플렉스 알고리즘은 성능이 낮을 때 심플렉스 알고리즘을 보완합니다. 예를 들어, 일부 솔버는 심플렉스와 배리어를 병렬로 실행하여 먼저 완료되는 알고리즘에서 솔루션을 반환합니다.

  3. 1차 메서드는 기울기 정보 (즉, 1차 미분)만 사용하여 반복을 안내하는 알고리즘 제품군입니다. 경사하강법은 잘 알려진 예입니다. 이러한 방법은 비선형 최적화와 머신러닝에서 널리 사용됩니다. LP의 경우 1차 메서드는 심플렉스 및 배리어보다 큰 문제로 확장할 수 있으며 메모리 요구사항도 훨씬 적을 수 있습니다. 반면 숫자 문제에 더 민감하며 매우 정확한 해결책을 얻는 데 어려움을 겪을 수 있습니다.

아래 표에는 OR-Tools에서 사용할 수 있는 LP 솔버가 나열되어 있으며 각 솔버에서 구현되는 세 가지 알고리즘 제품군이 나와 있습니다.

문제 해결사 심플렉스 Barrier 첫 번째 주문
클럽 X X
CPLEXL X X
글롭G X
GLPK X X
구로비L X X
PDLPG X
XpressL X X

G는 Google에서 개발한 솔버를 나타냅니다. L은 해결자에게 각 서드 파티 개발자가 발급한 라이선스가 필요함을 나타냅니다.

사용할 수 있는 솔버와 알고리즘에 대한 제안은 권장사항을 참조하세요.

해결이란 실제로 무엇을 의미할까요?

LP 문제 해결사를 최대한 활용하려면 문제 해결사가 LP 문제에 대한 해결책을 찾았다고 주장할 때 어떤 의미인지 이해하는 것이 중요합니다. 이 섹션에서는 특히 해의 숫자 부정확성 및 비고유성에 대해 이 질문에 답하는 데 필요한 기본사항을 설명합니다.

공차

LP 솔버는 거의 항상 부동 소수점 산술을 사용하므로 해가 숫자 부정확해질 수 있습니다. 이를 고려하고 이미 양호한 솔루션에 대한 노력을 방지하여 성능을 개선하기 위해, 솔루션가는 솔루션을 수락하고, 이러한 솔루션이 특정 허용 범위까지 조건을 충족할 때 문제를 해결했다고 주장합니다.

선형 프로그래밍 문제를 생각해 보세요.

$$ \begin{align*} \min\quad & -2x_1 - x_2 \\ \text{s.t.}\quad& x_1 + x_2 \le 1\\ & x_1, x_2 \ge 0 \end{align*} $$

해당 이중 문제와

$$ \begin{align*} \max\quad& y \\ \text{s.t.}\quad& -2 - y \ge 0\\ &-1 - y \ge 0 \\ &y \le 0 \end{align*} $$

이 문제 쌍은 $ x_1 = 1, x_2 = 0 $ 및 이중 해 $ y = -2 $라는 고유한 최적 원분법을 갖습니다. 문제 해결사가 최적으로 받아들일 수 있는 해는 무엇인가요? 이 문제를 해결하기 위해 다음과 같이 수량을 정의합니다.

  • 이중 격차는 기본 목표 값과 이중 목표 값 간의 차이입니다. 이 경우 $ |(-2x_1 - x_2) - y| $입니다.
  • 원시적 불가능성은 원천 제약 조건의 위반입니다. 이 경우에는 $ (\max\{ (x_1+x_2) - 1, 0 \}, \max\{-x_1, 0\}, \max\{-x_2, 0\}) $입니다.
  • 이중 불능은 이중 제약 조건의 위반입니다. 이 경우에는 $ (\max\{ 2 + y, 0 \}, \max\{ 1 + y, 0 \}, \max\{ y, 0 \}) $입니다.

이원성 격차, 원시 불능, 이중 불능이 주어진 허용 오차보다 작으면 문제 해결사가 최적으로 간주합니다.1

특히 공차의 적용은 해결자와 알고리즘에서 자연스러운 이유와 특이한 이유 모두에 따라 다릅니다. 예를 들어, 심플렉스 알고리즘의 이중성 격차는 숫자 부정확성에 의해서만 발생하는 반면, 원시 불능력과 이중 실현 가능성은 정확한 산술에서도 존재합니다. 일부 메서드는 $ x_1 \ge 0, x_2 \ge 0, $ 및 $ y \le 0 $보다 $ x_1 \ge 0, x_2 \ge 0, $ 및 $ y \le 0 $보다 크기 제약조건이 이중 제약 조건의 제약 조건의 영향을 직접적으로 받는 반면, 다른 방법은 구속 제약 조건의 위반을 $x_1 + x_2 \le 1$와 같은 선형 제약 조건 위반과 다르게 처리합니다. 즉, $ 해의 공차와 $ 해의 공차가 절대적입니다. 즉, $ 해

공차의 영향을 보여주는 예로, 위의 원시-이중 쌍에 적용된 절대 공차 $ \epsilon = \frac{1}{2} $ 을 고려해 보세요. 해 $ x_1 = 1.5, x_2 = 0, y = -3 $ 의 이중성 격차와 실행 불능이 모두 $ \epsilon $보다 작거나 같으므로 문제 해결사가 이 해를 '최적'으로 선언할 수 있습니다. 하지만 목표값 (-3)은 실제 최적 목표값인 -2와 1이 다릅니다. $ \epsilon $ 의 일반적인 기본값은 $10^{-6}$ 와 $10^{-8}$ 사이이므로 이러한 극단적인 예는 드물지만 불가능하지는 않습니다.

솔루션 유형

LP 문제에는 두 개 이상의 최적 솔루션이 있을 수 있으며 공차를 고려할 때는 더욱 그렇습니다. 위에 제시된 LP 알고리즘의 세 가지 계열에서 반환하는 솔루션의 속성을 간략하게 설명합니다.

심플렉스 알고리즘은 항상 가능한 영역의 꼭짓점 또는 꼭지점을 반환합니다. 이러한 솔루션은 희소한 경향이 있기 때문에 일부 상황에서 선호됩니다.

배리어와 1차 메서드는 일반적으로 꼭짓점을 반환하지 않습니다. (이론에 이 가이드의 범위를 벗어나는 추가적인 특성 지정이 제공됩니다.)

과거 이유와 꼭짓점 솔루션은 매력적인 특성을 지니고 있기 때문에, 문제 해결사는 기본적으로 크로스오버 절차를 적용하여 배리어 알고리즘에서 찾은 솔루션에서 최적의 꼭짓점으로 이동하는 경우가 많습니다. 현재 1차 메서드로 찾은 솔루션에는 크로스오버가 제공되지 않습니다.

권장사항

LP 솔버의 고급 사용을 위한 권장사항은 다음과 같습니다.

문제 데이터의 확장

숫자 문제로 인해 솔버의 수렴 또는 모델 실패가 느릴 수 있습니다. 이러한 문제는 여러 가지 이유로 발생할 수 있습니다. 예를 들면 다음과 같습니다.

매우 작거나 큰 숫자 상수가 LP 모델에 나타나는 경우가 일반적입니다. 위의 예를 확장하여 \(x_1\) 및 \(x_2\) 이 '제공업체 1' 또는 '제공업체 2'에 할당된 고객의 비율을 나타내고, 이러한 고객에게 서비스를 제공함으로써 얻는 이익을 극대화하려면 다음과 같은 목표 함수를 작성할 수 있습니다.

$$ \min -c_1x_1 - c_2x_2 $$

각 항목의 의미는 다음과 같습니다.

  • $ c_1 $ 는 고객을 제공업체 1에 할당할 때의 이점입니다.
  • $ c_2 $ 는 고객을 제공업체 2에 할당할 때의 이점입니다.

다음 제약조건을 충족하는 이중은 절대 공차 $ \epsilon $로 실행할 수 있는 것으로 간주됩니다.

  • $ y \le -c_1 + \epsilon $,
  • $ y \le -c_2 + \epsilon $입니다.

$ c_1 $ 및 $ c_2 $ 의 이점 단위가 $ \epsilon $와 동일한 척도에 있는 작은 분수 값일 경우, 이중 타당성 조건이 다소 약해지므로, 매우 차선인 원초가 최적으로 선언될 수 있습니다.

반면 혜택 단위가 '마이크로달러'(1,000,000마이크로달러 = 1달러)인 경우 결과로 생성되는 매우 큰 절댓값은 해의 정밀도가 매우 높아야 하며, 부동 소수점 수의 제한을 감안하면 불리하게 높은 정밀도를 얻을 수 있습니다. 문제가 이런 식으로 공식화되면 솔버가 수렴에 실패할 수 있습니다. 잘 준비된 문제를 작성할 때 고급 모델러는 문제 데이터가 솔버의 공차와 일치하는 방식으로 확장되는지를 고려해야 합니다.

숫자 오류를 방지하는 것 외에도 성능 향상을 위해 허용 오차를 조정할 수도 있습니다. 심플렉스 메서드와 배리어 메서드는 허용 오차에 너무 민감하지 않지만, 해법의 끝에서 진행이 지연되는 것으로 관찰되면 더 큰 공차를 사용하면 도움이 될 수 있습니다. 반면에 1차 메서드는 일반적으로 훨씬 더 민감합니다. 1차 메서드 사용자는 컨텍스트에서 허용하는 대로 허용 오차를 완화하여 더 빠른 솔루션의 이점을 얻을 수 있습니다.

Glop의 허용 오차는 GlopParameters의 primal_feasibility_tolerance, dual_feasibility_tolerance, solution_feasibility_tolerance를 참조하세요. primal_feasibility_tolerance 및 dual_feasibility_tolerance는 알고리즘 내에서 사용되고 solution_feasibility_tolerance는 해결 후 확인되어 숫자 문제를 플래그합니다. PDLP의 경우 eps_optimal_absolute 및 eps_optimal_relative를 참고하세요.

이러한 문제 유형에 관한 자세한 내용은 Gurobi의 숫자 문제 가이드라인을 참고하세요. 이 가이드라인은 Gurobi 사용자를 대상으로 작성되었지만 많은 원칙이 일반적으로 적용됩니다.

문제 해결사 및 알고리즘 선택

먼저 솔버와 알고리즘 선택이 미치는 영향이 얼마나 큰지 예시로 시작한 다음 LP 솔버를 선택하기 위한 가이드를 제시합니다.

실제 가변성

한스 미텔만이 LP 솔버를 벤치마킹하기 위해 사용한 일부 인스턴스의 해결 시간을 비교하여 LP 알고리즘과 솔버 전반에서 성능의 변동성을 설명합니다. 이러한 인스턴스는 상대적인 성능의 극한을 보여주도록 명시적으로 선택되었으며, 일반적인 동작을 꼭 나타낼 수도 없습니다.

Glop의 원시 및 이중 심플렉스 메서드는 Gurobi의 배리어 방법(정점 솔루션을 찾는 크로스오버 유무와 관계없음) 및 1차 메서드인 PDLP와 높은 정밀도에서 낮은 정밀도를 보여줍니다. 아래 보고서는 초 단위의 시간을 계산하며, 한도는 20분 (1,200초)입니다.

인스턴스 글롭
프라이멀 심플렉스		 Glop
이중 심플렉스		 구로비 배리어
(크로스오버 포함)		 Gurobi Barrier
크로스오버 없음		 PDLP
높은 정밀도		 PDLP
낮은 정밀도
ex10 >1200 >1200 79.7 63.5 8.2 2.7
너그08-3위 >1200 252.8 1,446만 3.2 1.1 0.9
savsched1 >1200 >1200 156.0 22.6 46.4 32.4
wide15 >1200 2,080 >1200 >1200 916.4 56.3
에너지 건축 자재 178.4 267.5 12.8 12.3 >1200 157.2
S250R10 12.1 520.6 15.2 16.4 >1200 >1200
Solver 버전 OR-도구 9.3 OR-도구 9.3 구로비 9.0 구로비 9.0 OR-도구 9.3 OR-도구 9.3
solver_specific_parameters (기본값) use_dual_simplex: true Method 2, Threads 1 Method 2, Crossover 0, Threads 1 termination_criteria { eps_optimal_absolute: 1e-8 eps_optimal_relative: 1e-8 } termination_criteria { eps_optimal_absolute: 1e-4 eps_optimal_relative: 1e-4 }

이러한 결과에서 다음과 같은 결론을 내립니다.

  • 알고리즘과 솔버의 상대적 성능은 단일 인스턴스에서 자릿수에 따라 달라질 수 있습니다.
  • 어떤 알고리즘과 문제 해결사도 다른 알고리즘과 솔버보다 모두 똑같지는 않습니다.
  • 크로스오버 (기본적으로 사용 설정됨)는 해결 시간을 상당히 증가시키며,
  • PDLP는 낮은 정밀도를 높은 정밀도보다 10배 빠르게 해결할 수 있습니다.

LP 해결사 선택을 위한 간단한 가이드

가장 적합한 단일 LP 알고리즘이나 솔버가 없다는 점을 감안할 때 다음 단계에 따라 사용 사례에 가장 적합한 방법을 찾는 것이 좋습니다. 첫 번째 단계부터 시작하고 성능이 충분하지 않은 경우 다음 단계로 진행합니다.

  1. Glop를 사용해 보세요. 이유: Glop는 기본 및 이중 심플렉스 메서드를 Google 내부에서 구현한 것입니다. Glop은 오픈소스이며 Google의 프로덕션 워크로드에 신뢰할 수 있습니다.
    • 기본 구성 (기본 단플렉스)이 제대로 작동하지 않으면 use_dual_simplex: true를 사용하여 이중 심플렉스로 전환해 보세요.
  2. 라이선스를 사용할 수 있는 경우 상업용 솔버 (CPLEX, Gurobi, Xpress)를 사용해 보세요. 심플렉스 메서드와 배리어 방법을 실험합니다. 이유: 이러한 솔버는 업계 표준이며 고도로 최적화되어 있습니다. 또한 배리어 메서드는 Glop에서 제공하는 심플렉스 알고리즘을 보완합니다.
    • 배리어를 사용하는 경우 꼭짓점 솔루션이 필요하지 않으면 '크로스오버'를 중지합니다.
  3. PDLP를 사용해 보세요. 애플리케이션에 맞게 수렴 허용 범위를 조정합니다. 이유: PDLP는 심플렉스 메서드와 배리어 메서드가 메모리 제한에 도달하거나 속도가 너무 느려지는 최대 규모의 문제에 맞게 설계되었습니다. PDLP는 정확하지만 느린 솔루션보다 근사하지만 빠른 솔루션이 선호되는 경우 가장 잘 작동합니다.
  4. 여기까지 왔다면 이제 고급 LP 사용자입니다. 추가 도움말은 OR-Tools 지원 옵션을 참고하세요.

  1. 이보다 더 복잡한 경우가 많습니다. 문제 해결자는 일반적으로 해결됨 문제라고 하는 변환/간소화된 버전의 문제에서 이러한 조건을 확인합니다. 경우에 따라 해결된 문제에 대한 해결책이 입력 문제의 해결책과 멀리 떨어져 있을 수도 있습니다. 이 상황으로 인해 CPLEX의 OptimalInfeas 또는 Glop의 IMPRECISE과 같은 비정상적인 상태가 발생할 수 있습니다.↩