주메뉴 바로가기 본문 바로가기 하단 바로가기

고객지원

기술문의

MIP를 CPLEX로 푸는데, breadth-first 기법은 option이 없나요?

  • 김동근
  • 2007.04.10
  • 조회수 1,528
안녕하세요.
MIP를 CPLEX로 풀고자 하는 박사과정 학생입니다.

breadth-first 기법으로 풀고자 manual을 찾아보니,
(ILOG CPLEX 10.1- User's Manual 256page)
depth-first기법 등 몇 가지는 option으로 이용할 수 있는데,
breadth-first기법은 없네요.

CPLEX에서 지원하지 않는 건가요?

그렇다면, breadth-first 기법을 구현하려면 어떻게 해야할까요?

답변부탁드려요~~

댓글 3

  • 유환주2007-04-11
    MIP 풀이에서 속도를 개선하려는 경우, 통상 MIPEmphasis의 변경, Heuristic 작동의 설정, 의미없는 Cut 작동의 정지, 새로운 Cut의 추가와 같은 작업을 합니다.
    그 외의 시도가 좋은 효과로 연결된 적은 별로 없었답니다.
    .
    이런 저런 설정의 변경으로 잘 안되면, 자신만의 탐색을 만들어 보세요.
    예제가 CPLEX Examples에 있습니다.
    ilogoalex3.cpp를 참조하면 깊이 우선탐색을 만들 수 있습니다.
    MIPEmphasis 설정 방법 -----------------
    cplex.setParam(IloCplex::MIPEmphasis, 0);
    - 0 Balance optimality and feasibility
    - 1 Emphasize feasibility over optimality
    - 2 Emphasize optimality over feasibility
    - 3 Emphasize moving best bound
    - 4 Emphasize finding hidden feasible solutions
    Node Selector 설정 방법 ---------------
    cplex.setParam(IloCplex::NodeSel, 0);
    - 0 Depth-first search
    - 1 Best-bound search
    - 2 Best-estimate search
    - 3 Alternative best-estimate search
    아이콘삭제
  • 김동근2007-04-11
    답변 감사합니다.

    그런데, 제가 하고자 하는 것은 깊이 우선탐색이 아니라 너비 우선탐색입니다.

    다시 한 번 답변 부탁드려요~~
    아이콘삭제
  • 유환주2007-04-11
    ilogoalex3.cpp 예제를 보시면,
    evaluate() 함수가 있는데, 이것은 노드를 선택시 이 평가값이 최소인 것을 먼저 선택합니다.
    따라서 return -getDepth();라는 것은 -depth가 최소인 것을 먼저 선택한다는 의미입니다.
    즉, depth가 증가되는 것을 우선 선택하는 깊이 우선탐색이 됩니다.
    .
    이것을 breadth-first로 바꾸려면,
    evaluate() 함수를 return getDepth();로 고쳐보세요.
    그러면 후보 중에서 depth가 최소인 것을 먼저 선택하게 될겁니다.
    아이콘삭제

댓글 입력