“K－Best Solution” in LINGO

wujianjack2

  本帖以一个简单的实例讨论LINGO求解整数规划中存在多解问题时的求解策略，如knapsack。

声明： 自LINGO 11版本后，已可以直接求解了，此处仅作简单分享。
           本帖内容主要参考文献：Lingo 11 Users Manual

1.示例程序（来自LINGO 11安装文件Samples文件夹，KBEST.lg4）
MODEL:
SETS:
   ITEMS: INCLUDE, WEIGHT, RATING;
   MYFAVORITES( ITEMS);
ENDSETS
DATA:
   KNAPSACK_CAPACITY = 15;
   ITEMS   WEIGHT  RATING =
     BRATS       3      1
     BROWNIES    3      1
     BEER        3      1
     ANT_REPEL   7      1
     BLANKET     4      6
     FRISBEE     1      6
     SALAD       5     10
     WATERMELON  7      9;
   MYFAVORITES = BRATS BROWNIES BEER;
ENDDATA
MAX = @SUM( ITEMS: RATING * INCLUDE);
@SUM( ITEMS: WEIGHT * INCLUDE) <= KNAPSACK_CAPACITY;
@FOR( ITEMS: @BIN( INCLUDE));
NUMFAVE = @SUM( MYFAVORITES: INCLUDE);
END

2.问题求解：（求解使用LINGO 11 Extended_English Crack）
如果直接用LINGO求解，无论是使用默认设置，还是使用Global Solver，均得到如下结果：

以上结果为Global Solver求解结果。

然而，这种问题最优解往往不止一个，或者，我们还想知道一些次优解，如何简单地利用LINGO实现呢？
操作流程：（以LINGO 11为例）
LINGO->Options->Integer Solver->K-Best Solutions（修改Desired值）
截图如下：(本例修改Desired值为3）


运行结果：


完整结果：


自定义选择结果：（以第一个值为23的解为例）


     对于类似的问题，采用上述操作，则可以得到所需的多解，但Desired值也不宜过大，建议由小到大逐个试。程序也要保证有多个解，这样避免出现不可预知的错误。
     有意者详情见参考文献。

wujianjack2

chengfei1004 发表于 2014-10-17 23:02

    看来是我误会啦，表示歉意。
    我之前查看你回复的其它帖子以及分享的资料，感觉你应该是一个比较有修养的人，且为人应当不错。只是你回复我均是这个表情，而我误解为“鄙视”之意。我以为你有什么意见或者建议，但不想说，加上你如今应该也在西安上学，以及我最近心情不好...........是故有此一问未直接警告什么的，冒犯之处，望多多包容。
    一个小建议哈，尽量不要用纯表情回复，以后数学中国也许也会再出现如我一般挑剔的版主，避免不必要的误会啊，你是新注册用户，希望你享受在论坛的时光。
    论坛里实则大杂烩，各色人均有，以后若有人对你言语不当，不要往心里去，Enjoy yourself !
    Good Luck ！

chengfei1004

wfg786200304

赞。。。。。。。。。。。。。。。。。。。

哇哈哈哈丨

健哥此做法仅限于ILP问题而不适合于LP问题

流雨星月

顶一个。。。。

小苹果°ヾ

小苹果°ヾ

顶                       

樊朋朋

顶顶顶顶顶顶顶顶顶顶顶顶顶顶

梦@di?~

lingo求解整数规划