Patch for pseudocost branching with product score
Chris Matrakidis <[email protected]>
| Newsgroups | gmane.comp.gnu.glpk |
|---|---|
| Message-ID | <CAEaJ3S4eNNjVzCejoCZorXGmT0bFK8mw8Qd-ii9uKaREBeUO3g@mail.gmail.com> |
Hi Andrew, This patch adds the option to select the branching variable using pseudocosts with product score, as described in Tobias Achterberg's thesis [1]. This is selected with a new br_tech option (GLP_BR_PMH) and a new option in glpsol (--pcostmul), so the old default behaviour is preserved. The patch also updates the manual accordingly. The patch is on top of the three initial patches I sent for speeding-up pseudocost initialisation, but should apply even without them. Using "glpsol --pcostmul --cuts" I was able to solve the following 32 problems from the MIPLIB 2010 benchmark set: acc-tight5, air04, app1-2, ash608gpia-3col, biella1, bienst2, binkar10_1, core2536-691, dfn-gwin-UUM, eil33-2, eilB101, lectsched-4-obj, map18, map20, mcsched, mine-166-5, neos-1109824, neos13, neos18, neos-476283, neos-686190, ns1766074, opm2-z7-s2, qiu, ran16x16, rmatr100-p10, rmatr100-p5, rmine6, sp98ir, tanglegram1, tanglegram2 and triptim1. Best Regards, Chris Matrakidis [1] T. Achterberg, "Constraint Integer Programming," PhD thesis, TU Berlin, 2007. _______________________________________________ Help-glpk mailing list [email protected] https://lists.gnu.org/mailman/listinfo/help-glpk
pcostmul.patch
(text/x-patch, 5.4 KB)
commit 85cb76830f41e50c2a970f94b2da7efcf9a03cda Author: Chris Matrakidis <[email protected]> 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 */