연구자들, 정수 선형 프로그래밍을 더 빠르게 처리하는 방법 발견

• 생산 계획·승무원 배치·차량 경로처럼 정수 단위 결정이 필요한 최적화 문제에서, Victor Reis와 Thomas Rothvoss가 ILP 실행 시간을 크게 줄이는 새 알고리듬을 제시함
• ILP는 일반 선형 프로그래밍보다 까다롭고, 1980년대 이후에는 기록적인 개선이 거의 없었기 때문에 이번 결과가 수십 년 만의 큰 진전으로 받아들여짐
• 새 접근은 격자와 볼록체의 교차를 다루는 기하학적 도구를 결합해 가능한 정수 해의 범위를 더 강하게 좁힘
• 핵심은 2016년 격자점 관련 결과를 활용해 covering radius의 상한을 낮춘 데 있으며, 실행 시간은 ((\log n)^{O(n)}) 수준까지 줄어듦
• 아직 실제 물류 시스템에 바로 적용된 것은 아니지만, ILP의 이론적 속도 한계에 거의 근접한 결과로 실무 솔버 개선의 장기적 방향을 보여줌

---

정수 제약이 최적화를 어렵게 만드는 이유

• 여행하는 세일즈맨 문제는 여러 도시를 지나는 최단 경로를 찾는 오래된 계산 문제이며, 가능한 경로를 모두 확인하면 도시 수가 조금만 늘어도 감당하기 어려움
• 선형 프로그래밍은 방정식과 부등식으로 가능한 조합을 체계적으로 다루는 수학적 모델임
• 현실의 최적화 문제에서는 소수점 답이 쓸모없는 경우가 많음
  • 공장 최적화 계획에서 500.7개의 소파를 생산하라는 답은 실제 결정으로 쓰기 어려움
• 정수 선형 프로그래밍(ILP) 은 이런 정수 제약이 있는 선형 프로그래밍 변형이며, 생산 계획, 항공사 승무원 일정, 차량 경로 지정 같은 이산적 결정 문제에 널리 쓰임
• Santosh Vempala는 ILP를 이론과 실무 양쪽의 운영 연구에서 핵심 도구로 봄

1980년대 이후 느리게 개선된 속도 한계

• ILP는 60여 년 전 정식화된 뒤 여러 알고리듬이 나왔지만, 필요한 단계 수 기준으로는 여전히 느린 편이었음
• 가장 단순한 기준점은 변수가 0 또는 1만 가질 수 있는 이진 변수 경우임
  • 변수 1개는 가능한 조합 2개
  • 변수 2개는 4개
  • 변수 3개는 8개
  • 일반적으로 실행 시간은 변수 수, 즉 차원에 대해 지수적으로 증가함
• 변수가 0과 1을 넘어 더 넓은 정수 값을 가질 수 있으면 실행 시간이 훨씬 더 길어짐
• 연구자들은 일반 ILP를 이 단순한 이진 경우의 속도에 더 가깝게 만들 수 있는지 오랫동안 탐구해 왔음
• 1980년대 기록 이후에는 점진적 개선만 이어짐

Lenstra가 연 기하학적 해석

• 1983년 Hendrik Lenstra는 일반 ILP 문제가 풀 수 있음을 증명하고, 이를 위한 첫 알고리듬을 제시함
• Lenstra는 ILP를 기하학적 문제로 바꿔 다룸
  • ILP의 부등식은 볼록한 도형, 즉 볼록체(convex body) 로 표현됨
  • 도형 내부는 부등식을 만족할 수 있는 모든 가능한 값에 대응함
  • 변수 2개 문제는 평면 다각형, 변수 3개 문제는 3차원 입체처럼 차원이 늘어남
• 모든 정수는 수학적으로 격자(lattice) 의 점으로 볼 수 있음
  • 2차원에서는 점들의 바다처럼 보임
  • 3차원에서는 건물 철골이 만나는 지점 같은 구조가 됨
• 결국 ILP를 푸는 일은 볼록체와 격자의 교차, 즉 가능한 해가 정수점과 만나는 위치를 찾는 문제가 됨
• Lenstra의 알고리듬은 이 공간을 탐색할 수 있었지만, 효율을 위해 문제를 더 낮은 차원의 조각으로 나눠야 하는 경우가 있었고 이 과정이 실행 시간을 늘림

covering radius가 만든 30년 병목

