commit 85cb76830f41e50c2a970f94b2da7efcf9a03cda
Author: Chris Matrakidis <address@hidden>
Date:   Wed Mar 9 03:06:23 2016 +0200

    add --pcostmul product score option

diff --git a/doc/glpk02.tex b/doc/glpk02.tex
index 08a0219..a653a0e 100644
--- a/doc/glpk02.tex
+++ b/doc/glpk02.tex
@@ -2956,7 +2956,11 @@ Branching technique option:
 
 \verb|GLP_BR_DTH| --- heuristic by Driebeck and Tomlin;
 
-\verb|GLP_BR_PCH| --- hybrid pseudo-cost heuristic.
+\verb|GLP_BR_PCH| --- hybrid pseudo-cost heuristic;
+
+\verb|GLP_BR_PMH| --- hybrid pseudo-cost heuristic with product
+score\footnote{T. Achterberg, ``Constraint Integer Programming,''
+PhD thesis, TU Berlin, 2007.}.
 
 \bigskip\vspace*{-2pt}
 
diff --git a/doc/glpk10.tex b/doc/glpk10.tex
index 1943ef0..c3cc7ff 100644
--- a/doc/glpk10.tex
+++ b/doc/glpk10.tex
@@ -118,6 +118,7 @@ the problem, and write its solution to an output text file.
                      (default)
    --pcost           branch using hybrid pseudocost heuristic (may be
                      useful for hard instances)
+   --pcostmul        variation of --pcost using product score
    --dfs             backtrack using depth first search
    --bfs             backtrack using breadth first search
    --bestp           backtrack using the best projection heuristic
@@ -153,6 +154,8 @@ For description of the modeling language see the document ``Modeling
 Language GNU MathProg: Language Reference'' included in the GLPK
 distribution.
 
+\newpage
+
 For description of the DIMACS min-cost flow problem format and DIMACS
 maximum flow problem format see the document ``GLPK: Graph and Network
 Routines'' included in the GLPK distribution.
diff --git a/examples/glpsol.c b/examples/glpsol.c
index f4d4b1d..5adee8d 100644
--- a/examples/glpsol.c
+++ b/examples/glpsol.c
@@ -357,6 +357,8 @@ static void print_help(const char *my_name)
       xprintf("   --pcost           branch using hybrid pseudocost heur"
          "istic (may be\n");
       xprintf("                     useful for hard instances)\n");
+      xprintf("   --pcostmul        variation of --pcost using product "
+         "score\n");
       xprintf("   --dfs             backtrack using depth first search "
          "\n");
       xprintf("   --bfs             backtrack using breadth first searc"
@@ -805,6 +807,8 @@ static int parse_cmdline(struct csa *csa, int argc, char *argv[])
             csa->iocp.br_tech = GLP_BR_DTH;
          else if (p("--mostf"))
             csa->iocp.br_tech = GLP_BR_MFV;
+         else if (p("--pcostmul"))
+            csa->iocp.br_tech = GLP_BR_PMH;
          else if (p("--pcost"))
             csa->iocp.br_tech = GLP_BR_PCH;
          else if (p("--dfs"))
diff --git a/src/glpapi09.c b/src/glpapi09.c
index 8e5496c..cf08764 100644
--- a/src/glpapi09.c
+++ b/src/glpapi09.c
@@ -465,7 +465,8 @@ int glp_intopt(glp_prob *P, const glp_iocp *parm)
             parm->br_tech == GLP_BR_LFV ||
             parm->br_tech == GLP_BR_MFV ||
             parm->br_tech == GLP_BR_DTH ||
-            parm->br_tech == GLP_BR_PCH))
+            parm->br_tech == GLP_BR_PCH ||
+            parm->br_tech == GLP_BR_PMH))
          xerror("glp_intopt: br_tech = %d; invalid parameter\n",
             parm->br_tech);
       if (!(parm->bt_tech == GLP_BT_DFS ||
diff --git a/src/glpios09.c b/src/glpios09.c
index 727761c..d4e1ba6 100644
--- a/src/glpios09.c
+++ b/src/glpios09.c
@@ -69,7 +69,8 @@ int ios_choose_var(glp_tree *T, int *next)
       {  /* branch using the heuristic by Dreebeck and Tomlin */
          j = branch_drtom(T, next);
       }
-      else if (T->parm->br_tech == GLP_BR_PCH)
+      else if (T->parm->br_tech == GLP_BR_PCH ||
+               T->parm->br_tech == GLP_BR_PMH)
       {  /* hybrid pseudocost heuristic */
          j = ios_pcost_branch(T, next);
       }
@@ -686,8 +687,14 @@ int ios_pcost_branch(glp_tree *T, int *_next)
          }
          /* estimate degradation of the objective for up-branch */
          d2 = psi * (ceil(beta) - beta);
-         /* determine d = max(d1, d2) */
-         d = (d1 > d2 ? d1 : d2);
+         if (T->parm->br_tech == GLP_BR_PCH)
+         {  /* determine d = max(d1, d2) */
+            d = (d1 > d2 ? d1 : d2);
+         }
+         else
+         {  /* determine d = d1 * d2 (with small bias to avoid zero) */
+            d = (1e-6 + d1) * (1e-6 + d2);
+         }
          /* choose x[j] which provides maximal estimated degradation of
             the objective either in down- or up-branch */
          if (dmax < d)
@@ -705,7 +712,9 @@ int ios_pcost_branch(glp_tree *T, int *_next)
             }
          }
       }
-      if (dmax == 0.0)
+      /* dmax is either zero or above 1e-6 for max score and 1e-12 or
+         above 2e-12 for product score */
+      if (dmax < 1.5e-12)
       {  /* no degradation is indicated; choose a variable having most
             fractional value */
          jjj = branch_mostf(T, &sel);
diff --git a/src/glpk.h b/src/glpk.h
index 137801c..e06d46b 100644
--- a/src/glpk.h
+++ b/src/glpk.h
@@ -163,6 +163,7 @@ typedef struct
 #define GLP_BR_MFV         3  /* most fractional variable */
 #define GLP_BR_DTH         4  /* heuristic by Driebeck and Tomlin */
 #define GLP_BR_PCH         5  /* hybrid pseudocost heuristic */
+#define GLP_BR_PMH         6  /* like GLP_BR_PCH with product score */
       int bt_tech;            /* backtracking technique: */
 #define GLP_BT_DFS         1  /* depth first search */
 #define GLP_BT_BFS         2  /* breadth first search */