InterviewSolution
| 1. |
Scip Has Found Decent Primal And Dual Bounds But Still Reports The Gap As "infinity". Why? |
|
Answer» By default, the SCIP output CONTAINS the display column "gap", which is computed as follows: If primal and dual bound have opposite SIGNS, the gap is "INFINITY". If primal and dual bound have the same sign, the gap is |primal bound - dual bound|/min (|primalbound|,|dualbound|)| (see SCIPgetGap()). This definition has the advantage that the gap decreases monotonously during the solving process. An alternative definition of the gap is (dual bound - primal bound) / abs (primal bound). Using this definition, a finite gap is computed as soon as a dual and primal bound have been found. HOWEVER, the gap may INCREASE during the solving process, if both bounds have opposite signs in the beginning. In SCIP, this definition can be included in the output by enabling the display column "primal gap": display/primal gap/active = 2 By default, the SCIP output contains the display column "gap", which is computed as follows: If primal and dual bound have opposite signs, the gap is "Infinity". If primal and dual bound have the same sign, the gap is |primal bound - dual bound|/min (|primalbound|,|dualbound|)| (see SCIPgetGap()). This definition has the advantage that the gap decreases monotonously during the solving process. An alternative definition of the gap is (dual bound - primal bound) / abs (primal bound). Using this definition, a finite gap is computed as soon as a dual and primal bound have been found. However, the gap may increase during the solving process, if both bounds have opposite signs in the beginning. In SCIP, this definition can be included in the output by enabling the display column "primal gap": display/primal gap/active = 2 |
|