Defining Set Packing using MathProg

Question

For someone with zero experience, this can be very confusing.

How do I define the Set Packing problem as seen in the wikipedia article as a MathProg program, to be later ran in the GLPK tool?

Intution alone would lead me into something like this:

var x

maximize SetPacking :
 sum {s in Subsets} x
s.t.         ??              //x is an integer 0 or 1
s.t.         ??              //amount of x <=1
end;

But its logic is obviously wrong and I can't even finish it.

vitaut · Accepted Answer · 2015-11-29 15:53:28Z

0

You can formulate the set packing problem in AMPL (and MathProg which is based on a subset of AMPL) as follows:

set U; # universe
set S; # subsets
set Members{S}; # members of subsets

# every set is either in the set packing or not
var x{S} binary;

# maximize the total number of subsets
maximize NumSets: sum{s in S} x[s];

# selected sets have to be pairwise disjoint
s.t. Disjoint{e in U}: sum{s in S: e in Members[s]} x[s] <= 1;

Note that you have to introduce indexed set Members with each element Members[s]representing members of subset s. This is the only difference from the algebraic formulation.

answered Nov 29, 2015 at 15:53

vitaut

57.4k31 gold badges232 silver badges409 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Defining Set Packing using MathProg

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related