Search code examples
linear-programminglpsolve

binary LP vs. integer LP

I wonder why there is a difference between the following linear programs. They are written in the LP file format. I would assume that x=1 would be the optimal solution in both cases.

Program A:

min: x;
x >= 1;
bin x;

Output:

Value of objective function: 0

Actual values of the variables:
x                               0

Program B (simulates the binary constraint with the integer constrain and two additional constrains):

min: x;
x >= 1;
x <= 1;
x >= 0;
int x;

Output:

Value of objective function: 1.00000000

Actual values of the variables:
x                               1
Solution

  • Yes, this is a small quirk of lpSove having to do with single variable constraints.

    In your Problem A, setting 'bin x' ends up overriding the constraint 'x >=1.' That is why 0 is given as the optimal solution.

    From the documentation:

    Note that for bounds on variables, you should not put labels before them. This is because lp_solve then makes this an extra restriction. If you don't put a label before single variables then lp_solve doesn't have to create an extra row for bounds on variables, resulting in better performance.

    So it is better to write:

     x1 >= 1;

    than

     r_x1: x1 >= 1;

    Note that this is only for single variables, so myrow: x1 + x2 >= 2;

    performs as well as

    x1 + x2 >= 2;

    In your Problem A, you have a single variable constraint. When it is not explicitly named, the 'bin' declaration overrides that constraint. As you rightly point out, if you make the constraint explicit, by naming it, then lpSolve will create a new row for x1, thus honoring the constraint and the 'bin' cannot override it.

    min: x;
a: x >= 1.0;
bin x;

    will give you:

    Value of objective function: 1.00000000

Actual values of the variables:
x                               1