1.5 Output
BiqCrunch provides detailed information during the solving process and an output
file is generated using the name of the input file (same directory).
Example of screen output: ./biqcrunch -v 1 example.bc biq_crunch.param
Output file: example.bc.output
Input file: example.bc
Parameter file: biq_crunch.param
Node 0 Feasible solution 43
Nodes = 3
Root node bound = 47.43
Maximum value = 43
Solution = { 1 2 3 }
CPU time = 0.0045 s
Example of output file: ./biqcrunch -v 1 example.bc biq_crunch.param
*******************************************************************************
* BIQ CRUNCH 2.0 Solver *
*******************************************************************************
| Copyright(C) 2010-2016 N. Krislock, J. Malick, F. Roupin |
| BIQ CRUNCH uses L-BFGS-B by C. Zhu, R. Byrd, J. Nocedal and BOB 1.0 by PNN |
| Team of PRiSM Laboratory. |
| |
| L-BFGS-B is distributed under the terms of the New BSD License. See the |
| website http://users.eecs.northwestern.edu/~nocedal/lbfgsb.html for more |
| information. BOB is free software. For more information visit the website |
| http://www.prism.uvsq.fr/~blec/index.php?p=./rech/so&lang=fr |
*******************************************************************************
Input file: example.bc
Solving as a MAXIMIZATION problem
Problem Size = 5 Number of equalities = 7 Number of inequalities = 1
Using Generic heuristic
BiqCrunch Parameters:
alpha0 = 0.100000
scaleAlpha = 0.500000
minAlpha = 0.000050
tol0 = 0.100000
scaleTol = 0.950000
minTol = 0.010000
withCuts = 1
gapCuts = -0.050000
cuts = 500
minCuts = 50
nitermax = 2000
minNiter = 12
maxNiter = 100
scaling = 1
root = 0
heur_1 = 1
heur_2 = 1
heur_3 = 1
soln_value_provided = 0
soln_value = 0
time_limit = 0
branchingStrategy = 1
seed = 2016
NBGW1 = 1
NBGW2 = 10
local_search = 1
Heuristic 1: Beta updated => 43
**************************************************************************************
Node 1
**************************************************************************************
Problem size 5
Fixed variables:
======================================================================================
Iter Time gap alpha tol nbit Enorm Inorm ynorm minCut NCut NSub NAdd
======================================================================================
1 0.0 4.6 1e-01 1e-01 24 5e-02 0e+00 5e+01 -3e-01 13 -0 +13
2 0.0 4.5 5e-02 1e-01 5 5e-02 9e-02 5e+01 -1e-01 31 -0 +18
3 0.0 4.4 3e-02 9e-02 7 4e-02 3e-02 5e+01 -7e-02 41 -0 +10
4 0.0 4.4 1e-02 9e-02 8 5e-02 3e-02 5e+01 -3e-02 41 -0 +0
5 0.0 4.4 6e-03 8e-02 4 6e-02 7e-02 5e+01 -2e-01 60 -0 +19
6 0.0 4.4 3e-03 8e-02 6 2e-02 0e+00 5e+01 3e-03 60 -0 +0
7 0.0 4.4 2e-03 7e-02 5 2e-02 5e-02 5e+01 -5e-02 60 -0 +0
8 0.0 4.4 8e-04 7e-02 6 2e-02 6e-02 5e+01 -6e-02 60 -0 +0
9 0.0 4.4 4e-04 7e-02 6 2e-02 6e-02 5e+01 -6e-02 60 -0 +0
10 0.0 4.4 2e-04 6e-02 6 2e-02 6e-02 5e+01 -6e-02 60 -0 +0
11 0.0 4.4 1e-04 6e-02 7 2e-02 6e-02 5e+01 -6e-02 60 -0 +0
12 0.0 4.4 5e-05 6e-02 13 4e-02 0e+00 5e+01 nan 60 -0 +0
======================================================================================
Giving up! Bound = 47.43, Iter = 12, alpha = 5e-05, tol = 6e-02, cuts = 60, time = 0.0
======================================================================================
Depth = 0, Bound = 47, Best = 43
Branching on x[3] = 0.04
Fixing x[3] = 0
**************************************************************************************
Node 2
**************************************************************************************
Problem size 4
Fixed variables: (x[3],0)
======================================================================================
Iter Time gap alpha tol nbit Enorm Inorm ynorm minCut NCut NSub NAdd
======================================================================================
1 0.0 2.2 1e-01 1e-01 12 5e-02 0e+00 4e+01 -1e-01 6 -0 +6
2 0.0 0.8 5e-02 1e-01 22 1e-01 0e+00 5e+01 nan 6 -0 +0
======================================================================================
Prune! Bound = 43.78, Iter = 2, alpha = 5e-02, tol = 1e-01, cuts = 6, time = 0.0
======================================================================================
Depth = 1, Bound = 43, Best = 43
Fixing x[3] = 1
**************************************************************************************
Node 3
**************************************************************************************
Problem size 4
Fixed variables: (x[3],1)
======================================================================================
Iter Time gap alpha tol nbit Enorm Inorm ynorm minCut NCut NSub NAdd
======================================================================================
1 0.0 0.9 1e-01 1e-01 24 3e-01 0e+00 6e+01 nan 0 -0 +0
======================================================================================
Prune! Bound = 43.90, Iter = 1, alpha = 1e-01, tol = 1e-01, cuts = 0, time = 0.0
======================================================================================
Depth = 1, Bound = 43, Best = 43
Nodes = 3
Root node bound = 47.43
Maximum value = 43
Solution = { 1 2 3 }
CPU time = 0.0045 s
BiqCrunch can be also used as a simple semidefinite solver to get a bound
(further details are given about parameters in Section 2). Hereafter, the same small
example is run with the parameter file bound.param (provided in the biqcrunch/
folder). In the first test, all the heuristics are disabled and so no lower bound (given
by a feasible solution) is available. In the second run, the heuristics are enabled (see
Section 2.1).
Example of screen file: ./biqcrunch -v 1 example.bc bound.param
Output file: example.bc.output_1
Input file: example.bc
Parameter file: bound.param
Nodes = 1
Root node bound = 47.32536
Best value = inf
Gap = 100.00%
CPU time = 0.0037 s
Output file: example.bc.output_2
Input file: example.bc
Parameter file: bound.param
Node 0 Feasible solution 43
Nodes = 1
Root node bound = 47.32536
Best value = 43
Gap = 10.06%
CPU time = 0.0038 s