Feasible problem returns infeasible; inconsistent results

[svigerske]

Issue created by migration from Trac.

Original creator: ltaylor

Original creation time: 2007-11-17 03:27:24

Assignee: somebody

Version:

This is an MPS file generated by COINMP.dll interface, after loading it by API calls. Under COINOptimizeProblem, it returns problem infeasible.

I have also tested it with: (1) windows binary clp.exe, several versions; (2) locally compiled MS Visual studio 2005 project in debug mode, with project files in synch with the latest (Nov. 16. 2007) versions, and several previous versions. Revision 1137.

Coin LP version 1.06.00, build Nov 16 2007
Clp takes input from arguments ( - switches to stdin)
Enter ? for list of commands or help
Clp:directory c://temp//
Clp:import ch108-prob1.mps
At line 1 NAME          BLANK
At line 2 ROWS
At line 98 COLUMNS
At line 11210 RHS
At line 11211 BOUNDS
At line 13581 ENDATA
Problem BLANK has 94 rows, 2369 columns and 17942 elements
Model was imported from c://temp//\ch108-prob1.mps in 0.062 seconds
Clp:duals
Presolve 72 (-22) rows, 2323 (-46) columns and 17764 (-178) elements
0  Obj 0 Primal inf 31.3191 (16)
76  Obj 4.52447e-006 Primal inf 0.587574 (7)
152  Obj 0.207158 Primal inf 285148 (24)
156  Obj 0.220218 Primal inf 895508 (23)
215  Obj 8859.37 Primal inf 1.02777e+010 (24)
220  Obj 15623.2 Primal inf 2.32421e+010 (30)
220  Obj 15623.2 Primal inf 2.32421e+010 (30)
Primal infeasible - objective value 15623.2
Presolved problem not optimal, resolve after postsolve
After Postsolve, objective 15701.4, infeasibilities - dual 0.000231735 (1), prim
al 3.49235e+010 (51)
PrimalInfeasible objective 15701.42062 - 440 iterations time 0.232, Presolve 0.0
9
Clp:

However, if I load the same file and use command 'primals', clp.exe reports that the problem is feasible. As I know from solving it previously, the correct solution has an objective of 4.87.

Microsoft Windows XP [Version 5.1.2600]
(C) Copyright 1985-2001 Microsoft Corp.

C:\Documents and Settings\Larry A. Taylor>cd my*

C:\Documents and Settings\Larry A. Taylor\My Documents>cd coi*

C:\Documents and Settings\Larry A. Taylor\My Documents\COIN-OR>cd
C:\Documents and Settings\Larry A. Taylor\My Documents\COIN-OR

C:\Documents and Settings\Larry A. Taylor\My Documents\COIN-OR>dir
 Volume in drive C has no label.
 Volume Serial Number is 07D1-0B0E

 Directory of C:\Documents and Settings\Larry A. Taylor\My Documents\COIN-OR

03/13/2007  12:04 PM    <DIR>          .
03/13/2007  12:04 PM    <DIR>          ..
03/08/2007  11:12 AM    <DIR>          Bonmin-0.1.1
03/13/2007  12:26 PM    <DIR>          Vol-1.0.0
03/13/2007  03:10 PM    <DIR>          Clp-1.3.3-win32-msvc8
03/13/2007  06:05 PM    <DIR>          CoinMP
03/13/2007  06:25 PM    <DIR>          MSVisualStudio
03/14/2007  03:19 PM           296,108 saltzman-OSI-2006.pdf
03/14/2007  04:09 PM           190,060 tkr2_symphony.pdf
03/14/2007  04:40 PM            66,037 CORS2004-OSI.pdf
03/14/2007  06:18 PM    <DIR>          FlopC++
03/15/2007  06:28 PM    <DIR>          TestCoinMP
03/15/2007  07:37 PM    <DIR>          TestCoinMP1
05/31/2007  02:51 PM    <DIR>          BINARY DOWNLOAD
06/07/2007  03:50 PM    <DIR>          WrapCoinMP
08/08/2007  03:06 PM             9,969 Doxyfile
08/08/2007  03:06 PM    <DIR>          html
08/08/2007  03:06 PM    <DIR>          latex
08/21/2007  12:04 PM    <DIR>          bin
08/21/2007  12:04 PM    <DIR>          doc
11/16/2007  07:08 PM    <DIR>          FEEDBACk
               4 File(s)        562,174 bytes
              17 Dir(s)   4,700,372,992 bytes free

