Incorrect result with integer problem

Question

Incorrect result with integer problem

Closed this issue 10 years ago · 14 comments

First off, great work on the branch and bound extension! I've been impressed with the performance on boolean problems.

I've been having trouble with integer problems. I tried to solve the following problem with ECOS_BB and it said that the problem was unbounded:

from cvxpy import *
x = Variable()
cost = square(x - 0.2)
prob = Problem(Minimize(cost))
prob.solve()
args = prob.get_problem_data(ECOS) # This exports the cvxpy problem into ecos standard form.
import ecos
ecos.solve(*args, int_vars_idx=[0]) # This means x is an integer variable.

Another strange thing is that the solver output suggested the problem was infeasible:

Iter    Lower Bound Upper Bound Gap
================================================
0   inf         inf         nan

It seems like it's trying to maximize the objective.

Answer 1 · 2014-11-18T22:47:54.000Z

I've expanded the branching criteria and it appears this problem is fixed:

from cvxpy import *
x = Variable()
cost = square(x - 0.2)
prob = Problem(Minimize(cost))
prob.solve()
-8.960056404547694e-10
args = prob.get_problem_data(ECOS) # This exports the cvxpy problem into ecos standard form.
import ecos
out = ecos.solve(*args, int_vars_idx=[0]) # This means x is an integer variable.

Iter Lower Bound Upper Bound Gap

0 0.00 inf inf
1 0.04 0.04 0.00

out['x']
array([ -6.57830169e-10, 3.99999749e-02])

Answer 2 · 2014-12-01T22:52:20.000Z

The variables are correct, but the pcost and dcost are recorded wrong in the output. I got this:

{'y': array([], dtype=float64), 'x': array([ -6.57830169e-10,   3.99999749e-02]), 's': array([  1.18632832e+07,   9.61477903e-10,   8.82419670e-02]), 'z': array([  2.95882660e-15,   4.00001912e-01,   5.20000191e-01]), 'info': {'dinf': 0.0, 'pcost': 0.6400000105313021, 'r0': 1e-07, 'infostring': 'Optimal solution found', 'dres': 2.444647267572523e-12, 'relgap': 1.3044891476199514e-07, 'dinfres': nan, 'pinf': 0.0, 'dcost': 0.6399999664601355, 'gap': 8.348730107243796e-08, 'pinfres': 1.5389973044038239, 'numerr': 0, 'iter': 16, 'exitFlag': 0, 'timing': {'runtime': 0.000261579, 'tsetup': 3.2693e-05, 'torder': 7.947e-06, 'tkktcreate': 1.785e-06, 'tkktfactor': 0.000385024, 'tsolve': 0.000228886, 'ttranspose': 1.9409999999999997e-06, 'tkktsolve': 0.00010439199999999999}, 'pres': 2.156679987446078e-12}}

Answer 3 · 2014-12-07T05:43:28.000Z

@hanwang would you mind looking into this issue of the wrong result being returned? Once this is fixed ECOS 1.0.6 can go on PyPi and I can update the cvxpy on PyPi to use it. The sooner I can do that the better.

Answer 4 · 2014-12-07T16:18:29.000Z

Latest commit has patched this issue.

On Sat, Dec 6, 2014 at 9:43 PM, Steven Diamond notifications@github.com
wrote:

@hanwang https://github.com/hanwang would you mind looking into this
issue of the wrong result being returned? Once this is fixed ECOS 1.0.6 can
go on PyPi and I can update the cvxpy on PyPi to use it. The sooner I can
do that the better.

—
Reply to this email directly or view it on GitHub
#92 (comment).

Answer 5 · 2014-12-07T22:01:19.000Z

The patch broke something. ecos doesn't build anymore. Here's the output from "python setup.py install"

