Search code examples
linear-programminglpsolve

lp_solve ignoring trivial restrictions

I made a really simple linear problem for lp_solve.

$ cat test.txt 
max: 100X ;

X <= 0 ;

bin X ;

The right answer shall be that X has to be 0, as it is a binary variable and cannot be 1 due the restriction. However the result is:

$ lp_solve test.txt 

Value of objective function: 100.00000000

Actual values of the variables:
X                               1

What explains this behaviour? I am doing something wrong? This also happens when alike restrictions are present on larger problems.

Solution

  • Yes, when lp_solve does its preprocessing, it is eliminating your constraint altogether. Then the fact that X is binary kicks in and the Objective function is shown to be 100. (Incorrectly)

    You can see that this is happening by running with the -stats flag:

    ./lp_solve -stat test.lp
Constraints: 0
Variables  : 1
Integers   : 1
Semi-cont  : 0
SOS        : 0
Non-zeros  : 0  density=nan%

    The zero constraints and nan% density could be causing this unexpected behavior.

    There a couple of workarounds for this.

    1. If you eliminate the X bin; constraint altogether, it will solve it correctly and give you an objective value of 0.

    2. Another 'hack-like' fix is to add a dummy variable to your trivial constraint. Now the entire constraint gets recorded by lp_solve.

    For example, try to change your test.lp to be:

    max: 100X ;

X  + x_dummy <= 0 ; 

bin X ;

    Which now gives the proper: 

    Constraints: 1
Variables  : 2
Integers   : 1
Semi-cont  : 0
SOS        : 0
Non-zeros  : 2  density=100.000000%

    Hope that helps.