• 1988년 Ravi Kannan과 László Lovász는 오류 정정 코드 연구에서 가져온 covering radius 개념으로 볼록체와 격자의 교차를 더 효율적으로 다루려 함
• covering radius는 볼록체를 격자 위 어디에 놓아도 적어도 하나의 정수점을 포함하도록 보장하는 크기와 관련됨
• 이 값의 크기가 ILP 문제를 얼마나 효율적으로 풀 수 있는지를 좌우함
• 이상적인 covering radius의 크기를 알아내는 일 자체가 어려운 문제였음
• Kannan과 Lovász는 가능한 값을 상한과 하한으로 좁혔고, 상한이 차원에 대해 선형적으로 커진다는 것을 보임
• 이 결과만으로는 ILP 실행 시간을 크게 줄이기에 부족했고, 이후 30년 동안 개선 폭은 제한적이었음

Reis와 Rothvoss의 새 알고리듬

• Victor Reis와 Thomas Rothvoss는 격자에 초점을 둔 별도의 수학 결과를 활용해 돌파구를 만듦
• 2016년 Oded Regev와 Noah Stephens-Davidowitz는 특정 도형 안에 격자점이 얼마나 들어갈 수 있는지를 보임
• Reis와 Rothvoss는 이 결과를 다른 도형들에 적용해 ILP의 covering radius 안에 포함되는 격자점 수를 더 잘 추정함
• 이 추정으로 상한이 낮아졌고, 전체 ILP 알고리듬 실행 시간이 크게 줄어듦
• 새 실행 시간은 ((\log n)^{O(n)})이며, 여기서 (n)은 변수 수이고 (O(n))은 (n)에 선형적으로 비례함
• 이 표현은 이진 변수 문제의 실행 시간과 “거의” 같은 수준으로 간주됨

이론적 성과와 실제 적용의 거리

• Noah Stephens-Davidowitz는 새 알고리듬을 거의 40년 만의 첫 주요 ILP 솔버 개선으로 봄
• Daniel Dadush는 이 결과를 수학, 컴퓨터 과학, 기하학의 교차점에서 나온 성과로 평가함
• 새 알고리듬은 아직 실제 물류 문제를 푸는 데 사용되지 않았음
  • 현재 프로그램을 이 방식에 맞게 업데이트하려면 많은 작업이 필요함
• Rothvoss는 이번 결과의 초점이 근본적 응용을 가진 문제에 대한 이론적 이해에 있다고 봄
• ILP 계산 효율이 더 좋아질 가능성은 남아 있지만, Vempala는 이상적 실행 시간에 더 가까워지려면 근본적으로 새로운 아이디어가 필요하다고 봄

[GN⁺]

Hacker News 의견들

• 핵심 NP-완전 문제의 알고리즘 상한을 낮추는 건 언제나 매우 흥미롭지만, 그 문제가 실제 구현에서 더 빨리 풀린다는 뜻은 아닐 수 있음
  혼합 정수 계획법(MIP) 솔버는 많은 알고리즘과 대량의 휴리스틱을 함께 쓰며, 휴리스틱과 전략 라이브러리를 쌓아온 것이 MIP 솔버 개선이 Moore의 법칙을 앞질러 온 핵심 이유임
  https://www.math.uwaterloo.ca/~hwolkowi/henry/teaching/f16/6...에 따르면 1990~2014년 하드웨어 개선은 6500배였지만, 소프트웨어 개선은 870000배 성능 향상에 기여했음
  이 논문도 MIP 솔버 성능 향상을 이어갈 퍼즐 조각이 될 수는 있지만, 그렇게 된다고 보장되지는 않음