running install
running bdist_egg
running egg_info
writing requirements to src/ecos.egg-info/requires.txt
writing src/ecos.egg-info/PKG-INFO
writing top-level names to src/ecos.egg-info/top_level.txt
writing dependency_links to src/ecos.egg-info/dependency_links.txt
reading manifest file 'src/ecos.egg-info/SOURCES.txt'
reading manifest template 'MANIFEST.in'
writing manifest file 'src/ecos.egg-info/SOURCES.txt'
installing library code to build/bdist.macosx-10.5-x86_64/egg
running install_lib
running build_py
running build_ext
building '_ecos' extension
gcc -fno-strict-aliasing -I/Users/stevend2/anaconda/envs/test_ecos_bb/include -arch x86_64 -DNDEBUG -g -fwrapv -O3 -Wall -Wstrict-prototypes -DPYTHON -DDLONG -DLDL_LONG -DCTRLC=1 -Iecos/include -I/Users/stevend2/anaconda/envs/test_ecos_bb/lib/python2.7/site-packages/numpy/core/include -Iecos/external/amd/include -Iecos/external/ldl/include -Iecos/external/SuiteSparse_config -I/Users/stevend2/anaconda/envs/test_ecos_bb/include/python2.7 -c src/ecosmodule.c -o build/temp.macosx-10.5-x86_64-2.7/src/ecosmodule.o
src/ecosmodule.c:208:3: error: unknown type name 'settings_bb'; did you mean 'settings'?
  settings_bb opts_ecos_bb;
  ^~~~~~~~~~~
  settings
ecos/include/ecos.h:101:3: note: 'settings' declared here
} settings;
  ^
src/ecosmodule.c:259:16: error: no member named 'abs_tol_gap' in 'struct settings'
  opts_ecos_bb.abs_tol_gap = MI_ABS_EPS;     
  ~~~~~~~~~~~~ ^
src/ecosmodule.c:260:16: error: no member named 'rel_tol_gap' in 'struct settings'
  opts_ecos_bb.rel_tol_gap = MI_REL_EPS;
  ~~~~~~~~~~~~ ^
src/ecosmodule.c:261:16: error: no member named 'integer_tol' in 'struct settings'
  opts_ecos_bb.integer_tol = MI_INT_TOL;
  ~~~~~~~~~~~~ ^
src/ecosmodule.c:287:21: error: no member named 'abs_tol_gap' in 'struct settings'
      &opts_ecos_bb.abs_tol_gap,
       ~~~~~~~~~~~~ ^
src/ecosmodule.c:361:53: error: no member named 'abs_tol_gap' in 'struct settings'
  if (checkPositiveFloat("mi_abs_eps", opts_ecos_bb.abs_tol_gap) < 0) return NULL;
                                       ~~~~~~~~~~~~ ^
src/ecosmodule.c:362:53: error: no member named 'rel_tol_gap' in 'struct settings'
  if (checkPositiveFloat("mi_rel_eps", opts_ecos_bb.rel_tol_gap) < 0) return NULL;
                                       ~~~~~~~~~~~~ ^
src/ecosmodule.c:363:53: error: no member named 'integer_tol' in 'struct settings'
  if (checkPositiveFloat("mi_int_tol", opts_ecos_bb.integer_tol) < 0) return NULL;
                                       ~~~~~~~~~~~~ ^
src/ecosmodule.c:588:85: error: too many arguments to function call, expected 19, have 20
      Apr, Ajc, Air, cpr, hpr, bpr, num_bool, bool_vars_idx, num_int, int_vars_idx, &opts_ecos_bb);
                                                                                    ^~~~~~~~~~~~~
ecos/include/ecos_bb.h:107:1: note: 'ECOS_BB_setup' declared here
ecos_bb_pwork* ECOS_BB_setup(
^
9 errors generated.
error: command 'gcc' failed with exit status 1

Answer 6 · 2014-12-07T22:02:30.000Z

Did you update the submodule? It appears that an older version of the header is beening used.

On Sun, Dec 7, 2014 at 2:01 PM, Steven Diamond notifications@github.com
wrote:

The patch broke something. ecos doesn't build anymore. Here's the output
from "python setup.py install"

running install
running bdist_egg
running egg_info
writing requirements to src/ecos.egg-info/requires.txt
writing src/ecos.egg-info/PKG-INFO
writing top-level names to src/ecos.egg-info/top_level.txt
writing dependency_links to src/ecos.egg-info/dependency_links.txt
reading manifest file 'src/ecos.egg-info/SOURCES.txt'
reading manifest template 'MANIFEST.in'
writing manifest file 'src/ecos.egg-info/SOURCES.txt'
installing library code to build/bdist.macosx-10.5-x86_64/egg
running install_lib
running build_py
running build_ext
building '_ecos' extension
gcc -fno-strict-aliasing -I/Users/stevend2/anaconda/envs/test_ecos_bb/include -arch x86_64 -DNDEBUG -g -fwrapv -O3 -Wall -Wstrict-prototypes -DPYTHON -DDLONG -DLDL_LONG -DCTRLC=1 -Iecos/include -I/Users/stevend2/anaconda/envs/test_ecos_bb/lib/python2.7/site-packages/numpy/core/include -Iecos/external/amd/include -Iecos/external/ldl/include -Iecos/external/SuiteSparse_config -I/Users/stevend2/anaconda/envs/test_ecos_bb/include/python2.7 -c src/ecosmodule.c -o build/temp.macosx-10.5-x86_64-2.7/src/ecosmodule.o
src/ecosmodule.c:208:3: error: unknown type name 'settings_bb'; did you mean 'settings'?
settings_bb opts_ecos_bb;
^~~~~~~~~~~
settings
ecos/include/ecos.h:101:3: note: 'settings' declared here
} settings;
^
src/ecosmodule.c:259:16: error: no member named 'abs_tol_gap' in 'struct settings'
opts_ecos_bb.abs_tol_gap = MI_ABS_EPS;
src/ecosmodule.c:260:16: error: no member named 'rel_tol_gap' in 'struct settings'
  opts_ecos_bb.rel_tol_gap = MI_REL_EPS;
  ~~~~~~~~~~~~ ^
