지난 50년간의 정수 선형 프로그래밍: 최근 실용적 진보 — Anubis 보호 페이지 표시

 (inria.hal.science)
1P by GN⁺ | ★ favorite | 댓글 1개
  • 논문 본문 대신 Anubis 봇 확인 페이지가 표시되어, 해당 URL에서는 실제 논문 내용을 바로 확인할 수 없음
  • 보호 페이지는 AI 회사들의 공격적 웹 스크래핑이 서버 다운타임과 리소스 접근 차단으로 이어질 수 있다고 안내함
  • Anubis는 Hashcash와 유사한 작업 증명을 요구해, 개인 사용자는 부담이 작지만 대량 스크래핑에는 누적 비용이 커지도록 설계됨
  • 이 방식은 임시 해법이며, 장기적으로는 폰트 렌더링 같은 단서로 헤드리스 브라우저를 식별하는 데 초점이 있음
  • 최신 JavaScript 기능이 필요하므로 JShelter 같은 플러그인이 켜져 있으면 해당 도메인에서 비활성화해야 접근이 가능함

Anubis 보호 페이지가 표시됨

  • 페이지 제목은 “Making sure you're not a bot!”이며, 화면에는 계산 중 상태가 나타남
    • 난이도는 4
    • 속도는 0kH/s
  • 서버 관리자가 AI 회사들의 공격적 스크래핑으로부터 서버를 보호하기 위해 Anubis를 설정해 이 페이지가 노출됨
  • 대량 스크래핑은 웹사이트 다운타임을 유발할 수 있고, 그 결과 모든 사용자가 리소스에 접근하지 못할 수 있음

작업 증명 방식과 접근 제약

  • Anubis는 Hashcash 계열의 작업 증명 방식을 사용함
    • 개별 사용자에게 생기는 추가 부하는 무시할 만한 수준임
    • 대량 스크래퍼는 누적 비용이 커져 스크래핑 비용이 높아짐
  • 현재 방식은 임시 해법에 가까움
    • 목표는 폰트 렌더링 방식 같은 단서로 헤드리스 브라우저를 식별할 시간을 확보하는 것임
    • 합법적 사용자일 가능성이 높은 경우에는 작업 증명 페이지를 보이지 않게 하는 방향임
  • Anubis는 최신 JavaScript 기능을 요구함
    • JShelter 같은 플러그인이 필요한 기능을 비활성화할 수 있음
    • 이 도메인에서는 JShelter 또는 유사 플러그인을 꺼야 함

함께 보면 좋은 글 β

