help-glpk
[Top][All Lists]

## [Help-glpk] MIP - Simple? Problem

 From: Eric Winter Subject: [Help-glpk] MIP - Simple? Problem Date: Fri, 11 Mar 2016 11:15:58 -0500

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 5
s.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 data
s.t. Two_rows_have_data: sum{i in I} Rows_With_Data[i] = 2;

# only allow 6 total w/in matrix
s.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 boolean
s.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.