这是什么离散优化系列?

What Discrete Optimization family is this?

提问人:klausnrooster 提问时间:8/13/2022 最后编辑:klausnrooster 更新时间:8/14/2022 访问量:32

问:

Bin-Assignment Problem我得到了 N 个将要物理实现的 M 个项目的列表(有人实际上必须将项目(此处缩写的名称)放入物理箱中。然后,如有必要,清空垃圾箱并重复使用,从左到右工作。将与以前不同的物品放入垃圾箱会产生真正的成本。我手动重新排列列表以最大程度地减少更改。软件可以以最佳方式更快、更可靠地做到这一点。整个事情发生在Excel中(然后是纸张,然后是工厂)。我写了一些 VBA,一个蛮力的事情,在一些例子中做得很好。但不是全部。如果我知道这是优化系列,我就可以对其进行编码,即使我只是将某些内容传递给 DLL。但多次在线搜索均未成功。我尝试了几种措辞。它不是旅行的 S..、背包等。这似乎类似于生物信息学中的序列比对问题。有人认出它吗?让我们听听吧,运筹学的人。

与语言无关的离 散数学 运筹学

评论

1赞 Matt Timmermans 8/14/2022
这个问题比你想象的要容易。从左到右,排列每一列以匹配上一列中的尽可能多的项目。其他都无所谓。您的示例的最佳成本是 5 - 手动编辑没有将最后两个 R2 放在正确的位置。
0赞 klausnrooster 8/14/2022
@MattTimmermans,谢谢。有一分钟,我看不出如何“达到 5”。但是下面的代码做到了,我的方法和你说的完全一样。这将对中试规模的工厂流程产生真正的影响,并节省我的时间。直到最近,我才意识到 or.stackexchange.com 的存在。并不是说它会有所帮助 - 这里的问题最终太微不足道了,不需要通过 OR 工具来解决。毫无疑问,我选择的标题是不合时宜的。

答:

0赞 klausnrooster 8/14/2022 #1

enter image description here事实证明,这个幼稚的解决方案只需要调整一下。看一个细胞。尝试在正确的列中找到相同的字母。如果你找到一个,现在就把它换成那个单元格右边的任何东西。一路向下。ColumnsPer 参数考虑了实际使用,其中每列都有一个关联的数字列表,网格列交替标签、数字、标签......

Option Explicit
Public Const Row1 As Long = 4
Public Const ColumnsPer As Long = 1  '2, when RM, % 
Public Const BinCount As Long = 6  
Public Const ColCount As Long = 6

Private Sub reorder_items_max_left_to_right_repeats(wksht As Worksheet, _
    col1 As Long, maxBins As Long, maxRecipes As Long, ByVal direction As Integer)

    Dim here As Range
    Set here = wksht.Cells(Row1, col1)
        here.Activate
        
    Dim cond
    For cond = 1 To maxRecipes - 1
        Do While WithinTheBox(here, col1, direction)
            If Not Adjacent(here, ColumnsPer).Value = here.Value Then
                   Dim there As Range
                   Set there = Matching_R_ange(here, direction)
                If Not there Is Nothing Then swapThem Adjacent(here, ColumnsPer), there
            End If
NextItemDown:
            Set here = here.Offset(direction, 0)
                here.Activate
                'Debug.Assert here.Address <> "$AZ$6"
          DoEvents
        Loop
NextCond:
        Select Case direction
            Case 1
                Set here = Cells(Row1, here.Column + ColumnsPer)
            Case -1
                Set here = Cells(Row1 + maxBins - 1, here.Column + ColumnsPer)
        End Select
        here.Activate
    Next cond
End Sub

Function Adjacent(fromHereOnLeft As Range, colsRight As Long) As Range
    Set Adjacent = fromHereOnLeft.Offset(0, colsRight)
End Function

Function Matching_R_ange(fromHereOnLeft As Range, _
                         ByVal direction As Integer) As Range
    
    Dim rowStart As Long
        rowStart = Row1
        
    Dim colLook As Long
        colLook = fromHereOnLeft.Offset(0, ColumnsPer).Column
        
    Dim c As Range
    Set c = Cells(rowStart, colLook)
    
    Dim col1 As Long
    col1 = c.Column
    
    Do While WithinTheBox(c, col1, direction)
        Debug.Print "C " & c.Address
    
        If c.Value = fromHereOnLeft.Value _
        And c.Row <> fromHereOnLeft.Row Then
            Set Matching_R_ange = c
            Exit Function
        Else
                Set c = c.Offset(1 * direction, 0)
        End If
      DoEvents
    Loop
    'returning NOTHING is expected, often
End Function

Function WithinTheBox(ByVal c As Range, ByVal col1 As Long, ByVal direction As Integer)
    Select Case direction
        Case 1
            WithinTheBox = c.Row <= Row1 + BinCount - 1 And c.Row >= Row1
        Case -1
            WithinTheBox = c.Row <= Row1 + BinCount - 1 And c.Row > Row1
    End Select
    WithinTheBox = WithinTheBox And _
               c.Column >= col1 And c.Column < col1 + ColCount - 1
End Function

Private Sub swapThem(range10 As Range, range20 As Range)
    'Unlike with SUB 'Matching_R_ange', we have to swap the %s as well as the items
    'So set temporary range vars to hold %s, to avoid confusion due to referencing items/r_anges
    If ColumnsPer = 2 Then
        Dim range11 As Range
        Set range11 = range10.Offset(0, 1)
        
        Dim range21 As Range
        Set range21 = range20.Offset(0, 1)
        'sit on them for now
    End If
    
    Dim Stak As Object
    Set Stak = CreateObject("System.Collections.Stack")
        Stak.push (range10.Value)           'A
        Stak.push (range20.Value)           'BA
                   range10.Value = Stak.pop 'A
                   range20.Value = Stak.pop '_  Stak is empty now, can re-use
                   
    If ColumnsPer = 2 Then
        Stak.push (range11.Value)
        Stak.push (range21.Value)
                   range11.Value = Stak.pop
                   range21.Value = Stak.pop
    End If
End Sub