[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[Help-glpk] finding multiple integer solutions
From: |
Erik Rantapaa |
Subject: |
[Help-glpk] finding multiple integer solutions |
Date: |
Wed, 19 Nov 2003 01:26:31 -0800 (PST) |
I would like to modify the MIP solver to allow for finding multiple optimal
solutions, and I would appreciate any comments on a particular approach I am
contemplating.
The idea is that when a node is found to have the same relaxed score
as the current best integer feasible solution, it is "saved" for later
evaluation rather than pruned. After an optimal integer solution is found,
these nodes can be revisted to see if they yield any more optimal solutions.
In all of my intended applications the objective function will be integer
valued.
The policy for saving nodes could take on various forms, such as:
1. Save at most a fixed number of nodes. Base your decision on the node's
relaxed score.
2. Save all nodes with the same relaxed score as the best integer solution.
Prune those nodes if a better integer solution is found.
Under policy 1 you may wind up saving nodes which yield sub-optimal
solutions. This, however may be okay if you are looking for, say, ten
of the best solutions. Under policy 2 you will only find optimal integer
solutions. However, the nodes you save may not yield any more optimal
solutions.
I know this approach is not guaranteed to find any new solutions, but it
seems better than, say, resolving the entire problem again with some
perturbations added in an attempt to locate a different solution.
The changes I envision to the MIP solver involve adding two fields to the
data structures:
- to the MIPTREE object, add a field called "mode" which can take on
the values SEARCHING, FOUND_OPTIMAL and TERMINATE. It's initial
value is SEARCHING.
- to the IESNODE object, add a flag called "marked" which is initially
set to 0 (or false).
The change to the solver code would be in three places: the main solver loop,
the record_solution() function and the MIP_V_SELECT code in the application
procedure. Here's the pseudo-code for these three changes:
/* decide what to do with the current subproblem */
if mode == SEARCHING,
if curr->lp_obj is strictly worse than best[0],
prune.
else if curr->lp_obj is equal to best[0],
either set curr->marked = 1 or prune.
perhaps prune other marked nodes to keep number
of marked nodes small.
if not pruned, note that curr remains an 'active' node.
else if curr->lp_obj is strictly better than best[0],
if integer solution, record_solution()
else branch.
end if
elsif mode == FOUND_OPTIMAL,
if curr->lp_obj is strictly worse than best[0],
prune.
else
if integer solution, record_solution()
else branch.
endif
elsif mode == TERMINATE,
prune.
endif
record_solution():
if mode == SEARCHING,
store the new solution in best[].
perhaps prune marked nodes which are strictly
worse than best[0].
else if mode == FOUND_OPTIMAL,
emit solution as an optimal one.
if found enough solutions,
mode = TERMINATE
endif
endif
MIP_V_SELECT:
if mode == SEARCHING,
if there is an active node which is not marked,
return one via the appropriate heuristic.
else
mode = FOUND_OPTIMAL,
/* fall through */
endif
endif
/* mode == FOUND_OPTIMAL or TERMINATE */
return an active node (perhaps a random one).
Here are the questions I have:
1. Is the above idea workable? Are there any flaws in the logic?
Can you think of any better ways to go about finding additional optimal
solutions?
2. Are there any data-structure integrity issues I'll have to worry about
if I'm going to implement this? For example, the MIP_V_SELECT code now
may return a node which already has been through the LP solver, whereas
in the original code I don't think this could happen. Will this cause
any problems?
This raises another question -- if the MIP_V_SELECT code does return a
node that's already been through the LP solver, is there a way to detect
this so that the node doesn't need to be re-relaxed?
3. These changes suggest that the protocol between the MIP solver and the
application could be extended so that more of the policy code could be
put in the application procedure. For instance, perhaps the application
proc could tell the solver what to do with a node -- prune, branch,
record it or just move on to the next sub-problem.
I'd appreciate any comments and/or suggestions on these issues.
__________________________________
Do you Yahoo!?
Protect your identity with Yahoo! Mail AddressGuard
http://antispam.yahoo.com/whatsnewfree
- [Help-glpk] finding multiple integer solutions,
Erik Rantapaa <=