Hacker News 의견

• NP-완전 문제의 알고리즘 상한을 낮추는 것은 매우 흥미로운 일이지만, 실제 문제를 해결하는 데 있어 실행 시간을 개선하는 것과 직접적인 관련이 없을 수 있음.

  • 혼합 정수 프로그래밍(MIP) 솔버는 다양한 알고리즘과 휴리스틱을 사용함.
  • 휴리스틱과 전략의 라이브러리 구축은 MIP 솔버의 개선이 무어의 법칙을 뛰어넘는 이유임.
  • 1990년부터 2014년까지 하드웨어의 개선은 6500배였지만, 소프트웨어의 개선은 870000배의 성능 향상을 담당함.
  • 참조된 논문은 MIP 솔버의 지속적인 성능 향상에 있어 또 다른 퍼즐 조각이 될 수 있지만, 확실한 것은 아님.

• 새로운 알고리즘은 아직 실제 물류 문제를 해결하는 데 사용되지 않았음.

  • 오늘날의 프로그램을 업데이트하는 데 너무 많은 작업이 필요하기 때문임.
  • 그러나 Rothvoss에 따르면, 이는 기본적인 응용을 가진 문제에 대한 이론적 이해에 관한 것임.

• "Integer Linear Programming"이라는 제목은 정수 부분이 훨씬 더 중요하기 때문에 명시되어야 함.

  • 선형 프로그래밍에 대한 다항 시간 알고리즘은 수십 년 동안 알려져 왔지만, 정수 선형 프로그래밍은 NP-난해함.

• 소프트웨어 엔지니어들은 선형 프로그래밍에 대해 배워야 함.

  • 많은 문제들이 선형 최적화로 표현될 수 있음.
  • 예를 들어, 당구공을 삼각대에 올바른 시작 위치에 놓기 위한 평균 최소 교환 횟수에 대한 문제를 선형 프로그래밍을 사용하여 해결할 수 있음.

• 이 논문은 Space Groups를 직접적으로 살펴보지는 않지만, 문제 "공간"의 단순화를 일반화하는 데 사용될 수 있는지 여부를 살펴보는 것이 흥미로울 것임.

  • 저자는 건축가로서 수학자는 아니지만, 생성된 벌집을 통한 경로를 살펴보는 사람으로서 이 결과가 더 많은 조사가 필요함을 시사함.

• 여행하는 세일즈맨 문제에 대한 Sapolsky의 책 "Determined: A Science of Life without Free Will"에서 인용한 내용이 소프트웨어 개발자들에게는 관련이 없을 수도 있지만 여전히 매혹적임.

  • 개미는 음식을 찾아 여덟 곳을 확인하며, 이는 유명한 "여행하는 세일즈맨 문제"의 한 버전임.
  • 컴퓨터 과학자들은 "가상 개미"를 사용하여 이러한 문제를 해결할 수 있으며, 이는 이제 군집 지능으로 알려져 있음.

• 저자는 1985/86년에 스탠포드 대학에서 운영 연구를 공부하고 George Dantzig의 수업을 들었지만, 운영 연구가 아닌 소프트웨어 엔지니어가 되었음.

  • 선형 프로그래밍 알고리즘에 대해 많은 것이 배워졌다는 것을 보고 흥미로움을 느낌.

• 많은 이산 최적화 문제들이 선형 프로그램으로 변환될 수 있음.

  • SAT 솔버와 같은 매우 강력한 도구 세트임.

• 이론적 복잡성은 심플렉스보다 내부 점 방법이 LP에 대해 더 좋을 수 있지만, 현실에서는 잘 조정된 심플렉스가 거의 항상 승리함.