给定一组 140 个选项，我的目标是选择一组选项，以最小化目标函数并实现权重必须 > 5584 个单位的约束。
标准 1 是要最小化的目标函数。
我没想到也不明白的是，为什么当我将选项集减少到较小的选项子集时，lp() 会找到一个更优化的解决方案。
请注意，我没有很强的数学背景，所以不太理解其背后的数学。但是，我知道线性规划每次都会为我找到可用的最佳解决方案。
这是一个可重现的示例：
#First define the FULL option set of 140 options, each with a weight and a criteria 1.
DFToOptimizeFull <- structure(list(item_ID = c("Option1", "Option2", "Option3", "Option4",
"Option5", "Option6", "Option7", "Option8", "Option9", "Option10",
"Option11", "Option12", "Option13", "Option14", "Option15", "Option16",
"Option17", "Option18", "Option19", "Option20", "Option21", "Option22",
"Option23", "Option24", "Option25", "Option26", "Option27", "Option28",
"Option29", "Option30", "Option31", "Option32", "Option33", "Option34",
"Option35", "Option36", "Option37", "Option38", "Option39", "Option40",
"Option41", "Option42", "Option43", "Option44", "Option45", "Option46",
"Option47", "Option48", "Option49", "Option50", "Option51", "Option52",
"Option53", "Option54", "Option55", "Option56", "Option57", "Option58",
"Option59", "Option60", "Option61", "Option62", "Option63", "Option64",
"Option65", "Option66", "Option67", "Option68", "Option69", "Option70",
"Option71", "Option72", "Option73", "Option74", "Option75", "Option76",
"Option77", "Option78", "Option79", "Option80", "Option81", "Option82",
"Option83", "Option84", "Option85", "Option86", "Option87", "Option88",
"Option89", "Option90", "Option91", "Option92", "Option93", "Option94",
"Option95", "Option96", "Option97", "Option98", "Option99", "Option100",
"Option101", "Option102", "Option103", "Option104", "Option105",
"Option106", "Option107", "Option108", "Option109", "Option110",
"Option111", "Option112", "Option113", "Option114", "Option115",
"Option116", "Option117", "Option118", "Option119"), criteria_1 = c(0.19382357870646,
0.406093545012686, 0.26444538198799, 0.26601032196915, 0.582727750839455,
0.610218171520381, 0.278839154130233, 0.121920371729594, 0.394236226297326,
0.377841864658525, 0.120477145449607, 0.26254096134174, 0.320858353224026,
0.157895381699022, 0.367337498338429, 0.178897294673147, 0.206447474122835,
0.125249409058597, 0.0964062671575285, 0.155883926971779, 0.745589005311248,
0.271814782493108, 1, 0.709925503817279, 0.283967774188142, 0.465574672453751,
0.747720902276497, 0.261597766848332, 0.223547497818285, 0.312169636303741,
0.361688040733056, 0.33135717134122, 0.720315669627635, 0.597242543157505,
0.793399950297349, 0.422337180472638, 0.319528402753296, 0.430606430135989,
0.397399279889498, 0.343212756243173, 0.330215166243809, 0.266929589837542,
0.341647931849574, 0.337592426703038, 0.42473989909206, 0.308525738460027,
0.424706956637327, 0.357390032884661, 0.280438539204411, 0.409378774656271,
0.346474174849303, 0.791793745557103, 0.450584584087061, 0.262056880638506,
0.311923434799947, 0.448835397534517, 0.330430390281398, 0.141640071895463,
0.1929124019673, 0.176881794381289, 0.379488987395177, 0.741791953949916,
0.0370066289465928, 0.0768869958215097, 0.147257049396344, 0.570100734558947,
0.36424969224812, 0.254741112761445, 0.339564812834843, 0.305964896057886,
0.286239647689116, 0.326383438614336, 0.458683804448965, 0.567810482635859,
0.235202885065509, 0.729063336203758, 0.341599616249299, 0.153703714406256,
0.117457767195094, 0.134082379254345, 0.558969536898439, 0.286059793445029,
0.322705673615406, 0.396612822128083, 0.100616428459969, 0.156259239780615,
0.232564021060054, 0.104164041865814, 0.210723751509863, 0.192397806148102,
0.166759676123656, 0.310175982060811, 0.200003698801935, 0.193767171976952,
0.137411647758468, 0.369825867340157, 0.429786451982038, 0.202788665483821,
0.786777129845286, 0.321634986042802, 0.496148738072809, 0.170282669379121,
0.140613654358518, 0.155074004935589, 0.106219651041155, 0.121895751579215,
0.144999508752868, 0.278420842748903, 0.61995781054043, 0.860520490784782,
0.860520490784782, 0.894125146651717, 0.894125146651717, 0.894125146651717,
0.443148836322235, 0.120796860641858, 0.0224245646683504, 0.223040877540759,
0.195655525952297), itemWeight = c(151, 482, 309, 323, 648, 766,
309, 29, 385, 232, 114, 104, 326, 172, 69, 133, 130, 107, 222,
118, 657, 152, 1150, 723, 339, 516, 1126, 300, 247, 372, 286,
380, 935, 849, 1239, 571, 344, 639, 640, 476, 456, 336, 563,
536, 682, 463, 477, 518, 350, 695, 384, 953, 457, 284, 345, 549,
418, 196, 276, 217, 569, 657, 37, 78, 151, 613, 392, 280, 389,
320, 332, 366, 584, 619, 258, 903, 349, 160, 124, 141, 671, 282,
333, 428, 97, 57, 251, 62, 214, 194, 167, 316, 198, 231, 135,
345, 514, 188, 787, 359, 522, 168, 128, 165, 114, 129, 131, 92,
374, 307, 307, 307, 307, 307, 86, 73, 7, 109, 208)), row.names = c(NA,
-119L), class = c("tbl_df", "tbl", "data.frame"))
#Minimize criteria 1 on the full set
minimizedC_1FullSet <- lp(direction = "min",
objective.in =
DFToOptimizeFull$criteria_1,
const.mat = matrix(
DFToOptimizeFull$itemWeight, nrow = 1),
const.dir = ">=", #firm energy must be greater than or equal to
const.rhs = 5584, #the energy target
all.bin = TRUE)
minimizedC_1FullSet
#I get 3.548285.
#--
#Now lets solve the exact same problem but on only a select number of options. Not the full set.
DFToOptimizeSelect <- DFToOptimizeFull %>% filter(item_ID %in% c( "Option19", "Option27", "Option35",
"Option39", "Option43", "Option45",
"Option50", "Option57"))
minimizedC_1Select <- lp(direction = "min",
objective.in =
DFToOptimizeSelect$criteria_1,
const.mat = matrix(
DFToOptimizeSelect$itemWeight, nrow = 1),
const.dir = ">=", #firm energy must be greater than or equal to
const.rhs = 5584, #the energy target
all.bin = TRUE)
minimizedC_1Select
#I get 3.541123, which is 0.007162 less than I got on the full set.
这可能看起来有些吹毛求疵，但它让我失去了 lp() 为我找到最佳解决方案的信心。
请帮助我理解为什么这是可能的？？？这种优化是我博士后的一个关键分析，我需要确信优化工作正常。难道是 lp() 函数中的错误吗？
鉴于
import pandas as pd
import pulp
item_ID = pd.RangeIndex(name='item_ID', start=1, stop=120)
df = pd.DataFrame(
index=item_ID,
data={
'criteria_1': (
0.19382357870646,
0.406093545012686, 0.26444538198799, 0.26601032196915, 0.582727750839455,
0.610218171520381, 0.278839154130233, 0.121920371729594, 0.394236226297326,
0.377841864658525, 0.120477145449607, 0.26254096134174, 0.320858353224026,
0.157895381699022, 0.367337498338429, 0.178897294673147, 0.206447474122835,
0.125249409058597, 0.0964062671575285, 0.155883926971779, 0.745589005311248,
0.271814782493108, 1, 0.709925503817279, 0.283967774188142, 0.465574672453751,
0.747720902276497, 0.261597766848332, 0.223547497818285, 0.312169636303741,
0.361688040733056, 0.33135717134122, 0.720315669627635, 0.597242543157505,
0.793399950297349, 0.422337180472638, 0.319528402753296, 0.430606430135989,
0.397399279889498, 0.343212756243173, 0.330215166243809, 0.266929589837542,
0.341647931849574, 0.337592426703038, 0.42473989909206, 0.308525738460027,
0.424706956637327, 0.357390032884661, 0.280438539204411, 0.409378774656271,
0.346474174849303, 0.791793745557103, 0.450584584087061, 0.262056880638506,
0.311923434799947, 0.448835397534517, 0.330430390281398, 0.141640071895463,
0.1929124019673, 0.176881794381289, 0.379488987395177, 0.741791953949916,
0.0370066289465928, 0.0768869958215097, 0.147257049396344, 0.570100734558947,
0.36424969224812, 0.254741112761445, 0.339564812834843, 0.305964896057886,
0.286239647689116, 0.326383438614336, 0.458683804448965, 0.567810482635859,
0.235202885065509, 0.729063336203758, 0.341599616249299, 0.153703714406256,
0.117457767195094, 0.134082379254345, 0.558969536898439, 0.286059793445029,
0.322705673615406, 0.396612822128083, 0.100616428459969, 0.156259239780615,
0.232564021060054, 0.104164041865814, 0.210723751509863, 0.192397806148102,
0.166759676123656, 0.310175982060811, 0.200003698801935, 0.193767171976952,
0.137411647758468, 0.369825867340157, 0.429786451982038, 0.202788665483821,
0.786777129845286, 0.321634986042802, 0.496148738072809, 0.170282669379121,
0.140613654358518, 0.155074004935589, 0.106219651041155, 0.121895751579215,
0.144999508752868, 0.278420842748903, 0.61995781054043, 0.860520490784782,
0.860520490784782, 0.894125146651717, 0.894125146651717, 0.894125146651717,
0.443148836322235, 0.120796860641858, 0.0224245646683504, 0.223040877540759,
0.195655525952297,
),
'criteria_2': (
0.17641981214023, 0.240848545191324,
0.20835265524648, 0.248767529787931, 0.451793498520131, 0.381683037411269,
0.241976585373557, 0.116782623551492, 0.20673566370936, 0.286801382192965,
0.070652688912388, 0.364572800178567, 0.269242816166067, 0.1189751136006,
0.323905107166701, 0.193872198256378, 0.147740819150117, 0.0860132098261335,
0.0580418616854518, 0.109446297259946, 0.500647366537576, 0.180393459509617,
0.653491503844082, 0.472660220201084, 0.163162249237616, 0.283984633127125,
0.415992733266123, 0.164994074648886, 0.167340730610985, 0.268800486663044,
0.32576183372859, 0.187746554917954, 0.513868883897277, 0.407993976147579,
0.520823834574429, 0.346647590611749, 0.249144414555891, 0.36143709685635,
0.275195240878429, 0.210744193768878, 0.276940989909035, 0.213850998663282,
0.189043772333223, 0.256031575641972, 0.267888778202805, 0.299825443704003,
0.232862594751094, 0.293319667536792, 0.165555116687722, 0.249950801232123,
0.185427153206608, 0.450646068867545, 0.283324056730209, 0.215590084378473,
0.168950797268736, 0.305193207638845, 0.190241720123152, 0.168636009700241,
0.140235480483511, 0.116295393379208, 0.254990237458096, 0.534546957175079,
0.0342844548026959, 0.147617877226165, 0.0856553598188811, 0.360464565082389,
0.26523128883826, 0.157202592030299, 0.189919356942208, 0.16741285463652,
0.184588573334462, 0.194498543981115, 0.290262033461934, 0.376277472517838,
0.167260290450748, 0.494939091832352, 0.312304468360028, 0.125687206435128,
0.124559809278627, 0.10118904396013, 0.436260473197599, 0.268812179666543,
0.28390152035242, 0.319129746519373, 0.0887131242082749, 0.0936087834963992,
0.146028350082448, 0.0852325359256434, 0.141593369478712, 0.142175267274303,
0.119637448691408, 0.213864087532372, 0.143729711242536, 0.240836706142566,
0.0857609795196696, 0.284704814576988, 0.321668930739399, 0.178845649197193,
0.893388564922643, 0.22274883820528, 0.43912198342029, 0.174430954851812,
0.118927528091718, 0.100615369508259, 0.0691456056815229, 0.0878417595367306,
0.133033845100036, 0.262412843717465, 0.320020039396849, 0.440301379519025,
0.440301379519025, 0.705078014946413, 0.705078014946413, 0.705078014946413,
0.478037536193209, 0.0604065918539912, 0.0112204438672376, 0.117238408833876,
0.131639362146937,
),
'itemWeight': (
151, 482, 309, 323, 648, 766,
309, 29, 385, 232, 114, 104, 326, 172, 69, 133, 130, 107, 222,
118, 657, 152, 1150, 723, 339, 516, 1126, 300, 247, 372, 286,
380, 935, 849, 1239, 571, 344, 639, 640, 476, 456, 336, 563,
536, 682, 463, 477, 518, 350, 695, 384, 953, 457, 284, 345, 549,
418, 196, 276, 217, 569, 657, 37, 78, 151, 613, 392, 280, 389,
320, 332, 366, 584, 619, 258, 903, 349, 160, 124, 141, 671, 282,
333, 428, 97, 57, 251, 62, 214, 194, 167, 316, 198, 231, 135,
345, 514, 188, 787, 359, 522, 168, 128, 165, 114, 129, 131, 92,
374, 307, 307, 307, 307, 307, 86, 73, 7, 109, 208,
),
'select': pulp.LpVariable.matrix(
name='select', indices=item_ID, cat=pulp.LpBinary,
),
},
)
prob = pulp.LpProblem(name='backpack', sense=pulp.LpMinimize)
firm_energy = pulp.lpDot(df['itemWeight'], df['select'])
prob.addConstraint(
name='min_firm_energy', constraint=firm_energy >= 5584,
)
第一个解决方案是
# Minimize criteria 1 on the full set
prob.setObjective(pulp.lpDot(df['criteria_1'], df['select']))
prob.solve()
assert prob.status == pulp.LpStatusOptimal
firm_energy = firm_energy.value()
df['select'] = df['select'].apply(pulp.value)
df = df.loc[df['select'] > 0.5, ['criteria_1', 'criteria_2', 'itemWeight']]
print(df)
Objective value: 3.48857926
Enumerated nodes: 0
Total iterations: 42
Time (CPU seconds): 0.03
Time (Wallclock seconds): 0.03
Option for printingOptions changed from normal to all
Total time (CPU seconds): 0.03 (Wallclock seconds): 0.03
criteria_1 criteria_2 itemWeight
item_ID
19 0.096406 0.058042 222
35 0.793400 0.520824 1239
39 0.397399 0.275195 640
43 0.341648 0.189044 563
44 0.337592 0.256032 536
45 0.424740 0.267889 682
46 0.308526 0.299825 463
50 0.409379 0.249951 695
61 0.379489 0.254990 569
第二个解决方案是
Objective value: 2.16717874
Enumerated nodes: 0
Total iterations: 0
Time (CPU seconds): 0.01
Time (Wallclock seconds): 0.01
Option for printingOptions changed from normal to all
Total time (CPU seconds): 0.02 (Wallclock seconds): 0.02
criteria_1 criteria_2 itemWeight
item_ID
19 0.096406 0.058042 222
27 0.747721 0.415993 1126
35 0.793400 0.520824 1239
39 0.397399 0.275195 640
43 0.341648 0.189044 563
45 0.424740 0.267889 682
50 0.409379 0.249951 695
57 0.330430 0.190242 418
鉴于不同的目标，这两种解决方案会有所不同，这是完全可以预料的。