혼합이라는 말의 의미
차량 대수처럼 정수로 정할 양과 공급량처럼 연속적으로 정할 양을 같은 모형에 둘 수 있다. 어떤 변수에 정수 조건이 필요한지는 문제를 설계할 때 지정한다. 0과 1만 허용하는 이진 변수는 정수 변수의 특별한 경우다. 선형식으로 썼다는 사실만으로 모든 변수가 연속적이라는 뜻은 아니다.
완화한 해와 정수 해
목적이 3x+y의 최대화이고 제약이 2x+y≤3, x≥0, y≥0이며 x만 정수라고 하자. 정수 조건을 풀면 x=1.5,y=0에서 값 4.5를 얻는다. 정수 조건을 지키면 x는 0 또는 1이며, x=1,y=1에서 최댓값 4를 얻는다. 정수 조건을 제거한 완화 문제의 값과 원래 문제의 값이 달라지는 예제다.
반올림으로 해결되지 않는다
앞 예제의 완화 해에서 x를 2로 반올림하면 2x+y≤3을 위반한다. x를 1로 내리고 y를 그대로 0으로 두면 가능하지만 목적값은 3이라 최적값 4보다 작다. 정수 변수를 바꾸면 다른 변수도 함께 조정해야 할 수 있다. 완화 문제를 푼 뒤 단순히 숫자만 반올림하는 절차는 일반적으로 정수 최적화와 다르다.
종료 상태와 모형 검토
제한 시간 안에 가능한 해를 찾았어도 최적성이 증명되지 않았을 수 있다. 목적값의 경계와 현재 해 사이의 간격, 정수성과 제약 위반 허용 오차를 확인해야 한다. 불가능한 모형과 해가 아직 발견되지 않은 상태도 구분한다. 실제 조건을 빠뜨리면 수학적으로 최적인 결과도 실행할 수 없으므로 정수 조건뿐 아니라 비용과 제약의 의미를 검토한다.