bnb
所属分类:matlab编程
开发工具:matlab
文件大小:135KB
下载次数:139
上传日期:2007-03-01 14:00:34
上 传 者:
duck_312
说明: matlab 实现的整数规划工具箱,用起来挺方便的
(Matlab achieve the integer programming toolbox, together with quite convenient)
文件列表:
bnb\BNB20.m (14545, 2000-01-24)
bnb\BNBGUI.m (810, 2000-02-21)
bnb\BNBGUICB.m (24558, 2001-11-16)
bnb\BNBHELP.txt (3247, 2000-02-21)
bnb\Example.zip (57037, 2001-11-16)
bnb\font\crld.ttf (73740, 1995-02-02)
bnb\optim\nlconst.m (21115, 2000-02-10)
bnb\optim\qpsub.m (26800, 2000-02-10)
bnb\private\guierr.m (3247, 2000-02-16)
bnb\private\guierr.mat (1864, 2000-02-16)
bnb\private\guifun.m (14231, 2000-02-21)
bnb\private\guifun.mat (2184, 2000-02-21)
bnb\private\guimain.m (11907, 2000-02-16)
bnb\private\guimain.mat (3576, 2000-02-16)
bnb\private\guiset.m (4292, 2000-02-21)
bnb\private\guiset.mat (1952, 2000-02-21)
bnb\private\guiupd.m (2465, 2000-02-16)
bnb\private\guiupd.mat (1720, 2000-02-16)
bnb\font (0, 2006-10-26)
bnb\optim (0, 2006-10-26)
bnb\private (0, 2006-10-26)
bnb (0, 2006-10-26)
README FOR THE BNBGUI
INSTALLATION
To function BNB needs:
Matlab 5.3 or newer
Optimization Toolbox 2.0
the Courier-LD font (8 points, regular)
Unzip BNB.zip to an empty directory that's in the MATLAB path. Make
sure you unzip using folder names. This because some files must be
placed in a subdirectory called private.
USAGE
BNB has a graphical user interface (GUI). To run it type BNBGUI at the
Matlab prompt. The program has been used (and tested) with Matlab
5.3.1.29215a (R11.1).
A short explanation of how branch and bound works: A problem with an
integer variable is first being solved with the integer variable
considered continuous (the first sub-problem). After this the program
generated sub problems where the domain of the variable (still
continuous) is being restricted. This is called branching. Then it
solves these sub-problems. This process continues until the variable is
fixed to a (integer) value.
The advantage of this approach (when compared with explicit
enumeration) lies in the fact that not all the sub-problems have to be
solved (fathoming, i will not explain how this works here). Important
for the user is that branch-and-bound only works when the problem is
formulated continuous.
BNB20 is useful for making choices. Say you want the algorithm to make
an optimal choice between 3 materials. Define 3 0-1-variables (integer
variables with domain 0-1). Somewhere in your formulas you use the
hardness of the material. Because the problem has to be formulated
continuous you should formulate the hardness like this:
hardness=x(1:3).*[hardness1 hardness2 hardness3];
And somewhere else in your formulas you use the weight:
weight=x(1:3).*[weight1 weight2 weight3]; etc.
Of course you want to end with one of the materials being picked, so
you add to your linear constrains x(1)+x(2)+x(3)=1.
ALGORITHM
The algorithm is BNB20.m. It is a simple branch-and-bound type
algorithm. Its specifications are:
* Depth-first traversal with backtracing.
* Both the variable to branch on and the branch to traverse are chosen
by simple
heuristics.
* The algorithm detects 0-1 variables with constrains like
x(a)+x(b)+x(c)+..=1
and adapts the branching to it.
* To solve the nonlinear sub-problems BNB20 uses fmincon from the
optimization
toolbox 2.0.
For more info at the Matlab prompt type help BNB20.
OPTIMIZATION TOOLBOX VERSION 2.0 (R11)
To get rid of bugs and to stop fmincon from hanging make the following
chances:
In optim/private/nlconst.m ($Revision: 1.20 $ $Date: 19***/08/24
13:46:15 $):
Get EXITFLAG independent of verbosity.
After the lines: disp(' less than 2*options.TolFun but
constraints are not satisfied.')
end
EXITFLAG = -1;
end
end
status=1;
add the line: if (strncmp(howqp, 'i',1) & mg > 0), EXITFLAG = -1; end;
(This bug was found by Ingar Solberg)
In optim/private/qpsub.m ($Revision: 1.21 $ $Date: 19***/09/01 21:37:56
$):
Stop qpsub from hanging.
After the line: % Andy Grace 7-9-90. Mary Ann Branch 9-30-96.
add the line: global maxSQPiter;
and changed the line: maxSQPiters = Inf;
to the line: if exist('maxSQPiter','var'), maxSQPiters = maxSQPiter;
else
maxSQPiters=inf; end;
I guess there was a reason to put maxSQPiters at infinity, but this
works fine for me.
Koert Kuipers
e-mail koertkuipers@yahoo.com
Fysische Informatica
Applied Physics
University of Groningen
The Netherlands
近期下载者:
相关文件:
收藏者: