Cfrgtkky

Me and my friend are trying to implement a paper and the last step requires solving a linear programming problem to get the final result. We are not so familiar with LP so i'd like to ask for your help.

Here's the function which is based on the PROFSET model

and here's the proposed constraints

(1)

(2)

where:

1. Pa and Qi are the binary decision variables


2. J are all the available categories


3. F are sets of frequent categories


4. Φ is the total number of selected categories

Constraint (1) actually says that Qi is 1 if category i is included in some itemset A where Pa = 1

Basically, we are trying to use some common open source lp solvers (like joptimizer) but we dont know
how to define those constraints, especially those that define set inclusion rules. Most of those solvers
seem to accept just inequalities.

So, do you have any idea about how to define those constraints? Maybe transform them to inequalities or
something? Any help would be appreciated.

Thank you

A constraint that is written as an equality can be also written as two inequalities.
e.g.

• A*x=b is the same as


• A*x<=b and A*x>=b

In order to write such a LP there are two ways.

1. To hardcode it, meaning writing everything in code for example in Java.


2. Write it the mathematical way in a "language" called AMPL: https://ampl.com/resources/the-ampl-book/ For the second way you don't really need to know a programming language. AMPL transforms magically your LP into code and feeds it to a solver e.g. commercial: CPLEX, Gurobi (academic license available) or open source: GLPK. AMPL provides also an online platform that you can provide your model as .mod file and data as .dat files.

If you still want to hardcode your LP GLPK has nice examples e.g. in JAVA:

public class Lp {

    //  Minimize z = -.5 * x1 + .5 * x2 - x3 + 1

    //

    //  subject to

    //  0.0 <= x1 - .5 * x2 <= 0.2

    //  -x2 + x3 <= 0.4

    //  where,

    //  0.0 <= x1 <= 0.5

    //  0.0 <= x2 <= 0.5

    //  0.0 <= x3 <= 0.5



public static void main(String arg) {

    glp_prob lp;

    glp_smcp parm;

    SWIGTYPE_p_int ind;

    SWIGTYPE_p_double val;

    int ret;



    try {

        // Create problem

        lp = GLPK.glp_create_prob();

        System.out.println("Problem created");

        GLPK.glp_set_prob_name(lp, "myProblem");



        // Define columns

        GLPK.glp_add_cols(lp, 3);

        GLPK.glp_set_col_name(lp, 1, "x1");

        GLPK.glp_set_col_kind(lp, 1, GLPKConstants.GLP_CV);

        GLPK.glp_set_col_bnds(lp, 1, GLPKConstants.GLP_DB, 0, .5);

        GLPK.glp_set_col_name(lp, 2, "x2");

        GLPK.glp_set_col_kind(lp, 2, GLPKConstants.GLP_CV);

        GLPK.glp_set_col_bnds(lp, 2, GLPKConstants.GLP_DB, 0, .5);

        GLPK.glp_set_col_name(lp, 3, "x3");

        GLPK.glp_set_col_kind(lp, 3, GLPKConstants.GLP_CV);

        GLPK.glp_set_col_bnds(lp, 3, GLPKConstants.GLP_DB, 0, .5);



        // Create constraints



        // Allocate memory

        ind = GLPK.new_intArray(3);

        val = GLPK.new_doubleArray(3);



        // Create rows

        GLPK.glp_add_rows(lp, 2);



        // Set row details

        GLPK.glp_set_row_name(lp, 1, "c1");

        GLPK.glp_set_row_bnds(lp, 1, GLPKConstants.GLP_DB, 0, 0.2);

        GLPK.intArray_setitem(ind, 1, 1);

        GLPK.intArray_setitem(ind, 2, 2);

        GLPK.doubleArray_setitem(val, 1, 1.);

        GLPK.doubleArray_setitem(val, 2, -.5);

        GLPK.glp_set_mat_row(lp, 1, 2, ind, val);



        GLPK.glp_set_row_name(lp, 2, "c2");

        GLPK.glp_set_row_bnds(lp, 2, GLPKConstants.GLP_UP, 0, 0.4);

        GLPK.intArray_setitem(ind, 1, 2);

        GLPK.intArray_setitem(ind, 2, 3);

        GLPK.doubleArray_setitem(val, 1, -1.);

        GLPK.doubleArray_setitem(val, 2, 1.);

        GLPK.glp_set_mat_row(lp, 2, 2, ind, val);



        // Free memory

        GLPK.delete_intArray(ind);

        GLPK.delete_doubleArray(val);



        // Define objective

        GLPK.glp_set_obj_name(lp, "z");

        GLPK.glp_set_obj_dir(lp, GLPKConstants.GLP_MIN);

        GLPK.glp_set_obj_coef(lp, 0, 1.);

        GLPK.glp_set_obj_coef(lp, 1, -.5);

        GLPK.glp_set_obj_coef(lp, 2, .5);

        GLPK.glp_set_obj_coef(lp, 3, -1);



        // Write model to file

        // GLPK.glp_write_lp(lp, null, "lp.lp");



        // Solve model

        parm = new glp_smcp();

        GLPK.glp_init_smcp(parm);

        ret = GLPK.glp_simplex(lp, parm);



        // Retrieve solution

        if (ret == 0) {

            write_lp_solution(lp);

        } else {

            System.out.println("The problem could not be solved");

        }



        // Free memory

        GLPK.glp_delete_prob(lp);

    } catch (GlpkException ex) {

        ex.printStackTrace();

    ret = 1;

    }

System.exit(ret);

}



/**

 * write simplex solution

 * @param lp problem

 */

static void write_lp_solution(glp_prob lp) {

    int i;

    int n;

    String name;

    double val;



    name = GLPK.glp_get_obj_name(lp);

    val = GLPK.glp_get_obj_val(lp);

    System.out.print(name);

    System.out.print(" = ");

    System.out.println(val);

    n = GLPK.glp_get_num_cols(lp);

    for (i = 1; i <= n; i++) {

        name = GLPK.glp_get_col_name(lp, i);

        val = GLPK.glp_get_col_prim(lp, i);

        System.out.print(name);

        System.out.print(" = ");

        System.out.println(val);

    }

}}