Different cardinality of Y_N on some instances with epsilon-constraint available with MOA

[xgandibleux]

Two reproducible examples are provided in the attached code (instances 53-56 & 53-57).
Comment/uncomment the lines in the code for running the corresponding version:

biUFLP2026Oscar.zip

P.S.: This code is an extract from a longer code; that is why the various configurations (instances/algorithms) are enabled using comments.

Here the results obtained with

1. epsilon-constraint from MOA (with Gurobi 13)
2. TambyVanderpooten from MOA (with Gurobi 13)
3. epsilon-constraint homemade (with Gurobi 13)
4. homemade specific algorithm (without MIP solver); code not provided (too long!) => no numerical problem => the reference

Note: The elapsed time (in seconds) for ‘Epsilon-constraint MOA’ is also the least favourable.

instance 53-56

Epsilon-constraint MOA

  fnames         tOpt        #YN
  F53-56    74.951400        307

TambyVanderpooten MOA

  fnames         tOpt        #YN
  F53-56    65.987400        318

Epsilon-Constraint homemade

  fnames         tOpt        #YN
  F53-56    37.167200        318

Homemade specific algorithm (without MIP solver)

  fnames         tOpt        #YN
  F53-56     0.114000        318

ND_YN = [(4465, 21051), (4466, 21029), (4468, 20997), (4469, 20975), (4471, 20974), (4472, 20965), (4473, 20943), (4474, 20923), (4475, 20918), (4476, 20896), (4478, 20891), (4479, 20886), (4480, 20864), (4481, 20844), (4483, 20843), (4484, 20834), (4485, 20812), (4487, 20811), (4488, 20804), (4490, 20803), (4491, 20794), (4492, 20772), (4494, 20771), (4496, 20762), (4497, 20740), (4499, 20739), (4500, 20732), (4502, 20731), (4503, 20722), (4504, 20700), (4506, 20699), (4508, 20696), (4509, 20674), (4511, 20673), (4512, 20666), (4514, 20665), (4515, 20656), (4516, 20634), (4518, 20633), (4522, 20621), (4524, 20620), (4526, 20608), (4528, 20607), (4529, 20600), (4531, 20599), (4532, 20590), (4533, 20568), (4535, 20567), (4539, 20555), (4541, 20554), (4544, 20550), (4545, 20546), (4547, 20545), (4548, 20540), (4550, 20536), (4551, 20514), (4552, 20508), (4554, 20507), (4557, 20501), (4558, 20495), (4560, 20494), (4562, 20480), (4564, 20479), (4568, 20467), (4570, 20454), (4572, 20453), (4576, 20441), (4578, 20440), (4580, 20426), (4581, 20420), (4583, 20419), (4586, 20413), (4587, 20407), (4589, 20406), (4592, 20402), (4594, 20401), (4595, 20398), (4597, 20395), (4598, 20388), (4599, 20366), (4601, 20365), (4605, 20353), (4607, 20352), (4610, 20348), (4612, 20347), (4615, 20345), (4616, 20335), (4618, 20334), (4623, 20322), (4625, 20321), (4628, 20317), (4630, 20316), (4632, 20313), (4634, 20304), (4636, 20303), (4642, 20294), (4644, 20293), (4647, 20292), (4648, 20281), (4650, 20280), (4653, 20276), (4655, 20275), (4658, 20273), (4659, 20263), (4661, 20262), (4666, 20250), (4668, 20249), (4671, 20245), (4673, 20244), (4675, 20241), (4677, 20232), (4679, 20231), (4686, 20223), (4688, 20222), (4690, 20220), (4692, 20219), (4693, 20210), (4695, 20209), (4698, 20205), (4700, 20204), (4703, 20202), (4704, 20192), (4706, 20191), (4714, 20184), (4716, 20183), (4717, 20180), (4719, 20179), (4726, 20177), (4727, 20172), (4729, 20171), (4735, 20161), (4737, 20159), (4739, 20158), (4745, 20153), (4746, 20150), (4748, 20149), (4750, 20147), (4752, 20146), (4753, 20137), (4755, 20136), (4758, 20132), (4760, 20131), (4763, 20129), (4764, 20119), (4766, 20118), (4774, 20111), (4776, 20110), (4777, 20107), (4779, 20106), (4780, 20103), (4782, 20102), (4787, 20099), (4789, 20098), (4790, 20095), (4792, 20094), (4793, 20091), (4795, 20088), (4797, 20087), (4802, 20086), (4803, 20083), (4805, 20080), (4807, 20079), (4808, 20076), (4810, 20075), (4811, 20072), (4813, 20070), (4815, 20069), (4818, 20068), (4820, 20067), (4821, 20064), (4822, 20061), (4824, 20060), (4826, 20058), (4828, 20057), (4829, 20048), (4831, 20047), (4834, 20043), (4836, 20042), (4839, 20040), (4840, 20030), (4842, 20029), (4850, 20022), (4852, 20021), (4853, 20018), (4855, 20017), (4862, 20016), (4863, 20010), (4865, 20009), (4871, 19999), (4873, 19998), (4878, 19997), (4880, 19996), (4881, 19991), (4883, 19990), (4884, 19987), (4886, 19986), (4891, 19985), (4893, 19984), (4894, 19979), (4896, 19978), (4901, 19977), (4902, 19976), (4904, 19975), (4905, 19973), (4907, 19972), (4909, 19966), (4911, 19965), (4913, 19962), (4915, 19961), (4919, 19958), (4920, 19951), (4922, 19950), (4928, 19949), (4930, 19943), (4932, 19942), (4933, 19939), (4935, 19938), (4942, 19937), (4943, 19931), (4945, 19930), (4951, 19920), (4953, 19919), (4958, 19918), (4960, 19917), (4961, 19912), (4963, 19911), (4964, 19908), (4966, 19907), (4971, 19906), (4973, 19905), (4974, 19900), (4976, 19899), (4981, 19898), (4982, 19897), (4984, 19896), (4985, 19894), (4987, 19893), (4989, 19887), (4991, 19886), (4993, 19883), (4995, 19882), (4999, 19879), (5000, 19878), (5002, 19875), (5004, 19874), (5006, 19871), (5008, 19870), (5012, 19867), (5013, 19866), (5015, 19865), (5016, 19863), (5018, 19862), (5023, 19858), (5025, 19857), (5030, 19856), (5031, 19850), (5033, 19849), (5037, 18629), (5201, 18573), (5202, 18545), (5207, 18538), (5208, 18510), (5209, 18490), (5210, 18462), (5215, 18455), (5216, 18427), (5222, 18424), (5226, 18423), (5227, 18417), (5228, 18389), (5238, 18385), (5241, 18360), (5245, 18352), (5248, 18339), (5254, 18336), (5258, 18316), (5260, 18301), (5270, 18297), (5271, 18287), (5273, 18272), (5277, 18264), (5284, 18263), (5285, 18260), (5288, 18250), (5290, 18228), (5300, 18224), (5302, 18223), (5303, 18199), (5307, 18191), (5315, 18187), (5320, 18162), (5328, 18158), (5331, 18156), (5332, 18150), (5336, 18149), (5337, 18146), (5338, 18138), (5342, 18130), (5344, 18127), (5345, 18121), (5350, 18117), (5353, 18112), (5355, 18101), (5360, 18096), (5366, 18095), (5367, 18089), (5369, 18086), (5372, 18084), (5374, 18082), (5375, 18076), (5378, 18071), (5379, 18066), (5380, 18060), (5385, 18055), (5388, 18051), (5393, 18046), (5395, 18035), (5398, 7064)]