C:\Documents and Settings\Larry A. Taylor\My Documents\COIN-OR>cd bin*

C:\Documents and Settings\Larry A. Taylor\My Documents\COIN-OR\BINARY DOWNLOAD>d
ir
 Volume in drive C has no label.
 Volume Serial Number is 07D1-0B0E

 Directory of C:\Documents and Settings\Larry A. Taylor\My Documents\COIN-OR\BIN
ARY DOWNLOAD

05/31/2007  02:51 PM    <DIR>          .
05/31/2007  02:51 PM    <DIR>          ..
05/31/2007  02:53 PM    <DIR>          Clp-1.3.3-win32-msvc8
05/31/2007  02:56 PM    <DIR>          coin-win32-msvc7-13Feb06
11/16/2007  06:09 PM         3,328,485 coin-win32-msvc6-24Feb06.zip
               1 File(s)      3,328,485 bytes
               4 Dir(s)   4,700,372,992 bytes free

C:\Documents and Settings\Larry A. Taylor\My Documents\COIN-OR\BINARY DOWNLOAD>c
d clp*

C:\Documents and Settings\Larry A. Taylor\My Documents\COIN-OR\BINARY DOWNLOAD\C
lp-1.3.3-win32-msvc8>dir
 Volume in drive C has no label.
 Volume Serial Number is 07D1-0B0E

 Directory of C:\Documents and Settings\Larry A. Taylor\My Documents\COIN-OR\BIN
ARY DOWNLOAD\Clp-1.3.3-win32-msvc8

05/31/2007  02:53 PM    <DIR>          .
05/31/2007  02:53 PM    <DIR>          ..
11/08/2006  03:07 PM                16 AUTHORS
05/31/2007  02:53 PM    <DIR>          bin
05/31/2007  02:53 PM    <DIR>          include
05/31/2007  02:53 PM    <DIR>          lib
11/08/2006  03:07 PM            11,611 LICENSE
11/08/2006  03:07 PM             1,837 README
               3 File(s)         13,464 bytes
               5 Dir(s)   4,700,372,992 bytes free

C:\Documents and Settings\Larry A. Taylor\My Documents\COIN-OR\BINARY DOWNLOAD\C
lp-1.3.3-win32-msvc8>cd bin

C:\Documents and Settings\Larry A. Taylor\My Documents\COIN-OR\BINARY DOWNLOAD\C
lp-1.3.3-win32-msvc8\bin>dir
 Volume in drive C has no label.
 Volume Serial Number is 07D1-0B0E

 Directory of C:\Documents and Settings\Larry A. Taylor\My Documents\COIN-OR\BIN
ARY DOWNLOAD\Clp-1.3.3-win32-msvc8\bin

05/31/2007  02:53 PM    <DIR>          .
05/31/2007  02:53 PM    <DIR>          ..
11/08/2006  03:46 PM         1,155,072 clp.exe
               1 File(s)      1,155,072 bytes
               2 Dir(s)   4,700,372,992 bytes free

C:\Documents and Settings\Larry A. Taylor\My Documents\COIN-OR\BINARY DOWNLOAD\C
lp-1.3.3-win32-msvc8\bin>clp.exe
Coin LP version 1.03.03, build Nov  8 2006
Clp takes input from arguments ( - switches to stdin)
Enter ? for list of commands or help
Clp:directory c://temp//
Clp:import ch108-prob1.mps

... SKIPPED ...

Clp:primals

... SKIPPED ...

Presolved problem not optimal, resolve after postsolve
After Postsolve, objective 2.71674e-005, infeasibilities - dual 0.00104051 (333)
, primal 3903.52 (6)
0  Obj 2.71674e-005 Primal inf 0.0464045 (4) Dual inf 4.06771e+010 (9)
7  Obj 4.87297 Primal inf 3.78856e-007 (1) Dual inf 0.000600785 (58)
7  Obj 4.87297 Primal inf 3.78856e-007 (1)
Optimal - objective value 3793.44
Optimal objective 3793.436084 - 184 iterations time 0.282, Presolve 0.06
Clp:

