CODEWITHSUNDEEP
javasolverglpk
jbolt
jbolt

Reputation: 688

GLPK-Java to solve MILP type problems

While I already know that there is not much documentation on using GLPK-Java library I'm going to ask anyway... (and no I can't use another solver)

I have a basic problem that involves scheduling. Student to course for semester with some basic constraints.

The example problem is:

We consider {s1, s2} a set of two students. They need to take two
courses {c1, c2} during two semesters {t1, t2}.
We assume the courses are the same. We also assume that the students
cannot take more than one course per semester, and we'd like to determine the
minimum capacity X that must be offered by the classroom, assuming they
all offer the same capacity.

The example we were given in CPLEX format looks like this:

minimize X

subject to
y111 + y112 = 1
y121 + y122 = 1
y211 + y212 = 1
y221 + y222 = 1
y111 + y112 <= 1
y121 + y122 <= 1
y211 + y212 <= 1
y221 + y222 <= 1
y111 + y112 -X <= 0
y121 + y122 -X <= 0
y211 + y212 -X <= 0
y221 + y222 -X <= 0

end

I can run this through the solver via glpsol command and get it to solve but I need to write this using the API. I've never really worked with Linear Programming and the documentation leaves something to be desired. While this is simplistic at best, the real problem involves solving 600 students over 12 semesters who have to take 12 courses out of 18 with certain classes only available certain semesters and some courses having prerequisites.

What I need help with it translating the simplistic problem into a coding example using the API. I'm assuming that once I can see how the very simplistic problem maps to the API calls I can then figure out how to create the application for the more complex issue.

From the examples in the library I can see that you set up columns which in this case would be the Semester and the rows are the Students

// Define Columns
GLPK.glp_add_cols(lp, 2);   // adds the number of columns
GLPK.glp_set_col_name(lp, 1, "Sem_1");
GLPK.glp_set_col_kind(lp, 1, GLPKConstants.GLP_IV);
GLPK.glp_set_col_bnds(lp, 1, GLPKConstants.GLP_LO, 0, 0);

GLPK.glp_set_col_name(lp, 2, "Sem_2");
GLPK.glp_set_col_kind(lp, 2, GLPKConstants.GLP_IV);
GLPK.glp_set_col_bnds(lp, 2, GLPKConstants.GLP_LO, 0, 0);

At this point I would assume you need to set up the row constraints but I'm at a loss. Any direction would be greatly appreciated.

Upvotes: 3

Views: 1460

Answers (1)

Paul G.
Paul G.

Reputation: 632

When using the API the optimization Problem is basically represented by a matrix of the Problem, where the columns are your variables and the rows your constraints. For your Problem you have to define 9 Columns, representing y111, y112, ... and X.

Then you can go on with the constraints (rows) by setting the used variables (columns)

GLPK.glp_set_row_name(lp, 2, "constraint1");
GLPK.glp_set_row_bnds(lp, 2, GLPKConstants.GLP_FX, 0, 1.0); // equal to 1.0
GLPK.intArray_setitem(ind, 1, 1); // Add first column at first position
GLPK.intArray_setitem(ind, 2, 2); // Add second column at second position    
// set the coefficients to the variables (for all 1. except X is -1. in the example)
GLPK.doubleArray_setitem(val, 1, 1.); 
GLPK.doubleArray_setitem(val, 2, 1.);
GLPK.glp_set_mat_row(lp, 1, 2, ind, val);

This will represent the y111 + y112 = 1 constraint - 11 to go.

In the GLPK for Java package should also be a documentation for glpk which contains a good documentation of the GLPK functions (which are also available in glpk for java). Also have a look at the lp.java example.

Upvotes: 2

Related Questions