• 새 알고리즘이 아직 물류 문제 풀이에 쓰이지 않은 이유가 “오늘날 프로그램을 업데이트하는 데 너무 많은 작업이 필요해서”라는 설명이 잘 이해되지 않음
  대부분의 도메인별 모델은 큰 문제에서는 Gurobi, CPLEX, FICO 솔버를 호출하고, 작은 문제에서는 SCIP 같은 오픈소스 솔버를 씀
  표준 MPS 형식으로 이들 솔버 사이에서 모델을 교환할 수 있고, 문제 정식화는 바뀌지 않으며 솔버 내부의 풀이 방식만 바뀌면 되는 것 아닌가 싶음
  새 구현이 필요하다는 뜻이라면, 구현했을 때 세상이 얻을 이익도 엄청날 것 같음

  • Reis & Rothvoss의 새 알고리즘은 Gurobi, CPlex 등의 핵심 알고리즘을 대체해야 할 가능성이 큼
    이 도구들은 수십 년간의 점진적 개선이 쌓인 매우 복잡한 공학적 산물이라, 새 발견을 이런 엔진에 통합하는 방법을 알아내는 데만도 상당한 연구 노력이 필요할 듯함
  • 문제 정식화와 문제 풀이를 혼동하는 듯함
    MPS 같은 형식으로 문제 정식화를 교환하는 표준 방식이 있는 건 맞고, 요즘은 AMPL 같은 대수적 모델링 언어가 더 많이 쓰이는 것 같지만, 그런 형식이 주는 건 표준 수학적 정식화뿐임
    실제 풀이는 각 솔버에 매우 특화되어 있고, 저마다의 자료구조, 알고리즘, 휴리스틱 기법이 있음
    이들은 서로 교체 가능하지도 않고, 의도적으로 공개되어 있지도 않으며, 솔버 코드와 전체 과정에 대한 지식 없이 외부 숫자 몇 개를 중간에 끼워 넣을 수는 없음
  • “현재 솔버에 통합하기가 이 연구의 어떤 부분 때문에 특히 어려운지 모르겠다”는 뜻으로 읽히는데, 일부는 “왜 그냥 기존 솔버에 통합하지 않았나, 쉬울 텐데 저자들이 게으르다”는 식으로 받아들이는 듯함
    오해를 풀고 싶었음
  • 오픈소스 솔버들은 30년 동안 박사과정 학생들이 랜덤하게 기여한 코드가 뒤섞인 상태라, 작동하는 것 자체가 놀라울 정도임
    가능하면 그런 것들로 직접 구현하는 일은 피하게 됨
  • Reis & Rothvoss가 논문 끝에서 제시한 무작위 알고리즘은 Gurobi/CPLEX/XPRESS에 구현되지 않을 것임
    그래도 훌륭한 결과라는 점은 변하지 않음
    이론적 계산 복잡도 관점에서 “정수 선형 계획법” [2]의 최고 알고리즘들은 격자에 기반하며, 최악 경우 큰 O 복잡도가 가장 좋음
    하지만 현재 구현들은 대개 (1) gmplib [3] 같은 임의 크기 유리수 연산이 필요해 메모리를 많이 먹고 실제로도 느리며, (2) LLL류 격자 축소 단계 [4]가 필요하지만 행렬 희소성을 활용하지 못함
    그 결과 이런 알고리즘은 보통 메모리에 들어가지 않아 1000x1000보다 큰 행렬 문제는 시작조차 못 하고, 설령 들어가도 지나치게 느림
    실무의 정수 계획법 솔버는 대신 SAT 풀이에 쓰이는 것과 비슷한 되추적 알고리즘인 분기 한정법에 기반하고, 각 반복마다 원래 문제에서 모든 변수를 연속 변수로 바꾼 “선형 계획법” 문제를 풂
    각 선형 계획법 문제는 내부점 방법 같은 다항 시간 알고리즘으로 풀 수 있지만, 실제로는 최악 경우 지수 시간인 단체법을 씀
    이유는 풀어야 하는 선형 계획법 문제들이 서로 매우 비슷해서, 단체법이 실전에서 그 점을 잘 활용하기 때문임
    또한 관련 알고리즘들은 벡터와 행렬의 희소성을 크게 활용함
    그래서 어떤 사람들은 변수 수가 수백만 개인 정수 계획법 문제도 며칠, 심지어 몇 시간 안에 풀기도 함
    솔버 구현자들은 절대적으로 가장 좋은 이론 복잡도를 좇고 있지 않으며, 이산 최적화의 이론과 실무가 어느 정도 갈라졌다고 볼 수 있음
    그렇다 해도 Reis & Rothvoss 논문 [1]은 깊은 수학적 작업이고, 이산수학에 관심 있는 사람에게는 그 자체로 매우 인상적임
    Dadush의 10년 된 추측을 해결했으며, 작년 11월 컴퓨터과학 이론의 양대 최고 학회 중 하나인 FOCS에서 발표됐음
    직접적인 실용성은 핵심이 아니고, 저자들도 비공식 자리에서는 그렇게 인정할 것임
    물론 연구비 신청서에서는 다르게 말하겠지만, 그건 게임의 일부임
    쓸모없다는 뜻은 아니며, 수학적 지식을 진전시킨다는 점만으로도 큰 가치가 있고, 몇 세대 뒤 연구자들이 이 아이디어를 바탕으로 실용 알고리즘을 만들어 솔버의 최첨단을 밀어 올릴 수도 있음
    결국 이 알고리즘들은 최악 경우 모두 지수 시간임
    이론에서는 최악 경우 복잡도의 지수부에 있는 다항식을 조금 줄이려 하겠지만, 실무자는 보통 크기 n이 커지는 문제군이 아니라 하나의 큰 최적화 문제를 풀고 싶어 함
    풀이 시간 추세선의 증가율보다, 자기 앞의 큰 인스턴스 하나를 푸는지가 중요하고, 그 인스턴스는 보통 같은 크기의 최악 경우가 되지 않게 해주는 구조를 갖고 있음
    그래서 공학적 선택도 달라짐
    [1] https://arxiv.org/abs/2303.14605
    [2] min { c^T x : A x >= b, x in R^n, some components of x in Z }
    [3] https://gmplib.org/
    [4] https://www.math.leidenuniv.nl/~hwl/PUBLICATIONS/1982f/art.p...

