branch and bound algorithm in AMPL

[rami_a...@yahoo.com]

Hi,

I have been trying to solve a mixed integer bilinear model (involves
multiplication of a binary variable by a continuous one) using my own
branch and bound (B&B) algorithm. The algorithm has proven to be
successful for small problem instances once applied manually but now i
am trying to solve large scale models and it has to be coded. The
algorithm deviates from the traditional B&B in the branching, bounding
and fathoming criteria and that is why i need to code it from scratch
or maybe modify the source code in AMPL. Any ideas on how to code B&B
in AMPL or if there is any ready source codes out there that i could
just modify. I looked in AMPL but icould not find any !! A source
code in any other language will also do ? Thanks a lot in advance.

Cheers,
Rami

[Paul]

If I understand this correctly, you do not want to do the coding in
AMPL. AMPL sets up models but does not solve them -- it exports the
necessary data to a solver, then imports the solution from the
solver. You need to code your algorithm in C++, Java or (dare I say?)
Fortran, perhaps using third-party libraries to do simplex
calculations etc.

If you want to use AMPL to generate the problems, you can have AMPL
export a problem file in a suitable format (if there is one), then
include in your code a routine to read the problem in. If you want
AMPL also to display and process the solution, you'll need to
investigate how to connect AMPL to a solver. I believe there is
information about that on the AMPL web site.

I have very limited experience with bilinear models, so I don't know
whether you can use something like MPS format for the problem files.
I'll leave that to someone else to address.

/Paul

[Ali Baharev]

Dear Rami,

> The
> algorithm deviates from the traditional B&B in the branching, bounding
> and fathoming criteria and that is why i need to code it from scratch

If you could provide more details, i may come up with some tips.

Ali