| [ KAIST ] in KIDS 글 쓴 이(By): widewood (황금의입술) 날 짜 (Date): 2003년 7월 22일 화요일 오후 01시 24분 01초 제 목(Title): Re: [질문] linear programing과 integer p Integer Program(IP)이 Linear Program(LP)의 special problem인것은 맞으나 해를 구하는 것은 하늘과 땅차이 입니다. LP의 경우는 solution set이 convex하다라는 기막힌 특성으로 인해 심플렉스라는 일종의 매트릭스 연산으로 간단하게 해결가능하나, IP의 경우는 최적해를 찾는 방법은 branch-and-bound라는 일일이 정수값을 넣어보는 무식한 방법밖에 없기때문에 편법으로 문제의 특성에 맞게 Heuristics을 써서 Near optimal solution을 찾아서 쓸수밖에 없습니다. (웬만한 문제들은 지구의 모래알 갯수보다 많은 수의 정수조합해를 가지기 때문에 실제적으로 branch-and-bound를 써서 답을 구하는 것은 사실상 불간ㅇ으로 보시믄 될듯요) |