src/ecosmodule.c:261:16: error: no member named 'integer_tol' in 'struct settings'
  opts_ecos_bb.integer_tol = MI_INT_TOL;
  ~~~~~~~~~~~~ ^
src/ecosmodule.c:287:21: error: no member named 'abs_tol_gap' in 'struct settings'
      &opts_ecos_bb.abs_tol_gap,
       ~~~~~~~~~~~~ ^
src/ecosmodule.c:361:53: error: no member named 'abs_tol_gap' in 'struct settings'
  if (checkPositiveFloat("mi_abs_eps", opts_ecos_bb.abs_tol_gap) < 0) return NULL;
                                       ~~~~~~~~~~~~ ^
src/ecosmodule.c:362:53: error: no member named 'rel_tol_gap' in 'struct settings'
  if (checkPositiveFloat("mi_rel_eps", opts_ecos_bb.rel_tol_gap) < 0) return NULL;
                                       ~~~~~~~~~~~~ ^
src/ecosmodule.c:363:53: error: no member named 'integer_tol' in 'struct settings'
  if (checkPositiveFloat("mi_int_tol", opts_ecos_bb.integer_tol) < 0) return NULL;
                                       ~~~~~~~~~~~~ ^
src/ecosmodule.c:588:85: error: too many arguments to function call, expected 19, have 20
      Apr, Ajc, Air, cpr, hpr, bpr, num_bool, bool_vars_idx, num_int, int_vars_idx, &opts_ecos_bb);
                                                                                    ^~~~~~~~~~~~~
ecos/include/ecos_bb.h:107:1: note: 'ECOS_BB_setup' declared here
ecos_bb_pwork* ECOS_BB_setup(
^
9 errors generated.
error: command 'gcc' failed with exit status 1

—
Reply to this email directly or view it on GitHub
<https://github.com/embotech/ecos/issues/92#issuecomment-65957393>.

Answer 7 · 2014-12-07T22:03:46.000Z

Oops, that fixed it.

On Sun, Dec 7, 2014 at 2:02 PM, Han Wang notifications@github.com wrote:

Did you update the submodule?

On Sun, Dec 7, 2014 at 2:01 PM, Steven Diamond notifications@github.com
wrote:
The patch broke something. ecos doesn't build anymore. Here's the output
from "python setup.py install"

running install
running bdist_egg
running egg_info
writing requirements to src/ecos.egg-info/requires.txt
writing src/ecos.egg-info/PKG-INFO
writing top-level names to src/ecos.egg-info/top_level.txt
writing dependency_links to src/ecos.egg-info/dependency_links.txt
reading manifest file 'src/ecos.egg-info/SOURCES.txt'
reading manifest template 'MANIFEST.in'
writing manifest file 'src/ecos.egg-info/SOURCES.txt'
installing library code to build/bdist.macosx-10.5-x86_64/egg
running install_lib
running build_py
running build_ext
building '_ecos' extension
gcc -fno-strict-aliasing
-I/Users/stevend2/anaconda/envs/test_ecos_bb/include -arch x86_64 -DNDEBUG
-g -fwrapv -O3 -Wall -Wstrict-prototypes -DPYTHON -DDLONG -DLDL_LONG
-DCTRLC=1 -Iecos/include
-I/Users/stevend2/anaconda/envs/test_ecos_bb/lib/python2.7/site-packages/numpy/core/include
-Iecos/external/amd/include -Iecos/external/ldl/include
-Iecos/external/SuiteSparse_config
-I/Users/stevend2/anaconda/envs/test_ecos_bb/include/python2.7 -c
src/ecosmodule.c -o build/temp.macosx-10.5-x86_64-2.7/src/ecosmodule.o
src/ecosmodule.c:208:3: error: unknown type name 'settings_bb'; did you
mean 'settings'?
settings_bb opts_ecos_bb;
^~~~~~~~~~~
settings
ecos/include/ecos.h:101:3: note: 'settings' declared here
} settings;
^
src/ecosmodule.c:259:16: error: no member named 'abs_tol_gap' in 'struct
settings'
opts_ecos_bb.abs_tol_gap = MI_ABS_EPS;
src/ecosmodule.c:260:16: error: no member named 'rel_tol_gap' in 'struct
settings'
opts_ecos_bb.rel_tol_gap = MI_REL_EPS;
~~~~~~~~~~~~ ^
src/ecosmodule.c:261:16: error: no member named 'integer_tol' in 'struct
settings'
opts_ecos_bb.integer_tol = MI_INT_TOL;
~~~~~~~~~~~~ ^
src/ecosmodule.c:287:21: error: no member named 'abs_tol_gap' in 'struct
settings'
&opts_ecos_bb.abs_tol_gap,
~~~~~~~~~~~~ ^
src/ecosmodule.c:361:53: error: no member named 'abs_tol_gap' in 'struct
settings'
if (checkPositiveFloat("mi_abs_eps", opts_ecos_bb.abs_tol_gap) < 0)
return NULL;
~~~~~~~~~~~~ ^
src/ecosmodule.c:362:53: error: no member named 'rel_tol_gap' in 'struct
settings'
if (checkPositiveFloat("mi_rel_eps", opts_ecos_bb.rel_tol_gap) < 0)
return NULL;
~~~~~~~~~~~~ ^
src/ecosmodule.c:363:53: error: no member named 'integer_tol' in 'struct
settings'
if (checkPositiveFloat("mi_int_tol", opts_ecos_bb.integer_tol) < 0)
return NULL;
~~~~~~~~~~~~ ^
src/ecosmodule.c:588:85: error: too many arguments to function call,
expected 19, have 20
Apr, Ajc, Air, cpr, hpr, bpr, num_bool, bool_vars_idx, num_int,
int_vars_idx, &opts_ecos_bb);
^~~~~~~~~~~~~
ecos/include/ecos_bb.h:107:1: note: 'ECOS_BB_setup' declared here
ecos_bb_pwork* ECOS_BB_setup(
^
9 errors generated.
error: command 'gcc' failed with exit status 1

—
Reply to this email directly or view it on GitHub
<https://github.com/embotech/ecos/issues/92#issuecomment-65957393>.
—
Reply to this email directly or view it on GitHub
#92 (comment).

Answer 8 · 2014-12-07T22:06:37.000Z

Except verbose=False doesn't silence the output anymore.

Answer 9 · 2014-12-07T22:09:39.000Z

Silencing the mixed integer output requires mi_verbose=False, verbose=False
has been reserved for the base ECOS solver. This way, any combination of
the verbosity can be toggled for debugging purposes.

On Sun, Dec 7, 2014 at 2:06 PM, Steven Diamond notifications@github.com
wrote:

Except verbose=False doesn't silence the output anymore.

—
Reply to this email directly or view it on GitHub
#92 (comment).

Answer 10 · 2014-12-07T22:43:14.000Z

mi_verbose=False doesn't seem to work.

Answer 11 · 2014-12-07T22:50:47.000Z

Sorry, try the latest commit.

Answer 12 · 2014-12-07T22:52:07.000Z

It works now, thanks!

On Sun, Dec 7, 2014 at 2:50 PM, Han Wang notifications@github.com wrote:

Reopened #92 #92.

—
Reply to this email directly or view it on GitHub
#92 (comment).

Answer 13 · 2014-12-24T16:39:17.000Z

Time to close! (Merry Christmas? :) )

Answer 14 · 2014-12-24T17:18:34.000Z

Thanks! Merry Christmas!

On Wed, Dec 24, 2014 at 11:39 AM, Eric Chu notifications@github.com wrote:

Time to close! (Merry Christmas? :) )

—
Reply to this email directly or view it on GitHub
#92 (comment).