instance 53-57

Epsilon-constraint MOA

  fnames         tOpt        #YN
  F53-57    59.119500        173

TambyVanderpooten MOA

  fnames         tOpt        #YN
  F53-57    52.847600        173

Epsilon-Constraint homemade

  fnames         tOpt        #YN
  F53-57    30.911600        173

Homemade specific algorithm (without MIP solver)

  fnames         tOpt            #YN
  F53-57     0.140500            173

ND_YN = [(4465, 50235), (4466, 50189), (4468, 50150), (4471, 50140), (4472, 50130), (4473, 50101), (4474, 50091), (4475, 50062), (4478, 50052), (4479, 50042), (4480, 50037), (4481, 50003), (4484, 49993), (4486, 49978), (4489, 49946), (4492, 49936), (4493, 49930), (4494, 49921), (4496, 49920), (4497, 49911), (4498, 49905), (4501, 49873), (4504, 49863), (4506, 49848), (4509, 49838), (4514, 49837), (4515, 49825), (4518, 49801), (4520, 49800), (4521, 49791), (4523, 49776), (4526, 49766), (4531, 49765), (4532, 49753), (4535, 49743), (4537, 49728), (4540, 49718), (4545, 49717), (4547, 49710), (4548, 49705), (4549, 49696), (4551, 49695), (4552, 49686), (4555, 49676), (4560, 49673), (4561, 49663), (4564, 49653), (4566, 49638), (4569, 49628), (4574, 49627), (4576, 49620), (4577, 49615), (4578, 49606), (4580, 49605), (4581, 49596), (4586, 49590), (4588, 49588), (4589, 49583), (4591, 49578), (4592, 49573), (4595, 49567), (4597, 49552), (4600, 49542), (4603, 49539), (4607, 49534), (4608, 49529), (4609, 49520), (4611, 49519), (4612, 49510), (4615, 49507), (4619, 49502), (4620, 49497), (4622, 49492), (4623, 49487), (4626, 49484), (4629, 49478), (4631, 49463), (4634, 49453), (4639, 49452), (4641, 49445), (4642, 49440), (4643, 49431), (4645, 49430), (4646, 49421), (4651, 49420), (4653, 49413), (4654, 49408), (4656, 49403), (4657, 49398), (4662, 49397), (4664, 49390), (4665, 49387), (4667, 49380), (4672, 49379), (4675, 49369), (4682, 49362), (4687, 49361), (4690, 49351), (4695, 49350), (4700, 49349), (4702, 49342), (4703, 49339), (4705, 49332), (4710, 49331), (4713, 49321), (4720, 49314), (4725, 49313), (4728, 49303), (4739, 49293), (4744, 49292), (4746, 49286), (4751, 49285), (4754, 49275), (4759, 49274), (4762, 49268), (4766, 49266), (4767, 49263), (4769, 49256), (4774, 49255), (4777, 49245), (4784, 49238), (4789, 49237), (4792, 49227), (4803, 49222), (4808, 49216), (4815, 49209), (4818, 49203), (4823, 49198), (4826, 49192), (4833, 49185), (4838, 49184), (4841, 49174), (4854, 49170), (4857, 49163), (4864, 49156), (4869, 49155), (4872, 49145), (4885, 49141), (4892, 49138), (4896, 49136), (4900, 49127), (4906, 49126), (4913, 49119), (4915, 49118), (4916, 49116), (4921, 49108), (4931, 49098), (4937, 49097), (4944, 49090), (4949, 49089), (4952, 49079), (4965, 49075), (4972, 49072), (4974, 49071), (4976, 49070), (4980, 49061), (4993, 49057), (4995, 49052), (4996, 49050), (5003, 49043), (5008, 49042), (5011, 49032), (5024, 49028), (5031, 49026), (5035, 49023), (5037, 29244), (5398, 25165), (5905, 23833), (6136, 21293), (6857, 17765), (6980, 9575), (6992, 8167), (8598, 6247)]