• 초록이 더 유익함: https://arxiv.org/abs/2303.14605
  n개 변수의 정수 계획법을 푸는 (log(2n))^O(n) 시간 무작위 알고리즘을 얻었다는 내용임
  즉 이 작업은 이론적인 결과로, R^n의 볼록체 구조와 그것을 정수 격자로 덮는 방법 분석에 기반해 이전 최고보다 나은 지수 시간 알고리즘을 제시함
  실용적인 ILP 작업 대부분은 휴리스틱과 분기 한정법을 쓰고, 특정 문제 정식화의 특별한 구조를 활용함
  이 연구가 그 둘 중 하나에 도움이 될지는 명확하지 않고, Gurobi 같은 곳의 누군가가 설명하지 않는 한 논문만 읽고는 판단하기 어려울 것 같음

• 사소한 지적이지만 제목에는 정수 선형 계획법이라고 명시해야 함
  여기서는 “정수” 부분이 훨씬 큰 차이를 만들기 때문임
  선형 계획법은 수십 년 전부터 다항 시간 알고리즘이 알려져 있었고, 정수 선형 계획법이 NP-난해함

  • 정수 선형 계획법이 NP-난해한 건 맞지만, 연속 선형 계획법의 더 빠른 알고리즘도 매우 흥미롭고 영향력이 큼
    연속 선형 계획법도 어렵다
    NP-난해하다는 뜻이 아니라, 효율적인 현대 LP 솔버를 만들려면 알고리즘과 공학 측면이 많이 들어간다는 뜻임
    수치 계산만 해도 충분히 복잡함
    그리고 많은 정수 선형 계획법 솔버가 연속 선형 계획법 솔버에 기반함

• 머신러닝이나 알고리즘에 관심 있는 소프트웨어 엔지니어라면 선형 계획법을 배워볼 만함
  놀랄 만큼 많은 문제가 선형 최적화로 정식화될 수 있음
  예를 들어 대학 때 산업공학을 전공한 친구와 당구공을 랙 삼각형 안의 허용 가능한 시작 위치에 놓는 데 필요한 평균 최소 교환 횟수에 대해 이야기한 적이 있음
  둘 다 몬테카를로 표본추출로 푸는 프로그램을 짰는데, 내 풀이는 그래프 상태공간에서 BFS를 했고, 친구의 풀이는 선형 계획법을 썼음
  아마 친구 쪽이 더 효율적이었을 것 같음

  • 조합 최적화 문제의 많은 다항 시간 알고리즘은 해당 LP에 대한 원시-쌍대 알고리즘으로 해석할 수 있음
    예를 들면 최소 신장 트리, 이분 그래프 또는 일반 그래프 매칭, 네트워크 흐름, 매트로이드 교차, 부분모듈러 흐름 등이 있음
    어떤 LP의 꼭짓점 해는 NP-완전 문제의 근사 알고리즘을 설계할 때 활용할 수 있는 흥미로운 성질도 가짐
    예를 들어 Steiner forest 문제의 꼭짓점 해에는 항상 값이 최소 1/2인 변수가 존재함을 증명할 수 있어서, 변수를 반복적으로 반올림하고 LP를 다시 풀면 2-근사 알고리즘을 얻을 수 있음
    대학원 때는 이 문제가 가진 유일한 2-근사 알고리즘이었음
    또 흥미로운 점은 다항 시간 분리 오라클만 있으면 제약식이 지수적으로 많아도 LP를 풀 수 있다는 것임
  • 대학원에서 가장 좋아했던 과목 중 하나가 근사 알고리즘이었고, LP로의 환원이 많이 나왔음
    정말 재미있었고 추천할 만함
  • 산업공학과 컴퓨터과학이 합쳐진 슈퍼 학위가 나오는 미래가 보임
    현재도 운용과학 쪽에서는 놀랄 만큼 겹치는 부분이 많지만, 산업공학 졸업생 중 프로그래밍을 제대로 못 하는 사람이 너무 많아 충격적임
    정말 아쉬움
  • 베팅 시장을 거래할 때 여러 시장에 걸친 차익거래 문제 상당수를 정수 선형 계획법으로 정식화할 수 있었음
    보통 센트 단위의 정수 금액으로만 거래할 수 있어서, 정수 부분이 꽤 중요했던 것으로 기억함
  • ILP는 NP-완전임

