Note that EUC_2D is rounded Euclidean distance. You can replace the GEODIST call with an expression that uses the ROUND and SQRT (or ROUND and EUCLID) functions.
... View more
The number of students it can handle depends on the number of courses, how much memory you have, how long you're willing to wait, and how close to optimal you want to get. Set covering is NP-hard, but in practice the MILP approach should definitely scale much better than brute-force.
... View more
The algorithm is deterministic in the sense that if you run it twice with the same settings on the same machine, you will get the same solution. But, in each new release of SAS/OR, changes in the underlying simplex algorithm, presolver, heuristics, cutting planes, branching strategies, etc. can alter which solution gets returned.
... View more
No, I just used the "have" data set as is. The READ DATA statement automatically removed the duplicate:
WARNING: Duplicate key <H,11> was read at observation 51.
By the way, you can use the CLP solver to find all optimal solutions:
solve with CLP / findallsolns;
for {s in 1.._NSOL_} put ({i in NAMES: Select[i].sol[s] > 0.5});
It turns out that there are four in this case:
{'C','G','H','I'} {'C','D','I','K'} {'C','G','I','K'} {'C','D','F','K'}
How did you solve it with SAS/STAT?
... View more
proc optmodel;
set <str,num> NAMES_VALUES;
read data have into NAMES_VALUES=[name value];
set NAMES = setof {<i,v> in NAMES_VALUES} i;
set VALUES = setof {<i,v> in NAMES_VALUES} v;
var Select {NAMES} binary;
min NumSelected = sum {i in NAMES} Select[i];
con Cover {v in VALUES}:
sum {<i,(v)> in NAMES_VALUES} Select[i] >= 1;
solve;
print {i in NAMES: Select[i].sol > 0.5} Select;
quit;
[1] Select C 1 D 1 F 1 K 1
This is known as a "set covering problem" in the literature.
... View more
The idea of the new constraint for the second solve is to force the first objective to be as good as in the first solve. See in particular the Objective_cut constraint in this example (but reverse the sense of the inequality since you are maximizing):
http://support.sas.com/documentation/cdl/en/ormpex/68157/HTML/default/viewer.htm#ormpex_ex19_toc.htm
... View more
Yes, adjusting the weights (objective coefficients) is a natural approach, but it requires you to come up with the "right" weights as input. An alternative approach is to use multiple objectives. The first objective is to maximize the contribution from the new items. After solving this, you add a constraint on this objective and then maximize the original objective in a second solve. This idea generalizes to an arbitrary number of objectives when you have some ordering on the importance of the objectives.
You can find several examples of this approach by searching for "multiple objectives" in the mathematical programming examples doc:
http://support.sas.com/documentation/cdl/en/ormpex/68157/HTML/default/viewer.htm#titlepage.htm
... View more
Yes, the .SOL suffix accesses the solution. The comparison to 0.5 is a safe way to pick up the variables that take value 1 (instead of 0) in the solution.
If there is more than one optimal solution, the MILP solver returns just the first one it finds. One way to find all optimal solutions is to use the CLP solver with the FINDALLSOLNS option:
solve with CLP / findallsolns;
for {s in 1.._NSOL_} do;
put s=;
for {<m,c> in MACHINE_COUNT: IsMachineCount[m,c].sol[s] > 0.5}
put m c area[m,c] profit[m,c];
end;
For the sample data, there is only one optimal solution.
... View more
Here it is in PROC OPTMODEL:
proc optmodel; set <str,num> MACHINE_COUNT; num area {MACHINE_COUNT}; num profit {MACHINE_COUNT}; read data have into MACHINE_COUNT=[machine count] area profit=total; set MACHINES = setof {<m,c> in MACHINE_COUNT} m; var IsMachineCount {MACHINE_COUNT} binary; max TotalProfit = sum {<m,c> in MACHINE_COUNT} profit[m,c]*IsMachineCount[m,c]; con OneCountPerMachine {m in MACHINES}: sum {<(m),c> in MACHINE_COUNT} IsMachineCount[m,c] = 1; con AreaBudget: sum {<m,c> in MACHINE_COUNT} area[m,c]*IsMachineCount[m,c] <= 600; solve; for {<m,c> in MACHINE_COUNT: IsMachineCount[m,c].sol > 0.5} put m c area[m,c] profit[m,c]; quit;
M1 2 100 43 M2 9 180 950 M3 7 315 550
... View more
You have stopped the solver early by setting MAXITER=100, and the resulting Infeasibility value is positive, meaning that some bounds or constraints are violated. Are you sure that the problem has a feasible solution?
... View more
I am able to replicate this behavior, and it turns out to be a known issue in the TSP solver when the objective value is large. It will be fixed in the next release, but as a workaround you can scale the input weights by dividing by 1000. Doing so averted the issue for me.
... View more
