Allow constants for objective function & deletion of rows in MixedIntegerLinearProgram

[johnperry-math]

Currently, MixedIntegerLinearProgram does not allow deleting rows. We would like to enable this for all backends that allow it.

Also, this is a bug.

sage: lp = MixedIntegerLinearProgram()
sage: x, y = lp[0], lp[1]
sage: lp.add_constraint(2*x + 3*y <= 6)
sage: lp.add_constraint(3*x + 2*y <= 6)
sage: lp.set_objective(x + y + 7)
sage: lp.set_integer(x); lp.set_integer(y)
sage: lp.solve()
2.0

The correct value ought to be 9, not 2. The problem is this line in the set_objective() method of mip.pyx:

        f.pop(-1,0)

John Perry will create a patch for GLPK and CBC; Nathann Cohen will create a patch for Gurobi and CPLEX.

Apply:

• attachment: trac_12823_rolls_all_into_one.patch

Depends on #12220
Depends on #12736
Depends on #12833

CC: @nathanncohen

Component: linear programming

Keywords: solver objective

Author: John Perry, Nathann Cohen

Reviewer: David Coudert, Nathann Cohen

Merged: sage-5.1.beta1

Issue created by migration from https://trac.sagemath.org/ticket/12823

[johnperry-math]

comment:1

I've uploaded a patch for Coin & GLPK. Do we want to take care of deleting constraints in this patch, too? I haven't done that yet; if so, I'll modify the ticket correspondingly.

[johnperry-math]

comment:2

I knew I'd forgotten something in the ticket properties: its type. Sorry. :-(

[johnperry-math]

Author: john_perry, ncohen

[johnperry-math]

comment:3

I'm about to upload a new patch that takes into account our offline discussion and enables deletion of rows. The doctests and some warning blocks are only in the backends, though; should those be moved to mip.pyx? I'm not real clear on that.

[johnperry-math]

comment:4

I also corrected the output of show().

[nathanncohen]

comment:5

Hellooooooooooo John !!

Well, there is no need to test functions 10 times in the same way, so the best is to write real hard tests in the backends, and some tests just meant as examples for the users in the documentation of numerical/mip.pyx. The point is that GLPK is the only solver whose documentation appears in Sage's online reference manual, so we can not easily write important documentation in the backends of CBC, Cplex and Gurobi for the user has almost no way to see it.

Nathann

[johnperry-math]

comment:6

Replying to @nathanncohen:

Well, there is no need to test functions 10 times in the same way, so the best is to write real hard tests in the backends, and some tests just meant as examples for the users in the documentation of numerical/mip.pyx.

Okay. I added a relatively simplex doctest for mip.pyx that illustrates removing constraints in a way that works for both GLPK and Coin. Its warning clause should hopefully alert the reader to look up the details for the solver they are using. While I was at it, I also fixed more output problems in show().

I guess it's time for you to referee this one, and to submit a patch for the other solvers. :-)

[johnperry-math]

Attachment: trac_12823_const_for_obj_funs.patch.gz

[nathanncohen]

comment:8

Hellooooooooo !!!

Simple. Your meant Simple. Not Simplex :-D
I'm making the same kind of mistake something with crazy words from graph theory or Sage... Crazy :-D

Well... This patch took me... quite some time ! It all began with #12833, which this patch depends upon. Some problems with Gurobi's interface. Which I noticed because my gurobi license was not valid anymore. Once I got this license again (and reinstalled Gurobi), I had a problem when installing cbc with sage -i cbc, for the first package Sage installed was the old one. Harald Schilly fixed that.
And... Ok, now this patch !
It does not do much actually, just adds the required methods in cplex and Gurobi.

Some important things I should mention. Please tell me what you think of them :