• 짧지만 좋은 글임
  아직 수학을 깊게 보진 않았지만, 프리프린트는 이것으로 보임: https://arxiv.org/pdf/2303.14605.pdf
  대칭이나 반복을 줄여 문제 “공간”을 일반화해 단순화하는 방식으로 공간군을 직접 보고 있는 것 같지는 않지만, 그런 구조가 적용될 수 있는지 보면 흥미로울 듯함
  공간군을 적용하고 그 안에 분포한 점 또는 점들의 집합 주변의 Voronoi 셀을 설명하는 소프트웨어를 쓰는 입장이라, 효과가 전파되는 “섬뜩한” 방식에는 익숙함 [1]
  수학자는 아니고 그저 건축가라 이 분야는 내 역량 밖이지만, 생성된 벌집 구조를 가로지르는 경로를 보고 있는 사람으로서 이 결과는 더 조사해볼 가치가 있음
  [0] https://arxiv.org/pdf/2303.14605.pdf
  [1] 이런 작업에 협업할 만한 수학자를 안다면 연락해주면 좋겠음
  진행 중인 작업이고, 말했듯 수학적으로는 내 역량 밖이지만, 실제 전문가가 더 깊이 살펴볼 만한 흥미로운 성질들을 마주쳤음

• 외판원 문제와 관련해 Sapolsky의 최신 책 Determined: A Science of Life without Free Will에 나온 인용이 흥미로움
  소프트웨어 개발자에게 얼마나 관련 있는지는 모르겠지만 매력적임
  개미가 여덟 곳을 확인하며 먹이를 찾을 때, 이상적으로는 각 장소를 한 번씩만 방문하고 5,040가지 가능한 경로, 즉 7! 중 가장 짧은 경로를 택해야 함
  이는 수학자들이 일반 해법을 찾지 못한 채 수세기 동안 붙들고 있는 유명한 외판원 문제의 한 형태임
  한 전략은 가능한 경로를 전부 살펴보고 비교해서 최선의 경로를 고르는 무차별 대입이지만, 방문지가 10곳만 되어도 가능한 방법이 36만 개를 넘고 15곳이면 800억 개가 넘음
  그런데 보통 군체에 있는 대략 1만 마리의 개미를 여덟 먹이 지점 문제에 풀어놓으면, 어떤 개미도 자신이 간 경로와 두 가지 규칙 이상을 알지 못해도 무차별 대입보다 훨씬 짧은 시간에 5,040가지 중 거의 최적에 가까운 해를 찾는다는 내용임
  이 방식이 잘 작동해서 컴퓨터과학자들도 “가상 개미”로 이런 문제를 풀며, 이것이 지금 군집 지능으로 알려져 있다고 함

  • “자연은 NP-난해 문제를 빠르게 푼다!”류 이야기는 꽤 많았지만, 깊이 파보면 보통 답은 “자연은 NP-난해 문제의 국소 최적해를 빠르게 찾는다!”에 가까움
    그리고 표준적인 반응은 “아주 단순한 컴퓨터 알고리즘도 그렇게 한다”임
    외판원 문제에서 유클리드 거리, 즉 각 노드가 고정 좌표를 갖고 경로 비용이 두 점 사이의 유클리드 거리인 경우라면, 최적해의 ε 배 이내 경로를 찾는 다항 시간 알고리즘도 줄 수 있음
    다만 ε에 대해서는 지수적임
  • The Evolutionary Computation Bestiary [1]에는 동물 행동에서 영감을 받은 다양한 휴리스틱이 나열되어 있음
    서문에는 훌륭한 면책 문구도 있음
    “우리는 개인적으로 이 분야 문헌에 유대류는 줄이고 수학은 더 많아져야 하며, 공동체로서 이 은유가 풍부한 시기를 벗어나야 한다고 믿지만, 이는 화학이 연금술을 벗어난 것과 비슷합니다. 다만 이 목록은 나열된 논문들의 과학적 품질에 대해 어떤 주장도 하지 않습니다.”
    [1]: https://fcampelo.github.io/EC-Bestiary/
  • 개미 군집 최적화라는 알고리즘이 있음: https://en.wikipedia.org/wiki/Ant_colony_optimization_algori...
    이런 개미 군체 행동을 모델로 삼은 알고리즘임
    다른 사람들이 말했듯 이는 금기 탐색, 모의 담금질, 유전 알고리즘처럼 국소 최적해를 찾는 데 좋음
    기사에 나온 “소파 생산” 사례 같은 대부분의 비즈니스 목적에는 이 정도로 충분함
    하지만 “일반 해법”을 찾는 것과는 다름
    Sapolsky가 우리가 “일반 해법”을 잘 못 찾는 것과 개미가 국소 최적해를 찾는 능력을 비교하는 건 약간 오해를 부르는 듯함
  • 이는 휴리스틱 탐색을 하는 여러 방법 중 하나를 설명하는 것임
    문제의 일반 형태가 NP-난해하지 않다는 뜻이 아니라, 정보를 더 추가하면 충분히 좋은 해를 근사하거나 최적 탐색을 다룰 수 있게 만들 수 있다는 뜻임
    이런 관점은 첫 번째 AI “혁명” 때 특히 두드러졌고, AI를 인간 지식으로 보강된 탐색 문제로 보는 방식이 유행했음
  • 개미가 다른 개미가 지나간 곳의 냄새를 맡을 수 있다면, 어느 정도 Dijkstra 알고리즘을 하는 셈 아닌가 싶음
    책에서 말하려는 “군집 지능”이 이건가?

