The EnumrXtrmC16.lng Model

-

View the model
Download the model

Find alternative primal optimal extreme point solutions (EnumrXtrmC.lng)
  or all feasible extreme points. (See parameter AltOpt)
  to a Linear Program, and report the average of all of them.

  All the solutions found can be written to the file:
    \temp\AltOpt.txt   (see parameter TOFILE)

 An MPS copy of a specific model can be sent to \temp\AltOpt.mps
 by setting GENMPS = 1.

 One can switch to different problems by commenting/uncommenting
the various models, essentially by
 changing a semi-colon to a space, and 
 changing a trailing space to a semi-colon.

  Method:  It is computationally expensive/complicated to enumerate every 
distinct alternative optimal solution.
The approach used here is to (pseudo) randomly choose a large number of 
random objectives/directions and then 
minimize this objective subject to: 
the solution is feasible and is 
optimal for the original objective.  
Duplicate solutions are discarded.
If enough random directions are generated, then 
all alternative primal optimal extreme points, or
feasible extreme points will be generated.
   Note, in 2 dimensions, the (pseudo) random directions 
 approach can enumerate all extreme points in finite steps
 by considering for every pair of already found extreme points 
  (xpt(i), ypt(i)) and (xpt( j), ypt( j)) and choosing the objective:
   (ypt(i)-ypt(j))*x + (xpt(i) - xpt( j)*y, (and its negation).
 If there is a point between i and j, this direction will find it.
 You can stop the search when for every i and j there is no new
 point to be found between them.
 This idea can be generalized to 3 or more dimensions,
 but it becomes a combinatorial challenge.

Keywords:

Enumeration | K-Best Solutions | Extreme point | Corner point | Monte carlo | LINGO | Alternative optima | Average solution | Basic solution | Polytope |