• I renamed self.obj_value to self.obj_constant_term, as I would have expected self.obj_value to store the optimal value reached by the objective function.
• Sage should never crash, whatever happens in the code. So as usual ((&@#)&@%&* indexes in GLPK) I added a +1 to the indices in GLPK, so that the constraints are numbered from 0 regardless of the solver. I also added tests in GLPK and Coin to ensure no crash happens. CPLEX and Gurobi never crash because of that, as they have a smarter management of exceptions (error codes).
• I also changed some doctests for which solutions were not unique. Actually I just removed the lines printing the value of variables, which were not fundamental, and let the others stay as they really tested the new methods.
• I believe I also added some #optional flags in Coin's file, though everything is mixed up in my head after editing 4 files in a row :-D

Anyway, everything is tested, and....

~/sage/numerical/backends$ sage -t -optional coin_backend.pyx glpk_backend.pyx gurobi_backend.pyx cplex_backend.pyx 
sage -t -optional "devel/sage-2/sage/numerical/backends/coin_backend.pyx"
	 [1.3 s]
sage -t -optional "devel/sage-2/sage/numerical/backends/cplex_backend.pyx"
	 [1.3 s]
sage -t -optional "devel/sage-2/sage/numerical/backends/glpk_backend.pyx"
	 [1.3 s]
sage -t -optional "devel/sage-2/sage/numerical/backends/gurobi_backend.pyx"
	 [1.4 s]
 
----------------------------------------------------------------------
All tests passed!
Total time for all tests: 5.3 seconds
~/sage/numerical/backends$ 

(And I rarely have all solvers installed at the same time)

Soo... Well, if you agree with my patch (I can send you my cplex/gurobi license if necessary), .... :-)

Thank you very much for your work on that one ! It's good to see this class move a bit :-)

Nathann

[nathanncohen]

Dependencies: 12833

[johnperry-math]

comment:9

I'm okay with offsetting the constraint according to the solver. However, line 401 of coin_backend should have

if i < 0 or i >= self.si.getNumRows():

instead of

if i < 0 or i > self.si.getNumRows():

shouldn't it?

[nathanncohen]

comment:10

Ahahaah. Totally right. Updated :-)

I had also totally forgotten to do the same for GLPK O_o
That's what you get when you code through copy/paste in several patches :-P

Nathann

[johnperry-math]

comment:11

Why do you enumerate the constraints in coin_backend, maybe others? Why not simply loop i from 0 to len(constraints)?

More: I don't understand this:

for i,c in enumerate(constraints): 
  if i < 0 or i >= nrows: 
    sage_free(rows) 
    raise ValueError("The constraint's index i must satisfy 0 <= i < number_of_constraints") 

  rows[i] = constraints[i] 

Seems to me the test should be

  if c < 0 or c >= nrows:

shouldn't it? and then you could have

  rows[i] = c     # same as constraints[i]

[nathanncohen]

comment:12

Why do you enumerate the constraints in coin_backend, maybe others? Why not simply loop i from 0 to len(constraints)?

