Originally posted by: Eumpfenbach

I am first going to post some code and then will explain my problem/question.

var_included = sol;
var_excluded = [1:size(c,1)];
var_excluded(var_included) = [];
bin_ind = 565039;
    var_introduced_flag = 1;
    counter = 0;
    while var_introduced_flag == 1
        counter = counter + 1;
%         if counter >= 17
%             num_var;
%         end
        lp_sub = Cplex('lp_sub');
        lp_sub.Model.sense = 'minimize';
        lp_sub.Param.simplex.display.Cur = 0;
        lp_sub.Param.preprocessing.presolve.Cur = 0;
        lp_sub.Model.A = A;
        lp_sub.Model.A(:,var_excluded) = [];
        lp_sub.Model.obj = c;
        lp_sub.Model.obj(var_excluded) = [];
        lp_sub.Model.rhs = b;
        lp_sub.Model.lhs = ones(size(b,1),1) * -Inf;
        lp_sub.Model.lb = zeros(size(var_included,2),1);
        temp1 = find(var_included < bin_ind);
        temp2 = find(var_included >= bin_ind);
        lp_sub.Model.ub = [ones(size(temp1,2),1) * Inf; ones(size(temp2,2),1)];
        lp_sub.Model.ctype = (ones(size(var_included,2),1) * 'C');
        lp_sub.solve();

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: Eumpfenbach

I am trying column generation in Matlab. I solve the lp relaxation of the problem I have in an MPS file. I store the solution as "sol" (using a command sol = find(problem.Solution.x ~= 0). I then start over and solve the problem using only the columns that had nonzero solution values when solving the whole problem. I get an infeasible problem. How can this happen?

I don't think there is any problem with the way I am creating the subproblem. If I make "var_included = " (ie, I included all of the columns), then lp_sub matches up perfectly with the cplex opject created by just reading in the MPS file.

I'm pretty stumped about what I am doing wrong. Help would be greatly appreciated.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: Eumpfenbach

Also, Bin_Ind is the number where the binary variables of the MPS file start. I just use it to create an upper bound of 1 for the proper variables when solving the lp relaxation.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: John Cui

When you got infeasible, I suggest you to export your model to a lp file, then you can check the lp file is what you expected or not. This is the method to check your code for modeling is correct or not.

Use below code to export model:

prob.writeModel('debug.lp')

John Cui
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: Eumpfenbach

I suspect I may have found the problem. I have some rows that look like this:

c23: <= 0

ie they have a RHS and their coefficients are all zeros. Presolve would have eliminated it I'm sure, but I turn presolve off for the column generation procedure. The variables that have nonzero coefficients in the full problem are not in the subproblem. Is there a standard way to handle this? I could introduce dummy variables to satisfy them, but that kind of contradicts the idea of column generation.

I'm thinking I should find all the rows with all zero coefficients, delete them but keep an indicator array of what constraints were deleted, and then reconstruct the proper dual vector? ie I start with n constraints, have m after I remove the unwanted ones. Then I take the m dimensional dual vector and splice in zeros for the constraints I deleted and regain an n dimensional dual vector to do the pricing with. Is this what you would do?
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

No, the "<= 0" rows should not be an issue, even if presolve is disabled.

I suggest that you use the standard tactics to find out why a model is infeasible. Dump the infeasible model to an .sav file (or .lp if you like). Then load it into the interactive CPLEX and optimize (should turn out to be infeasible). Then enter "conflict" to run the conflict refiner and "disp conf all" to show the conflict that it has found. Maybe you can already see what is going wrong.

If the conflict is too big, you could try the following:
Write the conflict to a ".clp" file. Then read in the full model (which is feasible), solve it and dump the solution into a ".sol" file. Read in the ".clp" file again, change the problem type to "milp" ("change prob milp"), read the ".sol" file as MIP start, and enter "conflict 1" to analyze why the ".sol" solution is not feasible for the ".clp" problem.
In theory, your approach should work. Discarding all columns with zero solution value should not make the problem infeasible. Nevertheless, you may have encountered numerical issues. For example, if you have discarded a column with a value of 1e-9 that appears in a model with coefficients larger than 1e+3, this could trigger an infeasibility.
Tobias
#CPLEXOptimizers
#DecisionOptimization