Hi,
I have what seems like a simple problem, but I'm not quite sure how to
address it.
I have complex model that I've simplified below. Basically I have a MIP
problem where I would like to have
- three elements in a row and
- I would like the non-zero rows optimally spaced.
Seems like it should be simple. (at the bottom is a link to glpk.js)
Thanks,
Eric
# How can I optimize spacing and force variables to be adjacent?# given a
(binary) 5x5 matrix Y# in 2 rows, set 3 locations where the 3 in each row
are adjacent then optimize for spacing of rows to ideally be# s rows
apart. # so: 6 locations are set, # rows have either 3 or 0 (so there
will be 2 non-zero rows)# force the 3 in a given row to be adjacent.#
space those rows optimally.## My optimization for spacing is piecewise
linear: cost = -3s/3 + 3 for s <= 3, 1/4s for s > 3# Approach: create a
binary Rows_With_Data and use it to view rows only# one optimal solution
where s is 3# 1 1 1 0 0# 0 0 0 0 0# 0 0 0 0 0# 0 1 1 1 0# 0 0 0 0 0# # I
know I can add a constraint to acheive row spacing, but this is a
simplification of my real problem (there will be many rows# to be optimally
spaced not just one).set I := 1..5;
var Y{I,I}, binary;var Rows_With_Data{I}, binary; # does this row have
any data?
# only 3 in a row of 5s.t. Three_max_per_row {i in I}: sum{j in I }
Y[i,j] <= 3; # allows 2 or 1 in a row (bad)
# only 2 rows have datas.t. Two_rows_have_data: sum{i in I}
Rows_With_Data[i] = 2;
# only allow 6 total w/in matrixs.t. Six_total: sum{i in I, j in
I}(Y[i,j]) = 6;
# if a row has any, then it has 3, uses Rows_With_Data as a booleans.t.
Three_in_one_row{i in I}: sum{j in I} (Y[i,j]) = Rows_With_Data[i]*3;
# Now enforce sequence# to do...
# minimize cost# ???
solve;
display I;display Y;display:Rows_With_Data;display
Six_total_in_two_rows2;display
Six_total_in_two_rows3;data;
end;
Here's the link to glpk.js solver.
https://www3.nd.edu/~jeff/mathprog/mathprog.html?model=%0A%23%20How%20can%20I%20optimize%20spacing%20and%20force%20variables%20to%20be%20adjacent%3F%0A%23%20given%20a%20(binary)%205x5%20matrix%20Y%0A%23%20%20%20in%202%20rows%2C%20set%203%20locations%20where%20the%203%20in%20each%20row%20are%20adjacent%20then%20optimize%20for%20spacing%20of%20rows%20to%20ideally%20be%0A%23%20%20%20s%20rows%20apart.%20%0A%23%20%20%20so%3A%206%20locations%20are%20set%2C%20%0A%23%20%20%20rows%20have%20either%203%20or%200%20(so%20there%20will%20be%202%20non-zero%20rows)%0A%23%20%20%20force%20the%203%20in%20a%20given%20row%20to%20be%20adjacent.%0A%23%20%20%20space%20those%20rows%20optimally.%0A%23%0A%23%20My%20optimization%20for%20spacing%20is%20piecewise%20linear%3A%20cost%20%3D%20-3s%2F3%20%2B%203%20for%20s%20%3C%3D%203%2C%201%2F4s%20for%20s%20%3E%203%0A%23%20Approach%3A%20create%20a%20binary%20Rows_With_Data%20and%20use%20it%20to%20view%20rows%20only%0A%23%20one%20optimal%20solution%20where%20s%20is%203%0A%23%201%201%201%200%200%0A%23%200%200%200%200%200%0A%23%200%200%200%200%200%0A%23%200%201%201%201%200%0A%23%200%200%200%200%200%0A%23%20%0A%23%20I%20know%20I%20can%20add%20a%20constraint%20to%20acheive%20row%20spacing%2C%20but%20this%20is%20a%20simplification%20of%20my%20real%20problem%20(there%20will%20be%20many%20rows%0A%23%20to%20be%20optimally%20spaced%20not%20just%20one).%0Aset%20I%20%3A%3D%201..5%3B%0A%0Avar%20Y%7BI%2CI%7D%2C%20binary%3B%0Avar%20Rows_With_Data%7BI%7D%2C%20binary%3B%20%20%20%23%20does%20this%20row%20have%20any%20data%3F%0A%0A%23%20only%203%20in%20a%20row%20of%205%0As.t.%20Three_max_per_row%20%20%20%20%7Bi%20in%20I%7D%3A%20sum%7Bj%20in%20I%20%7D%20Y%5Bi%2Cj%5D%20%3C%3D%203%3B%20%23%20allows%202%20or%201%20in%20a%20row%20(bad)%0A%0A%23%20only%202%20rows%20have%20data%0As.t.%20Two_rows_have_data%3A%20sum%7Bi%20in%20I%7D%20Rows_With_Data%5Bi%5D%20%3D%202%3B%0A%0A%23%20only%20allow%206%20total%20w%2Fin%20matrix%0As.t.%20Six_total%3A%20%20%20%20%20%20sum%7Bi%20in%20I%2C%20j%20in%20I%7D(Y%5Bi%2Cj%5D)%20%3D%206%3B%0A%0A%23%20if%20a%20row%20has%20any%2C%20then%20it%20has%203%2C%20uses%20Rows_With_Data%20as%20a%20boolean%0As.t.%20%20Three_in_one_row%7Bi%20in%20I%7D%3A%20sum%7Bj%20in%20I%7D%20(Y%5Bi%2Cj%5D)%20%3D%20Rows_With_Data%5Bi%5D*3%3B%0A%0A%23%20Now%20enforce%20sequence%0A%23%20to%20do...%0A%0A%23%20minimize%20cost%0A%23%20%3F%3F%3F%20%20%0A%20%20%0A%0Asolve%3B%0A%0Adisplay%20I%3B%0Adisplay%20Y%3B%0Adisplay%3ARows_With_Data%3B%0A%0Adata%3B%0A%0Aend%3B
Eric Winter
_______________________________________________
Help-glpk mailing list
[email protected]
https://lists.gnu.org/mailman/listinfo/help-glpk