[odow]

Here's a reproducible example:

using JuMP
import Gurobi
import MultiObjectiveAlgorithms as MOA

#!format: off
contents = """
90
30

28 13 34 83 8 75 69 38 51 7 22 93 82 47 9 69 30 96 1 46 69 75 88 69 49 81 53 79 58 30
19 79 5 91 16 99 91 49 55 99 26 29 25 24 18 97 50 15 18 97 49 32 6 0 20 37 67 82 15 46
76 38 88 60 84 17 32 20 99 20 30 45 85 8 3 59 23 13 10 11 22 29 41 44 52 54 15 57 58 87
65 89 66 19 75 95 86 56 0 7 85 70 85 0 82 76 67 97 76 62 18 90 19 30 68 55 3 28 25 8
7 78 62 96 26 24 44 42 91 67 37 98 36 49 86 45 83 10 77 68 41 30 24 87 45 29 21 22 88 81
78 22 8 74 14 86 38 21 84 67 41 0 56 14 76 72 68 14 64 25 40 30 71 19 4 47 99 47 88 79
75 37 71 84 69 38 80 7 72 97 6 38 41 97 71 55 63 25 44 96 13 81 12 70 1 47 55 14 39 98
57 39 65 90 78 37 7 77 63 37 83 53 45 30 54 94 93 99 94 58 97 34 26 79 99 8 55 53 0 40
84 88 12 98 97 97 46 76 51 37 19 84 11 11 60 20 5 16 31 6 98 88 87 28 14 64 53 89 42 88
83 81 16 14 39 28 44 87 94 53 41 9 50 85 84 7 32 92 81 84 95 14 43 2 44 30 97 21 75 92
57 24 73 98 75 67 19 83 16 53 15 73 27 24 5 7 14 96 67 35 28 9 89 40 33 51 73 48 4 79
17 23 80 49 62 55 65 29 33 96 60 56 75 96 70 57 85 47 99 49 92 40 54 93 21 84 5 55 53 45
79 7 76 19 78 68 66 23 48 75 61 80 58 25 15 37 43 24 38 32 26 55 62 6 28 33 92 22 36 2
35 38 74 18 99 47 3 4 23 77 48 72 80 27 27 54 49 65 29 83 58 16 63 21 50 33 80 16 6 12
35 45 45 99 53 66 81 1 95 96 95 95 52 77 66 10 22 6 62 6 23 35 91 87 68 69 56 29 0 23
61 91 50 5 81 55 91 49 67 7 77 0 69 62 5 44 94 80 31 12 16 37 29 24 30 59 84 39 3 5
40 25 58 75 63 71 14 86 72 5 47 22 61 92 53 67 14 13 37 68 81 68 44 93 63 33 16 78 38 91
36 77 13 87 94 61 94 98 92 29 94 15 64 30 42 62 80 2 48 23 67 86 33 38 54 61 53 91 39 19
44 97 24 66 93 66 63 25 95 10 32 74 65 4 6 45 3 18 7 66 35 99 53 25 85 54 26 85 36 68
37 86 4 50 62 97 13 10 61 22 59 96 27 67 2 36 10 12 11 86 12 62 65 62 64 55 70 15 14 63
62 73 97 13 4 59 63 0 69 60 80 87 11 14 43 8 35 20 63 6 22 8 98 97 89 24 66 26 57 86
45 47 91 62 55 64 15 50 69 11 18 50 10 37 13 87 19 51 4 4 98 29 76 45 93 84 20 89 25 69
53 0 22 43 92 31 92 33 95 68 42 68 76 5 42 66 65 7 67 7 61 82 99 15 98 74 45 39 29 53
5 92 98 57 17 14 49 17 43 43 89 72 70 16 22 42 63 47 1 33 74 38 68 88 97 28 0 89 27 83
50 5 67 86 70 24 79 76 52 2 86 47 27 40 60 4 96 71 59 36 90 92 0 64 98 97 72 60 81 0
38 43 79 27 72 19 81 37 30 0 7 7 51 28 25 68 48 85 96 94 16 66 39 75 77 59 35 30 50 34
24 38 96 50 70 90 79 40 81 97 63 13 28 98 16 98 84 68 91 17 85 4 16 51 89 43 12 50 74 46
11 1 99 48 45 39 40 61 45 77 55 72 47 94 40 81 6 99 92 69 67 64 84 89 41 83 20 25 84 20
20 49 77 45 61 92 52 51 66 95 27 38 24 99 24 78 79 5 95 3 23 18 81 93 76 27 71 36 44 14
48 7 92 84 23 75 53 52 8 31 87 44 78 12 44 81 9 57 93 63 6 11 36 78 60 76 5 88 85 62
12 72 29 4 16 38 70 34 3 24 27 27 3 49 52 64 9 88 90 73 41 87 10 55 78 31 55 90 75 35
59 94 10 28 28 56 32 42 89 93 23 23 45 96 73 43 99 44 48 58 29 27 90 54 27 94 79 75 40 18
53 24 69 43 59 79 19 66 89 66 98 51 13 81 24 94 18 53 69 76 25 96 61 72 23 80 24 20 58 24
12 45 64 0 89 1 17 88 48 89 48 25 65 41 59 46 47 88 21 97 10 69 40 74 96 18 29 27 18 53
17 13 92 62 98 5 91 40 78 86 36 38 80 76 5 20 31 86 22 44 25 85 68 7 32 32 14 26 10 96
73 42 46 90 24 65 1 69 46 10 70 70 78 77 67 15 83 80 88 83 81 35 34 21 89 58 71 74 73 16
81 32 4 68 20 22 76 55 84 16 22 43 61 5 39 26 5 85 10 39 73 37 78 40 12 99 16 65 66 76
1 60 64 22 71 38 0 94 40 37 17 62 88 48 51 24 62 62 95 68 48 46 14 67 90 41 86 6 91 56
62 78 1 86 94 94 86 93 34 7 29 20 32 15 9 15 77 26 61 13 55 88 6 81 28 8 19 26 42 21
53 33 40 87 48 75 18 20 5 1 55 79 82 19 20 76 50 15 13 77 22 65 10 13 42 51 14 11 91 85
28 16 41 83 15 79 92 64 91 13 37 59 81 46 61 53 34 37 74 97 69 11 8 55 97 53 63 96 60 46
52 16 53 55 94 70 40 96 56 45 83 27 37 97 18 61 51 47 90 82 42 90 88 30 52 78 65 58 22 82
39 99 75 19 86 92 45 37 3 48 36 63 70 62 9 71 57 93 59 27 62 89 13 2 54 0 64 83 73 22
22 7 9 73 54 2 59 77 29 8 28 12 2 20 43 56 5 70 74 31 18 29 85 27 47 23 81 58 23 72
90 82 17 98 16 91 9 73 61 49 79 86 75 31 97 72 3 91 26 9 32 79 83 90 58 57 99 20 25 6
86 4 98 15 4 13 91 89 82 49 47 41 25 55 41 16 37 27 60 92 21 36 80 57 33 51 38 33 24 42
73 14 80 91 88 41 34 38 49 24 37 49 28 77 97 77 56 45 14 52 37 25 87 28 53 6 69 62 43 99
77 16 50 18 7 99 63 23 2 88 94 66 64 98 80 74 22 95 89 65 89 66 67 99 72 89 70 80 17 73
54 95 9 49 18 22 42 52 38 66 55 10 14 7 75 26 38 41 27 30 44 88 0 43 95 63 69 57 40 54
27 41 11 49 71 28 73 98 35 26 36 17 85 80 84 52 5 66 98 79 36 85 60 93 57 11 76 12 21 96
53 18 71 28 16 85 10 20 48 85 6 51 94 64 35 3 64 26 15 57 17 82 71 41 13 27 45 56 76 80
20 2 89 78 45 0 32 16 76 71 11 87 52 15 58 38 96 14 1 70 85 43 13 34 56 59 15 6 20 14
71 45 5 99 12 60 67 27 81 49 12 7 66 77 42 56 85 13 6 77 26 42 23 71 65 14 9 81 13 9
12 79 50 26 65 42 72 6 81 86 49 84 64 34 56 96 17 72 44 5 53 87 58 17 58 95 13 91 48 26
91 86 27 99 12 84 37 16 6 75 54 55 81 10 74 37 55 51 94 12 14 72 74 68 1 89 43 71 58 27
92 94 68 53 42 76 66 24 5 34 35 43 74 20 83 11 83 82 77 16 62 81 86 12 51 74 46 67 54 63
62 77 54 67 0 92 7 66 34 91 4 39 68 4 54 70 22 62 30 13 69 32 83 37 60 69 19 88 68 79
92 36 47 87 49 2 77 54 46 83 47 74 14 6 98 68 32 0 27 31 53 54 16 9 94 96 50 27 59 23
30 69 78 63 98 96 88 41 27 55 59 92 47 4 68 36 6 64 67 8 87 78 89 10 39 22 4 26 78 11
99 23 79 97 60 19 58 34 82 1 14 81 16 14 89 52 43 63 58 36 42 99 52 54 73 65 92 14 97 50
78 92 19 59 49 43 9 86 33 25 41 81 36 83 61 26 37 33 67 49 5 46 65 79 32 3 37 81 69 96
28 47 95 79 44 34 60 3 17 49 90 83 71 60 28 79 13 57 66 5 16 87 85 74 65 62 1 63 13 3
98 45 27 50 86 26 50 79 19 90 1 98 56 16 79 96 61 57 64 93 63 67 13 96 22 17 97 66 90 60
31 53 41 5 99 45 17 29 60 57 15 33 2 28 20 24 68 26 43 69 79 74 25 60 32 30 25 89 37 13
94 17 20 33 0 89 19 76 65 23 47 58 28 81 84 39 31 98 41 68 16 36 95 94 60 67 94 69 91 19
86 30 67 45 6 27 10 76 38 39 20 90 29 3 20 97 35 36 99 22 0 19 59 45 25 3 88 15 68 25
0 57 68 49 25 50 16 95 42 12 79 85 82 51 77 44 41 64 64 26 95 73 45 56 86 51 55 5 39 70
72 36 21 69 31 6 46 29 72 80 5 10 39 22 61 70 7 60 27 81 6 25 51 18 72 35 49 77 42 57
54 44 72 75 6 35 45 42 65 71 98 2 43 51 90 10 78 53 85 61 99 63 19 50 61 18 79 92 34 11
20 74 85 89 84 39 94 57 5 2 82 58 13 64 34 83 74 64 66 48 25 87 64 44 83 24 79 26 61 44
63 9 93 24 94 98 71 60 12 51 28 38 57 64 37 45 94 20 10 55 69 47 89 8 16 75 3 76 19 87
10 85 95 96 42 29 57 9 44 96 71 52 56 4 9 54 88 6 74 45 88 9 40 81 89 22 34 24 8 37
57 37 19 92 24 62 18 66 57 1 63 36 67 10 53 61 21 87 81 88 63 7 72 4 46 26 83 58 82 74
48 46 30 6 78 18 82 66 48 69 91 94 37 99 83 94 7 72 33 14 32 8 84 23 0 75 62 99 79 75
12 29 98 42 36 16 76 99 33 31 30 22 65 52 23 32 90 90 31 6 50 75 52 69 95 76 83 12 76 59
35 61 61 7 56 74 34 79 99 49 80 51 38 68 96 81 27 15 40 0 58 39 36 8 53 47 91 18 6 57
86 8 54 33 52 46 45 93 42 2 34 62 62 85 18 4 14 27 2 54 77 46 47 48 16 37 45 3 5 66
26 11 1 89 89 39 94 98 9 53 43 83 63 11 53 59 90 79 59 80 51 87 26 63 81 16 75 83 36 75
3 6 76 25 40 88 42 57 81 34 16 17 76 12 71 50 62 68 47 99 79 73 25 82 99 6 63 32 61 56
33 80 88 91 59 7 35 34 64 92 94 43 59 49 45 71 36 12 36 73 55 25 38 80 22 33 97 48 24 87
82 60 40 17 99 39 55 21 28 97 52 83 1 30 54 18 13 35 40 10 56 2 54 72 6 17 90 69 4 76
15 81 6 91 62 64 11 37 14 83 72 88 53 94 53 17 38 1 4 70 59 36 40 50 58 8 69 42 26 45
89 97 11 13 64 36 0 78 35 41 63 65 30 63 63 22 89 44 75 75 4 36 69 61 43 80 55 58 19 57
74 48 10 34 13 91 45 76 55 94 17 71 0 94 76 19 25 92 34 67 49 26 58 84 46 39 54 22 3 2
62 4 27 91 9 28 41 27 2 82 25 32 40 15 97 51 98 94 32 61 98 61 71 41 74 56 62 0 98 73
37 72 14 68 26 21 15 35 42 36 48 20 7 85 24 29 99 73 90 70 24 12 77 16 73 15 20 89 88 56
37 96 65 58 2 77 61 13 42 31 86 39 55 45 98 32 21 36 25 49 62 69 90 61 54 41 10 45 25 9
95 98 69 25 66 1 64 99 71 70 90 8 65 62 58 7 92 26 24 26 68 25 30 59 68 51 97 62 63 34
78 38 51 95 27 56 96 1 49 48 42 28 45 74 96 35 53 46 81 5 58 55 93 1 25 45 43 57 61 21
34 90 32 86 23 99 81 56 80 8 17 76 9 49 80 56 17 92 95 95 55 82 86 49 41 32 86 79 51 83

46 76 83 21 64 45 52 70 87 88 35 7 99 82 72 77 36 15 21 6 23 56 80 54 27 75 58 9 21 87
38 41 89 35 96 44 11 26 49 70 14 96 62 91 65 54 28 70 68 45 4 23 62 34 67 89 47 76 24 62
90 52 88 33 72 79 4 55 91 9 92 29 32 97 30 69 53 89 5 1 72 58 5 0 38 0 16 69 20 64
62 13 61 74 4 66 62 63 64 82 10 45 66 71 56 76 0 69 8 89 37 64 96 4 78 7 25 39 97 97
17 94 8 6 23 60 81 87 38 85 79 82 57 4 81 26 61 10 33 1 11 22 31 7 0 77 27 38 80 55
6 77 67 14 95 64 99 89 91 95 90 84 2 43 10 73 67 25 82 67 86 53 78 22 70 35 53 13 2 23
49 70 61 20 62 65 57 92 49 3 76 46 18 43 33 82 31 58 80 7 18 9 16 93 64 94 9 4 37 91
5 18 63 21 5 43 56 78 23 72 70 14 53 52 33 85 23 45 70 80 99 15 25 90 79 69 56 5 74 27
43 30 83 9 38 63 3 63 60 78 24 67 93 0 11 75 59 78 67 9 60 77 26 96 23 55 28 9 80 93
69 71 74 94 33 13 78 69 43 8 49 82 86 20 87 6 15 37 27 29 13 80 24 5 86 1 91 42 14 20
97 62 69 59 44 85 2 76 69 29 39 4 60 0 37 52 54 46 0 10 83 89 55 94 66 38 29 88 70 80
88 89 3 83 21 67 78 53 81 73 88 49 25 88 87 31 0 65 36 99 78 25 81 51 35 16 79 66 27 18
63 93 99 83 32 94 48 25 10 84 14 10 94 52 61 97 88 69 99 41 6 12 32 65 88 50 46 42 43 97
75 57 30 94 94 47 51 2 47 21 89 11 91 21 34 82 30 74 80 0 55 40 78 99 20 68 81 64 28 95
20 54 94 76 96 90 19 8 65 79 84 95 71 7 51 71 40 94 37 69 44 2 88 5 98 41 71 27 47 12
67 32 62 82 25 50 45 80 18 72 15 65 4 42 24 88 82 55 30 66 13 32 19 44 17 55 50 88 91 90
86 55 2 35 5 37 36 59 24 55 34 23 78 67 21 12 29 11 20 97 10 90 9 23 5 88 58 90 54 55
56 59 7 98 16 19 71 97 15 88 37 98 7 28 65 60 25 10 75 76 48 50 67 76 2 4 65 89 26 91
65 24 18 92 32 86 45 28 68 56 76 27 52 85 77 31 25 85 79 96 64 25 1 98 80 50 93 40 21 93
35 17 74 47 1 99 91 9 70 34 90 23 55 69 98 82 82 55 42 50 19 82 8 43 58 54 9 58 4 4
57 39 98 7 8 39 3 48 28 95 20 41 16 27 13 14 64 49 58 7 37 32 54 39 30 56 50 61 3 60
82 71 18 57 25 81 30 87 95 60 96 18 76 82 14 12 32 65 99 39 40 68 65 74 67 90 63 33 55 92
95 35 97 24 9 71 24 36 41 41 22 10 60 92 65 18 34 42 19 31 15 95 61 3 20 86 15 13 54 85
99 47 6 80 43 46 96 95 3 53 74 21 2 28 95 75 62 42 15 95 6 23 84 55 53 55 27 45 28 40
58 65 58 60 41 6 36 29 8 37 68 87 0 12 26 2 88 66 91 75 80 69 44 61 38 45 46 47 53 97
8 59 42 67 54 93 92 45 17 68 32 96 23 78 28 68 60 69 36 5 25 70 39 76 13 66 72 87 68 81
96 53 34 13 84 30 60 35 36 44 51 61 17 65 72 42 98 9 42 24 47 77 86 6 88 48 11 65 40 94
46 40 92 92 54 98 72 33 96 8 37 67 23 14 75 27 14 77 91 23 84 18 40 8 42 95 7 32 63 90
58 71 6 86 14 60 92 67 6 98 31 63 45 96 46 36 76 58 51 59 21 64 72 53 46 64 13 77 65 96
17 77 3 14 71 60 68 71 46 24 98 89 81 80 95 30 52 39 52 27 79 45 39 55 63 89 6 57 63 22
15 20 44 68 12 14 64 83 99 5 87 32 67 12 13 70 8 85 0 44 96 93 95 72 31 85 91 38 72 38
8 31 96 5 37 7 83 51 6 57 85 10 57 6 48 16 40 71 91 95 71 72 63 11 94 54 20 11 61 69
6 2 11 32 34 68 15 46 77 1 15 63 44 2 74 15 83 91 26 53 39 10 69 51 67 24 70 88 64 55
52 5 83 86 84 85 39 43 19 40 13 27 9 59 25 62 30 87 26 69 80 15 29 97 23 14 84 70 15 49
58 8 17 22 88 68 88 79 9 80 13 48 73 90 4 88 17 39 88 99 44 26 62 86 28 42 83 99 50 77
17 91 31 30 81 53 16 70 30 32 28 49 85 34 0 39 14 68 43 51 86 86 12 79 81 24 86 47 24 46
65 68 67 50 52 43 44 85 73 54 67 94 63 36 47 69 95 16 53 0 61 81 35 38 17 87 92 18 40 32
44 3 86 56 51 39 20 42 78 59 79 27 6 40 70 42 35 26 24 56 32 61 68 79 20 99 58 52 0 85
14 31 66 20 33 46 55 53 76 85 31 71 61 35 99 81 90 89 5 83 12 87 60 11 94 65 99 66 44 17
58 73 15 0 34 53 86 38 63 65 93 0 22 72 59 69 50 51 50 13 41 24 44 27 46 89 7 22 3 93
95 68 68 59 39 8 17 64 87 20 57 28 80 79 44 68 23 61 9 20 62 69 47 37 68 87 96 12 9 4
37 88 41 34 79 50 67 45 6 17 39 75 18 76 84 85 63 18 15 84 76 83 25 28 52 13 92 72 16 79
39 31 79 13 25 84 90 82 66 15 18 83 4 78 25 22 88 45 19 38 7 55 97 66 25 80 9 52 84 76
8 67 73 89 82 86 99 32 49 22 87 40 91 35 8 95 56 57 7 55 27 97 82 33 69 27 30 29 92 54
73 87 76 34 20 32 70 78 27 31 49 66 69 61 88 54 35 86 87 55 98 77 73 19 35 18 37 50 99 1
1 26 52 86 18 15 29 82 41 16 84 78 36 38 38 34 93 23 31 2 94 65 49 42 17 84 71 53 94 52
73 34 58 80 71 44 34 29 81 26 69 82 55 13 0 95 3 32 17 31 4 85 48 22 85 46 93 25 5 23
80 76 82 86 10 31 43 27 22 71 96 21 98 11 38 16 84 22 61 48 91 71 22 72 21 34 69 53 8 30
66 56 86 99 38 33 25 1 42 90 76 17 27 89 48 93 39 11 75 33 94 89 73 42 14 90 83 94 98 95
43 43 90 21 50 25 43 66 96 14 2 83 92 23 65 21 10 76 77 64 12 72 70 81 41 46 69 58 3 71
6 71 52 60 27 29 59 87 82 94 39 1 18 46 61 25 38 73 51 57 81 82 79 14 44 67 98 91 38 90
48 16 61 46 62 35 37 35 47 50 29 43 95 98 47 13 75 37 6 70 9 93 92 16 13 63 56 6 71 89
34 88 82 59 70 53 76 75 90 35 99 8 40 57 26 42 6 8 23 54 69 3 99 92 61 57 95 51 31 76
9 57 29 50 69 10 74 93 65 40 68 66 47 83 60 97 18 79 73 50 93 51 61 31 4 19 50 39 56 42
82 71 86 15 56 65 71 58 49 32 80 48 65 10 70 29 20 40 82 57 87 48 72 82 51 80 86 92 33 40
77 29 7 3 99 92 11 12 50 71 10 5 41 70 82 88 98 28 34 82 51 29 49 3 43 81 47 44 78 85
92 78 85 34 89 99 67 16 48 65 63 99 4 14 42 32 36 66 8 93 5 35 82 55 20 11 90 60 90 81
84 26 24 13 57 9 99 6 33 25 85 90 68 69 18 28 52 14 51 51 27 65 20 28 55 97 21 57 96 14
58 21 87 98 35 50 18 37 92 87 66 57 99 43 22 90 72 82 13 51 64 91 27 17 54 8 73 22 35 20
39 16 65 57 38 38 40 32 41 29 9 22 56 59 28 74 78 50 23 81 39 33 22 78 32 49 66 39 65 3
7 70 99 17 61 51 64 39 68 48 49 26 79 9 15 79 72 24 88 16 64 94 19 5 83 45 13 94 1 1
80 18 40 70 52 50 32 33 67 47 58 27 11 99 15 62 82 73 90 29 6 35 24 59 15 66 18 69 89 11
91 93 92 46 1 76 73 27 0 98 18 65 60 41 46 48 17 13 18 99 4 13 79 34 67 81 63 70 5 67
29 91 53 30 99 76 17 34 38 40 22 11 66 48 34 4 22 4 69 10 5 21 96 96 55 19 94 32 70 25
36 0 48 54 91 45 23 97 74 84 17 60 92 1 31 7 51 72 54 28 44 21 53 7 9 86 83 77 42 51
19 96 13 69 12 51 95 88 6 7 22 57 82 38 39 66 7 9 94 43 6 8 98 28 92 30 47 89 5 73
84 45 66 99 49 19 33 60 39 25 17 4 69 78 1 4 29 72 61 72 57 59 91 64 75 31 77 68 75 97
66 54 27 87 40 8 68 36 74 91 84 40 48 95 87 62 42 70 64 51 34 74 44 1 69 45 5 50 85 4
18 99 8 43 16 18 44 50 5 51 45 83 79 35 12 88 7 16 72 25 81 1 40 42 71 96 50 30 1 17
18 25 65 73 70 46 32 45 53 6 5 32 4 4 56 29 48 99 20 43 54 38 53 90 67 62 62 9 92 28
65 87 0 22 62 90 91 49 91 45 17 15 26 95 58 53 33 57 17 47 81 34 52 61 90 52 76 73 57 50
0 75 85 27 80 92 18 16 9 14 45 58 58 67 35 94 63 57 17 72 5 56 3 73 27 20 36 86 2 68
2 71 31 41 33 24 30 37 2 4 58 86 82 96 73 8 10 26 23 74 97 43 19 54 61 38 38 26 74 61
53 97 58 66 86 23 68 83 45 62 46 4 74 89 26 34 32 40 41 32 89 93 51 59 92 74 92 98 44 67
19 13 9 61 93 70 17 47 35 23 43 77 41 55 88 25 38 16 78 17 29 94 63 28 41 24 78 54 91 14
1 11 24 44 26 19 89 61 25 72 65 83 66 99 39 90 31 79 13 54 27 50 85 35 94 28 17 59 57 37
19 40 65 6 80 24 33 84 38 60 57 82 73 18 79 46 53 33 32 13 84 26 70 4 31 23 80 69 13 2
30 71 92 21 89 80 11 89 31 22 43 29 11 95 64 0 72 44 58 2 19 69 18 76 69 98 0 65 66 57
49 11 24 6 91 94 25 39 77 44 94 56 17 72 31 57 25 19 57 22 89 4 19 69 19 19 62 7 38 12
48 27 32 58 87 1 56 91 23 71 76 60 73 63 85 37 12 43 31 83 69 14 42 41 56 15 26 32 60 59
98 58 67 45 54 34 91 16 90 33 32 43 39 74 88 72 82 12 96 58 43 13 68 59 75 7 52 89 16 65
45 39 48 36 16 7 95 46 33 17 54 35 99 0 36 94 36 72 56 30 74 37 6 53 36 0 5 87 30 51
0 30 75 84 64 26 35 36 17 19 32 75 73 2 71 69 72 91 84 1 64 62 83 46 54 60 79 85 12 58
10 44 26 10 81 87 34 45 11 88 72 95 30 66 30 35 91 55 86 6 77 56 74 24 13 78 3 10 27 67
35 91 9 86 76 52 67 97 56 56 81 47 96 32 94 69 72 24 1 44 56 45 29 87 65 76 98 58 60 95
33 3 75 47 44 79 71 73 11 15 42 63 31 27 10 8 14 70 4 51 44 1 93 84 30 97 29 15 24 39
13 26 72 56 94 80 31 2 66 55 62 99 12 11 94 71 24 16 2 57 94 94 57 71 46 63 42 48 65 85
23 5 38 29 46 92 15 38 84 15 52 49 47 60 96 90 52 52 30 66 95 26 70 17 79 77 0 92 1 52
87 70 75 69 99 48 77 84 21 59 13 57 56 72 62 65 39 28 35 74 10 86 53 74 21 83 47 25 74 45
17 79 18 95 12 73 42 46 11 6 57 73 31 47 42 8 79 35 94 99 23 70 28 22 59 6 97 42 95 98

3815 4854 2353 4496 3207 4876 1405 3058 2121 5204 1585 1236 4512 2693 2734 4429 794 4771 4559 3309 2544 2085 1967 2946 3700 1897 716 3449 1897 5064

17060 23824 9612 8793 12220 4428 26833 22103 23918 18701 13140 11901 20608 23072 11974 16471 14465 4699 10652 26019 3447 19181 15127 26158 8842 24711 2273 10614 9804 26456
"""
#!format: on