Notice that this was the clp.exe of the binary download clp-1.3.3-win32-msvc8.

Even for this earlier version, it does not get the correct answer if you type 'duals'.

What is even weirder is that if you do the same problem in clp.exe twice in a row (e.g., duals followed by duals, or other combinations), I get different answers. Something is not clearing out between optimizations.

Also, although when it gets the right answer, 4.87, it is not reported correctly in the same line as the "optimal" report.

LAT

[svigerske]

Attachment ch108-prob1-mps.zip by ltaylor created at 2007-11-17 03:29:27

Zip of MPS file of problem, plus basis file believed to be correct solution

[svigerske]

Comment by @jpfasano created at 2007-11-17 11:47:41

LAT states:

if I load the same file and use command 'primals', clp.exe reports that the problem is feasible. As I know from solving it previously, the correct solution has an objective of 4.87.

This is not what happens for me. 'primals' reports the problem as infeasible:

D:\COIN\Coin-Clp-All\trunk\Clp\MSVisualStudio\v8\clp\Release>clp
Coin LP version 1.06.00, build Nov 17 2007
Clp takes input from arguments ( - switches to stdin)
Enter ? for list of commands or help
Clp:import ch108-prob1.mps
At line 1 NAME          BLANK
At line 2 ROWS
At line 98 COLUMNS
At line 11210 RHS
At line 11211 BOUNDS
At line 13581 ENDATA
Problem BLANK has 94 rows, 2369 columns and 17942 elements
Model was imported from .\ch108-prob1.mps in 0.03 seconds
Clp:primals
Presolve 72 (-22) rows, 2323 (-46) columns and 17764 (-178) elements
Perturbing problem by 0.001 % of 7682.26 - largest nonzero change 0.0240588 (% 0.056856) - largest zero change 0
0  Obj 0 Primal inf 31.313 (16) Dual inf 1.89922e+013 (386)
76  Obj 1.45628e-005 Primal inf 0.0468318 (13) Dual inf 2.28393e+008 (198)
137  Obj 3.25773e-005 Primal inf 0.0468206 (13)
147  Obj 2.41675e-005 Primal inf 0.0443591 (3) Dual inf 242.045 (128)
156  Obj 2.36299e-005 Primal inf 0.0443591 (3) Dual inf 2.444 (64)
160  Obj 2.46491e-005 Primal inf 0.0443591 (3) Dual inf 4.64826 (61)
163  Obj 2.4318e-005 Primal inf 0.0443591 (3) Dual inf 1.32923 (38)
168  Obj 2.41847e-005 Primal inf 0.0443591 (3) Dual inf 1.34902 (30)
171  Obj 2.62022e-005 Primal inf 0.0443591 (3) Dual inf 0.387188 (16)
175  Obj 2.73519e-005 Primal inf 0.0443591 (3) Dual inf 0.0494242 (3)
177  Obj 2.71674e-005 Primal inf 0.0443591 (3)
Primal infeasible - objective value 2.71674e-005
Presolved problem not optimal, resolve after postsolve
After Postsolve, objective 2.71674e-005, infeasibilities - dual 0.00104051 (333), primal 3903.52 (6)
PrimalInfeasible objective 2.716742009e-005 - 354 iterations time 0.072, Presolve 0.02
Clp:

I used the current trunk version of Clp built with the Microsoft V8 compiler solution file.

[svigerske]

Comment by @jpfasano created at 2007-11-17 12:33:07

The latest trunk Clp code on Linux report the problem as infeasible when solved with 'primals' or 'duals'.

[svigerske]

Comment by ladanyi created at 2008-02-11 04:08:13

Same things happen for me as for JP: 1.6.0, stable/1.6, trunk all return infeasible both with primals and duals. I compiled with VC++ Express.

cplex also determines the problem to be infeasible. The two solvers agree, so I doubt that the problem would be feasible, i.e., the basis supplied in the zip file could be an optimal basis.

For now I close the ticket. LAT, feel free to reopen the ticket if you still think that there is problem.

--Laci

[svigerske]

Comment by ladanyi created at 2008-02-11 04:08:13

Resolution: worksforme