Oh. Because I have been told that "enumerate" had been "optimised", and that as "for i in range(n)" it was translated into "good C code". Actually, here is what it gives :

  __pyx_t_4 = 0;
  __pyx_t_1 = ((PyObject *)__pyx_v_coeff); __Pyx_INCREF(__pyx_t_1); __pyx_t_5 = 0;
  for (;;) {
    if (__pyx_t_5 >= PyList_GET_SIZE(__pyx_t_1)) break;
    __pyx_t_2 = PyList_GET_ITEM(__pyx_t_1, __pyx_t_5); __Pyx_INCREF(__pyx_t_2); __pyx_t_5++;
    __Pyx_XDECREF(__pyx_v_v);
    __pyx_v_v = __pyx_t_2;
    __pyx_t_2 = 0;
    __pyx_v_i = __pyx_t_4;
    __pyx_t_4 = (__pyx_t_4 + 1);

So it is more or less the same... In particular, when you have a "for i in range(len(something))" I guess the "len(something)" is evaluated many times.

  __pyx_t_4 = PyObject_Length(__pyx_v_constraints); if (unlikely(__pyx_t_4 == -1)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 450; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
  for (__pyx_t_5 = 0; __pyx_t_5 < __pyx_t_4; __pyx_t_5+=1) {
    __pyx_v_i = __pyx_t_5;

Oh. No, it is not. Ok well.. It looks like it is indeed better as an range(len(thing)) :-D
And anyway it makes more sense this way... Of course there is no way to ensure that "len(thing)" does not change between the loops, but the meaning of "range(len(thing))" is clear, even if "thing" changed later on in the loop.

Updated !

Seems to me the test should be

  if c < 0 or c >= nrows:

shouldn't it?

Yeah totally.... Stupid me.

Nathann

[johnperry-math]

comment:54

Nathann

Replying to @nathanncohen:

Sorry for the delay, I am in Austria these days and mostly backpacking, so it is pretty hard to find some time with both my computer and WiFI access :-)

Hope you're having fun :-)

The point is that when I apply you folded patch (but I guess I should try to find out what it contains) I mostly get rejections. I applied before the two patch the current ticket says it depends on : #12736, #12833.

I'm not surprised. I forgot to test it w/#12833 first.

I can't get #12833 to apply at all on 5.0.beta9, so I'll have to try this at home, later tonight or tomorrow. Bummer. Stay tuned...

[johnperry-math]

comment:55

Okay. I downloaded & build beta 13 on a second computer (the first is a nearly 15 year-old, 32-bit machine, bogged down in testing some other tickets), applied the requisite patches for all dependencies listed, and after a lot of tinkering, got it to work.

I then went back & figured out why beta 8 didn't like #12833 --- some sort of whitespace error --- and tested it there, since I have coin installed there. That works, too.

So Coin & GLPK work on my machines. Someone please test gurobi & cplex again!

An aside: most of the problems seem to have been caused by whitespace!!! Apparently #12833 fixes some whitespace problems in gurobi and mip that I had also tried to fix in the latest patch for this one. I hadn't tried to fix them before; hence the unpleasant surprise.

I hope this one works...

[johnperry-math]

Changed reviewer from David Coudert to David Coudert, Nathann Cohen

[nathanncohen]

comment:56

Hellooooooooooooo !!!

Well, this one seems well oiled :-)

~/sage/numerical/backends$ sage -t -optional coin_backend.pyx glpk_backend.pyx gurobi_backend.pyx cplex_backend.pyx 
sage -t -optional "devel/sage-2/sage/numerical/backends/coin_backend.pyx"
	 [1.2 s]
sage -t -optional "devel/sage-2/sage/numerical/backends/cplex_backend.pyx"
	 [1.2 s]
sage -t -optional "devel/sage-2/sage/numerical/backends/glpk_backend.pyx"
	 [1.2 s]
sage -t -optional "devel/sage-2/sage/numerical/backends/gurobi_backend.pyx"
	 [1.4 s]
 
----------------------------------------------------------------------
All tests passed!
Total time for all tests: 5.0 seconds

And all tests pass in mip.pyx, graph, dgraph, generic_graph. Sooooo... I guess the patch is now positively reviewed :-)

Nathann

[johnperry-math]

comment:57

Yessss! :-) It only took... uhm, how many tries? X-D

[nathanncohen]

comment:58

Ahahah.. Well, it is still funnier like that compared with times when it takes several months before a ticket gets reviewed :-)

Nathann

[nathanncohen]

comment:59

(This being said, the ticket still depends on #12833 ^^;)

[dcoudert]

comment:60

Hello,

I don't need patch #12833 to apply this patch and all tests are OK (sage -t sage/numerical, and sage -t -optional sage/numerical/backends/glpk_backend.pyx and same for cplex).
So we could remove the dependency.

D.

[jdemeyer]

Changed work issues from failing doctests to none

[jdemeyer]

Changed author from john_perry, ncohen to John Perry, Nathann Cohen

[jdemeyer]

comment:63

The patch needs a proper commit message.

[jdemeyer]

comment:65

This needs to be rebased to sage-5.0.rc0:

applying /padic/scratch/jdemeyer/merger/patches/trac_12823_rolls_all_into_one.patch
patching file sage/numerical/mip.pyx
Hunk #16 FAILED at 809
Hunk #17 FAILED at 852
Hunk #19 FAILED at 969
3 out of 35 hunks FAILED -- saving rejects to file sage/numerical/mip.pyx.rej
abort: patch failed to apply

[nathanncohen]

Attachment: trac_12823_rolls_all_into_one.patch.gz

[nathanncohen]

comment:66

Patch updated ! ;-)

Nathann

[jdemeyer]

Merged: sage-5.1.beta1