mutable struct Instance
    fname::String
    nI::Int
    nJ::Int
    c1::Matrix{Int}
    c2::Matrix{Int}
    r1::Vector{Int}
    r2::Vector{Int}

    function Instance(f::IO)
        nI = parse(Int, readline(f))
        nJ = parse(Int, readline(f))
        _ = readline(f)
        c1 = Matrix{Int}(undef, nI, nJ)
        for i in 1:nI
            c1[i,:] .= parse.(Int64, split(readline(f)))
        end
        _ = readline(f)
        c2 = Matrix{Int}(undef, nI, nJ)
        for i in 1:nI
            c2[i,:] .= parse.(Int64, split(readline(f)))
        end
        _ = readline(f)
        r1 = parse.(Int, split(readline(f)))
        _ = readline(f)
        r2 = parse.(Int, split(readline(f)))
        @assert length(r1) == nJ
        @assert length(r2) == nJ
        return new(fname, nI, nJ, c1, c2, r1, r2)
    end
end

function main(io::IO, algorithm::MOA.AbstractAlgorithm)
    data = Instance(io)
    model = Model(() -> MOA.Optimizer(Gurobi.Optimizer))
    set_attribute(model, MOA.Algorithm(), algorithm)
    @variable(model, x[1:data.nI, 1:data.nJ], Bin)
    @variable(model, s[1:data.nJ], Bin)
    @expression(model, f1, sum(data.c1 .* x) + data.r1' * s)
    @expression(model, f2, sum(data.c2 .* x) + data.r2' * s)
    @objective(model, Min, [f1, f2])
    @constraint(model, [i in 1:data.nI], sum(x[i,:]) == 1)
    @constraint(model, [i in 1:data.nI,j in 1:data.nJ], x[i, j] <= s[j])
    start_time = time()
    optimize!(model)
    elapsed_time = round(time() - start_time; digits = 4)
    Y_N = Vector{Int}[
        round.(Int, objective_value(model; result)) for
        result in 1:result_count(model)
    ]
    return Y_N, elapsed_time
end

io = IOBuffer(contents)
seekstart(io)
epsilon_constraint = main(io, MOA.EpsilonConstraint())
tamby_vanderpooten = main(io, MOA.TambyVanderpooten())

[odow]

Explanation for the missing points

The missing points are:

which is suspiciously similar to the MIPGap issue in #191.

Indeed, if we set:

set_attribute(model, "MIPGap", 0.0)

then we get, with EpsilonConstraint, the expected 318 solutions:

----------------------------------------------
termination_status: OPTIMAL
result_count: 318

Total solve time:          6.54108e+01
Time spent in subproblems: 6.46072e+01 (99%)
Number of subproblems:     639
----------------------------------------------

Explanation for the difference in runtime between our EpsilonConstraint and your custom one

We do a two-stage solve to ensure we don't have any weakly dominated points:

MultiObjectiveAlgorithms.jl/src/algorithms/EpsilonConstraint.jl

Lines 124 to 139 in b5bd81f

	# First-stage solve: minimize f₂: f₁ <= u₁ - ε
	MOI.set(inner, MOI.ObjectiveFunction{typeof(f2)}(), f2)
	MOI.set(inner, MOI.ConstraintSet(), ci_1, MOI.LessThan(u_1 - c_1 - ε))
	MOI.set(inner, MOI.ConstraintSet(), ci_2, MOI.LessThan(u_2 - c_2))
	optimize_inner!(model)
	if !_is_scalar_status_optimal(model)
	break
	end
	# Second-stage solve: minimize f₁: f₂ <= f₂^*
	f_2_opt = MOI.get(inner, MOI.ObjectiveValue())::Float64
	MOI.set(inner, MOI.ObjectiveFunction{typeof(f1)}(), f1)
	MOI.set(inner, MOI.ConstraintSet(), ci_2, MOI.LessThan(f_2_opt - c_2))
	optimize_inner!(model)
	if !_is_scalar_status_optimal(model)
	break
	end

See #128 and #172.

Your implementation does only a single solve.

There's approximately a 2x performance difference between the two implementations, which explains the difference.

[odow]

So I put this down to: things are correct and working as expected.

There is just a missing area of the literature where the algorithms assume exact MIP solvers and yet we use approximate ones with tolerances.

[odow]

Here's a case where TV fails because of constraint tolerances: #196