• 많은 이산 최적화 문제는 선형 계획법으로 번역할 수 있음
  SAT 솔버처럼 알아두면 정말 강력한 도구임

  • 최근에야 선형 계획법을 알게 됐고, 감을 잡으려고 PuLP와 Python으로 시작했음
    개발자로서 “이걸 어떻게 지금까지 놓쳤지?” 싶은 순간 중 하나였음

• 훌륭한 결과지만 아마 실용적이지는 않을 것임
  선형 계획법에서 내부점 방법이 단체법보다 이론 복잡도는 더 좋지만, 현실에서는 잘 튜닝된 단체법이 거의 항상 이기는 것과 비슷함

  • 그 부분을 잘 이해한 적이 없음
    내부점 방법이 실제로 보통 더 느린 데 대해 널리 받아들여지는 “이유”가 있나?
    경계에 묶여 있는 것보다 내부를 지나가면 좋은 해에 더 빨리 접근할 것 같은데, 고차원에서는 그 차이가 덜 중요할지도 모르겠음

• 여기서 쓰인 표현이 조금 혼란스러움
  “그들이 생각해낸 최선의 버전, 일종의 속도 제한은 문제의 변수들이 외판원이 도시를 방문하는지 여부처럼 이진 값, 즉 0 또는 1만 가질 수 있는 사소한 경우에서 나온다”는 문장이 있는데, NP-완전 문제를 사소한 경우라고 부른 건가?
  모든 ILP는 01-ILP로 환원될 수 있고 그 반대도 된다고 알고 있었음
  또 “불행히도 변수가 0과 1을 넘어선 값을 취하면 알고리즘 실행 시간이 훨씬 길어진다. 연구자들은 오랫동안 이 사소한 이상에 더 가까워질 수 있는지 궁금해했다”는 부분을 보면, 이 연구가 01-ILP의 하한을 개선한 솔버인지, 아니면 01-ILP와 일반 ILP 사이의 경계를 더 가깝게 만든 알고리즘인지 궁금함