help-glpk
[Top][All Lists]
Advanced

[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




reply via email to

[Prev in Thread] Current Thread [Next in Thread]