GN⁺   [-]
Hacker News 의견들

  • 상용 정수 선형계획법(ILP) 솔버가 Gurobi처럼 무료/오픈소스보다 훨씬 나은 이유를 큰 그림으로 알고 싶음
    ILP가 본질적으로 너무 어려운 문제라서, 최고의 솔버들이 특정 하위 문제용 휴리스틱을 대규모로 모아둔 형태이고 공개 영역에는 일반적으로 좋은 전략이 아직 없는 건지 궁금함

    • 주된 이유는 고객과 아주 밀접하게 협업하면서 문제별 속도 개선을 구현해 왔기 때문임. 그리고 이걸 10~20년 동안 해왔음
      혼합정수 선형계획법(MILP)에서는 분기한정법의 좋은 시작점을 찾고 트리를 효과적으로 가지치기하는 휴리스틱, 그리고 분수해를 잘라내 목적값과 정수성을 개선하는 맞춤 절단평면이 중요함
      운영연구 연구자들이 특정 문제를 잡으면 직접 절단평면과 휴리스틱을 작성해 Gurobi 같은 범용 솔버를 꽤 쉽게 이기기도 함. 솔버 회사들은 박사와 연구자 팀을 고용해 이 작업을 꾸준히 하고, 고객 문제 묶음으로 개선과 회귀를 추적함
    • 대형 상용 솔버들은 실제 문제에 맞춰 풀이 과정의 모든 것을 조정하는 데 많은 시간을 투자할 자원과 협력 고객이 있음. 휴리스틱도 그 일부이고, 더 단순한 하위 문제나 근사를 인식해 전체 문제에 다시 반영하는 것도 포함됨
      오픈소스 솔버는 몇 가지가 겹쳐 발목이 잡히는 듯함. 최신 최적화 개발의 진입 장벽이 매우 높아 수학과 프로그래밍 양쪽에 의미 있게 기여할 수 있는 연구자/개발자가 애초에 적고, 그런 능력이 있으면 돈이 되는 경로가 오픈소스 기여에서 멀어지게 만들며, 오픈소스 프로젝트 특성상 “고객”이 솔버 개선에 필요한 예제, 성능 데이터, 프로파일링을 되돌려줄 가능성이 낮음
      예외도 있지만, 전통적인 상용 솔버 개발 밖에 있다고 해서 곧 오픈소스인 건 아님. 예를 들어 Stanford에서 개발된 SNOPT도 여전히 상용 라이선스임. 학계 솔버 작업은 Clarabel처럼 특정 응용 맥락에서 이뤄지는 경우가 많아 문제군이 좁아지는 경향이 있음
      다른 분야는 대형 기술 회사가 기존 상용 프로젝트를 인수하거나, 경쟁사를 견제하기 위해 오픈소스 프로젝트에 자금을 대면서 병목을 넘기도 했음. 솔버에도 Ceres 같은 좁은 예는 있지만, 범용 솔버 스택 전체를 처음부터 개발하는 투자는 너무 크다고 여겨졌을 가능성이 큼
    • 상용 솔버는 방대한 기법 모음과, 현재 문제에 어떤 기법이 도움이 될지 감지하는 좋은 패턴 탐지 메커니즘을 갖고 있음
      문제 구조를 알고 있으면 그걸 활용해 상용 솔버 성능을 넘어설 수도 있음. 하지만 임의의 문제라면 가능성이 거의 없음
    • “솔버가 특정 하위 문제용 휴리스틱의 큰 앙상블”이라는 말은 ILP처럼 SAT와 동등한 NP-난해 문제라면 거의 자명하게 적용되는 것 아닌가 싶음
    • 핵심은 규모와 속도임. 예를 들어 대부분의 퀀트 트레이딩 회사는 가능한 한 자주 거대한 최적화를 돌림. 오픈소스 솔버는 이런 문제를 아예 풀지 못하는 경우도 많음. 메모리 부족 예외 같은 식임

  • IBM의 “ILOG” 혼합정수 선형계획법 라이브러리로 자원 배분 도구를 만들었던 기억이 어렴풋함. 우리가 5분 안에 풀던 같은 문제를 20년 전에 만들었다면 아직도 실행 중이었을 거라는 걸 깨달았음
    순수 컴퓨팅 성능이 약 1000배 늘고, 알고리즘도 비슷한 정도로 개선되어 총 백만 배 정도 좋아졌던 것으로 기억함
    미래를 예측할 때 곱씹어볼 만함. 참고로 그 “자원”은 다이아몬드였음

  • 실제로 이런 게 어떻게 쓰이는지 궁금함. 수치 최적화를 구현하면 데이터 기반 접근에서 흔한 문제들, 예를 들어 신뢰와 나쁜 데이터 때문에 자주 실패하고, 결국 중요한 누군가가 감으로 어떻게 할지 정하는 그림이 떠오름

    • 직장에서는 스택 전반에서 솔버를 씀. 가정의 배터리와 전기차를 최적으로 스케줄링하는 솔버, 그런 집 수십만 곳을 포트폴리오로 최적 스케줄링하는 솔버, 그 포트폴리오를 최적으로 거래하는 솔버가 있음
      EU 전력 현물 가격은 매일 하나의 거대한 솔버 실행으로 정해짐. Euphemia를 찾아보면 작동 방식에 대한 글들이 있음
      최적화할 명확한 목표가 있고 실제 돈이 걸린 분야 대부분은 솔버로 가득 차 있음
    • FMCG 회사에서는 실제로 이런 용도로 씀. 영업사원과 배송 이동 계획, 생산을 위한 기계·인력·자재 자원 스케줄링, 창고 물류센터의 재고 수준 최적화가 있음
      재고 쪽은 수요 예측이 어려워 완전 자동화되지는 않았음
    • 사례 연구를 읽어보면 됨
      Gurobi 사례 연구: https://www.gurobi.com/case_studies/
      CPLEX 사례 연구 일부: https://www.ibm.com/products/ilog-cplex-optimization-studio/...
      Hexaly, 예전 LocalSolver, 사례 연구: https://www.hexaly.com/customers

  • Gurobi가 꽤 비싸다고 들었음. 가격 정보를 공유할 수 있는 사람이 있는지 궁금함

    • 가격 정보는 기밀이라 공유할 수 없지만, 그냥 MIP를 가지고 놀고 싶은 거라면 매우 비싼 3대 솔버인 XPRESS, Gurobi, CPLEX를 살 필요는 없음. 보통 학생에게는 무료로 제공됨
      오픈소스이거나 비상업적 용도 무료인 괜찮은 MIP 솔버가 최소 두 개 있음
      https://highs.dev/
      https://www.scipopt.org/
    • 들은 바로는, 물론 확인할 수는 없지만, 가격 등급이 사실상 “문의하세요” 하나뿐이고 그때 얼마나 돈을 버는지 파악한 뒤 일부를 요구하는 방식이라고 함
    • 왜 그렇게 깊이 감춰진 비밀이라고 생각하는지 모르겠음. 코어 제한 라이선스 기준으로 좌석당 대략 1만 달러임
    • 느리게 잘못된 결정을 내리는 것보다 훨씬 쌈. GLPK 같은 무료 솔버는 작은 문제에는 괜찮지만, 많은 비즈니스 문제는 프리미엄 솔버에 돈을 내지 않으면 필요한 시간 안에 거의 풀 수 없음. Gurobi가 그중 최고임
    • 약 10년 전에 마지막으로 확인했을 때, 여러 사용자가 서버에서 쓰는 전체 라이선스가 약 10만 달러였음. 정확한 좌석 수나 서버 수 제한은 기억나지 않음
      업계의 많은 사람에게는 충분히 그 값을 한다고 덧붙이고 싶음

  • 1990년대에 학습용으로 Maple에서 Gomory 절단 초평면의 어떤 버전을 구현했던 기억이 남. 실사용용은 아니었음. 분야가 많이 발전한 듯함
    “1990년대 초 LP를 푸는 데 실행 시간이 두 달 필요했다면 오늘날에는 1초도 걸리지 않는다. 최근 Bixby는 1990년부터 2020년까지 CPLEX와 Gurobi라는 두 MILP 솔버의 기계 독립적 성능을 비교해 거의 4×10^6배의 속도 향상을 보고했다”

  • 이런 문제에 기계학습/인공지능 기반 접근이 꽤 부족한 느낌임. 작은 문제를 풀려는 강화학습/그래프 신경망 논문 사례는 많이 봤지만, 결국 Gurobi 라이선스를 사서 돌리는 게 최선처럼 보일 때가 많음
    최근 작업장 스케줄링에 가까운 스케줄링 최적화를 해왔는데, 강화학습을 쓰는 예시가 있긴 해도 충분하지 않아 보임. 큰 문제에서 그럴듯한 해를 얻으려고 진화 알고리즘에 의존하게 됐음
    문제를 잘 정식화할 수 있으면 운영연구식 접근을 쓰는 편이 항상 더 효율적인지도 모르겠음

    • 문제에 따라 다름. 보안 제약 단위 기동 문제는 어떤 발전소를 언제 켤지 결정하는 문제인데, 믿기 어려울 정도로 복잡하지만 Gurobi 같은 MILP 솔버는 MIP 간격 범위 안에서 전역 최적해를 빠르게 찾을 수 있음
      유전 알고리즘을 만들 수도 있겠지만, 국소 최솟값에 갇히지 않은 답을 준다는 보장이 없음. 빠르게 실행되게 만들 수 있다는 가정도 필요함. 신경망도 역시 최적보다 못할 것임
    • SAT는 표준적인 상징적 인공지능(GOFAI) 문제이고, 당연히 기계학습 계열 프로그래밍 언어로 SAT 솔버를 작성할 수도 있음. 그런 의미에서 기계학습/인공지능 접근은 꽤 적용 가능하다고 봄

  • “1988년부터 2004년까지 하드웨어는 1600배 빨라졌고, LP 솔버는 3300배 빨라져 누적 속도 향상 계수가 5 × 10^6을 넘었다. 그것도 이미 20년 전이다!”
    “저자들은 2001년부터 2020년 사이 상용 MILP 솔버에서 1000배 속도 향상을 관찰했다. 그중 50배는 알고리즘, 20배는 더 빠른 컴퓨터 덕분이다”
    컴퓨팅 하위 분야별로 이런 속도 향상 계수를 모으고, 알고리즘 개선과 더 빠른 컴퓨터의 기여로 분해해볼 수 있을지 궁금함
    컴파일러에는 “Proebsting의 법칙”이 있음. 컴파일러 발전은 18년마다 컴퓨팅 성능을 두 배로 만든다는 법칙임

  • 제목에 [pdf] [2024] 를 붙이면 좋겠음

답변달기