Linear Program Solver and Mixed Integer Program Solver in Sage #6502

nathanncohen · 2009-07-09T16:34:48Z

Following this message on SAGE-devel :
http://groups.google.com/group/sage-devel/browse_thread/thread/9da47e06bcdfc49f

This is the class sage.numerical.mip which is meant to be the common interface between SAGE and 3 different LP solvers : GLPK, Coin-Or, and CPLEX.

Trac ticket for GLPK : #6602
Trac ticker for COIN : #6603

CC: @haraldschilly

Component: numerical

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

nathanncohen · 2009-07-09T16:35:08Z

Class sage.numerical.mip

nathanncohen · 2009-07-09T16:43:21Z

comment:1

Attachment: 12428.patch.gz

If you want to try this code, you will find a short example there :

http://groups.google.com/group/sage-devel/browse_thread/thread/7c13a0a4ba3d87b6

sagetrac-carlohamalainen · 2009-07-10T11:14:54Z

comment:2

Compiles and installs successfully on Sage 4.0.1 on Ubuntu x86.

The methods in MIP should have doctests/docstrings. e.g. I should be able to type

sage: MIP.addBound?

and see a nice example for how to add a bound.

wdjoyner · 2009-07-10T11:49:42Z

comment:3

I agree, this needs docstrings.

Installation of the spkg went fine on a macbook running 10.4.11. The patch seemed to apply okay. sage -testall on 4.1.rc1 passed except for failures in parallel/decorate (DeprecationWarning: os.popen2 is deprecated. ) and interfaces/sage0 (which could not be replicated).

The examples given in the sage-devel email (below) seemed to work okay, though I am not an expert on this stuff.

g=graphs.RandomGNP(10,.5)

p=MIP(max=True)

obj={}
for i in g.vertices():
   obj["V"+str(i)]=1
   p.setinteger("V"+str(i))
p.setobj(Constraint(obj,obj=True))
for (a,b,c) in g.edges():
   obj={}
   obj["V"+str(a)]=1
   obj["V"+str(b)]=1
   p.addconstraint(Constraint(obj,lt=1))
p.solve()

nathanncohen · 2009-07-23T14:22:23Z

comment:5

solves LP using GLPK ( see GLPK for Sage #6602 )
the interface with the COIN solver has been moved to a SPKG whose link will be added here
Doctstrings have been added
small modifications everywhere

Patch numerical.mip-2.patch applies on top of 2428.patch

I hope you will like it !! I spent a lot of time on this LP for SAGE ! ;-)

nathanncohen · 2009-07-23T14:22:42Z

Attachment: numerical.mip-2.patch.gz

nathanncohen · 2009-07-23T14:56:20Z

comment:8

A small mistake in the detection of COIN -- fixed ! ;-)

sagetrac-mvngu · 2009-07-26T02:16:50Z

comment:9

Attachment: numerical.mip-3.patch.gz

Once this ticket has positive review, the SPKG at #6602 should also be merged in the standard packages repository. So in a sense, that SPKG is dependent on this ticket.

wdjoyner · 2009-07-26T23:01:45Z

comment:10

I got this problem:

wdj@hera:~/sagefiles/sage-4.1.1.alpha0$ ./sage
----------------------------------------------------------------------
| Sage Version 4.1.1.alpha0, Release Date: 2009-07-20                |
| Type notebook() for the GUI, and license() for information.        |
----------------------------------------------------------------------
Loading Sage library. Current Mercurial branch is: OR2
sage: hg_sage.apply("/home/wdj/sagefiles/12428.patch")
cd "/home/wdj/sagefiles/sage-4.1.1.alpha0/devel/sage" && hg status
/home/wdj/sagefiles/sage-4.1.1.alpha0/local/lib/python2.6/site-packages/sage/misc/hg.py:240: DeprecationWarning: os.popen3 isdeprecated.  Use the subprocess module.
  x = os.popen3(s)
cd "/home/wdj/sagefiles/sage-4.1.1.alpha0/devel/sage" && hg status
cd "/home/wdj/sagefiles/sage-4.1.1.alpha0/devel/sage" && hg import   "/home/wdj/sagefiles/12428.patch"
applying /home/wdj/sagefiles/12428.patch
patching file module_list.py
Hunk #1 succeeded at 240 with fuzz 2 (offset 13 lines).
patching file sage/numerical/all.py
Hunk #1 FAILED at 0
1 out of 1 hunks FAILED -- saving rejects to file sage/numerical/all.py.rej
abort: patch failed to apply

Any suggestions?

sagetrac-mvngu · 2009-07-26T23:06:23Z

comment:11

Replying to @wdjoyner:

I got this problem:

> Any suggestions?

I suggest we wait until 4.1.1 is out.

nathanncohen · 2009-07-30T22:50:02Z

comment:12

New patch including all the previously announced features and probably a bit more. It encompasses the previous patches, so you need only apply this one and forget about the others ! ;-)

wdjoyner · 2009-07-31T01:28:11Z

comment:13

Attachment: MIP-1.patch.gz

This was applied to 4.1.1.a0 and the following test failed:

zeus:~/sagefiles/sage-4.1.1.alpha0 davidjoyner$ ./sage -t  "devel/sage/sage/numerical/mip.pyx"
sage -t  "devel/sage/sage/numerical/mip.pyx"                
sh: line 1: kpsewhich: command not found
sh: line 1: kpsewhich: command not found
**********************************************************************
File "/Users/davidjoyner/sagefiles/sage-4.1.1.alpha0/devel/sage/sage/numerical/mip.pyx", line 37:
    sage: p=MIP(sense=1)
Exception raised:
    Traceback (most recent call last):
      File "/Users/davidjoyner/sagefiles/sage-4.1.1.alpha0/local/bin/ncadoctest.py", line 1231, in run_one_test
        self.run_one_example(test, example, filename, compileflags)
      File "/Users/davidjoyner/sagefiles/sage-4.1.1.alpha0/local/bin/sagedoctest.py", line 38, in run_one_example
        OrigDocTestRunner.run_one_example(self, test, example, filename, compileflags)
      File "/Users/davidjoyner/sagefiles/sage-4.1.1.alpha0/local/bin/ncadoctest.py", line 1172, in run_one_example
        compileflags, 1) in test.globs
      File "<doctest __main__.example_0[3]>", line 1, in <module>
        p=MIP(sense=Integer(1))###line 37:
    sage: p=MIP(sense=1)
    NameError: name 'MIP' is not defined
**********************************************************************
File "/Users/davidjoyner/sagefiles/sage-4.1.1.alpha0/devel/sage/sage/numerical/mip.pyx", line 39:
    sage: for i in g.vertices():
Exception raised:
    Traceback (most recent call last):
      File "/Users/davidjoyner/sagefiles/sage-4.1.1.alpha0/local/bin/ncadoctest.py", line 1231, in run_one_test
        self.run_one_example(test, example, filename, compileflags)
      File "/Users/davidjoyner/sagefiles/sage-4.1.1.alpha0/local/bin/sagedoctest.py", line 38, in run_one_example
        OrigDocTestRunner.run_one_example(self, test, example, filename, compileflags)
      File "/Users/davidjoyner/sagefiles/sage-4.1.1.alpha0/local/bin/ncadoctest.py", line 1172, in run_one_example
        compileflags, 1) in test.globs
      File "<doctest __main__.example_0[5]>", line 1
         for i in g.vertices():###line 39:
    sage: for i in g.vertices():
                                                                             
    ^
     SyntaxError: unexpected EOF while parsing
**********************************************************************
File "/Users/davidjoyner/sagefiles/sage-4.1.1.alpha0/devel/sage/sage/numerical/mip.pyx", line 40:
    sage:     obj[i]=1
Exception raised:
    Traceback (most recent call last):
      File "/Users/davidjoyner/sagefiles/sage-4.1.1.alpha0/local/bin/ncadoctest.py", line 1231, in run_one_test
        self.run_one_example(test, example, filename, compileflags)
      File "/Users/davidjoyner/sagefiles/sage-4.1.1.alpha0/local/bin/sagedoctest.py", line 38, in run_one_example
        OrigDocTestRunner.run_one_example(self, test, example, filename, compileflags)
      File "/Users/davidjoyner/sagefiles/sage-4.1.1.alpha0/local/bin/ncadoctest.py", line 1172, in run_one_example
        compileflags, 1) in test.globs
      File "<doctest __main__.example_0[6]>", line 1
         obj[i]=Integer(1)###line 40:
    sage:     obj[i]=1
        ^
     IndentationError: unexpected indent
**********************************************************************
File "/Users/davidjoyner/sagefiles/sage-4.1.1.alpha0/devel/sage/sage/numerical/mip.pyx", line 41:
    sage:     p.setinteger(i)
Exception raised:
    Traceback (most recent call last):
      File "/Users/davidjoyner/sagefiles/sage-4.1.1.alpha0/local/bin/ncadoctest.py", line 1231, in run_one_test
        self.run_one_example(test, example, filename, compileflags)
      File "/Users/davidjoyner/sagefiles/sage-4.1.1.alpha0/local/bin/sagedoctest.py", line 38, in run_one_example
        OrigDocTestRunner.run_one_example(self, test, example, filename, compileflags)
      File "/Users/davidjoyner/sagefiles/sage-4.1.1.alpha0/local/bin/ncadoctest.py", line 1172, in run_one_example
        compileflags, 1) in test.globs
      File "<doctest __main__.example_0[7]>", line 1
         p.setinteger(i)###line 41:
    sage:     p.setinteger(i)
        ^
     IndentationError: unexpected indent
**********************************************************************
File "/Users/davidjoyner/sagefiles/sage-4.1.1.alpha0/devel/sage/sage/numerical/mip.pyx", line 42:
    sage: p.setobj(obj)
Exception raised:
    Traceback (most recent call last):
      File "/Users/davidjoyner/sagefiles/sage-4.1.1.alpha0/local/bin/ncadoctest.py", line 1231, in run_one_test
        self.run_one_example(test, example, filename, compileflags)
      File "/Users/davidjoyner/sagefiles/sage-4.1.1.alpha0/local/bin/sagedoctest.py", line 38, in run_one_example
        OrigDocTestRunner.run_one_example(self, test, example, filename, compileflags)
      File "/Users/davidjoyner/sagefiles/sage-4.1.1.alpha0/local/bin/ncadoctest.py", line 1172, in run_one_example
        compileflags, 1) in test.globs
      File "<doctest __main__.example_0[8]>", line 1, in <module>
        p.setobj(obj)###line 42:
    sage: p.setobj(obj)
    NameError: name 'p' is not defined
**********************************************************************
File "/Users/davidjoyner/sagefiles/sage-4.1.1.alpha0/devel/sage/sage/numerical/mip.pyx", line 43:
    sage: for (a,b,c) in g.edges():
Exception raised:
    Traceback (most recent call last):
      File "/Users/davidjoyner/sagefiles/sage-4.1.1.alpha0/local/bin/ncadoctest.py", line 1231, in run_one_test
        self.run_one_example(test, example, filename, compileflags)
      File "/Users/davidjoyner/sagefiles/sage-4.1.1.alpha0/local/bin/sagedoctest.py", line 38, in run_one_example
        OrigDocTestRunner.run_one_example(self, test, example, filename, compileflags)
      File "/Users/davidjoyner/sagefiles/sage-4.1.1.alpha0/local/bin/ncadoctest.py", line 1172, in run_one_example
        compileflags, 1) in test.globs
      File "<doctest __main__.example_0[9]>", line 1
         for (a,b,c) in g.edges():###line 43:
    sage: for (a,b,c) in g.edges():
                                                                                   
    ^
     SyntaxError: unexpected EOF while parsing
**********************************************************************
File "/Users/davidjoyner/sagefiles/sage-4.1.1.alpha0/devel/sage/sage/numerical/mip.pyx", line 44:
    sage:     cons={}
Exception raised:
    Traceback (most recent call last):
      File "/Users/davidjoyner/sagefiles/sage-4.1.1.alpha0/local/bin/ncadoctest.py", line 1231, in run_one_test
        self.run_one_example(test, example, filename, compileflags)
      File "/Users/davidjoyner/sagefiles/sage-4.1.1.alpha0/local/bin/sagedoctest.py", line 38, in run_one_example
        OrigDocTestRunner.run_one_example(self, test, example, filename, compileflags)
      File "/Users/davidjoyner/sagefiles/sage-4.1.1.alpha0/local/bin/ncadoctest.py", line 1172, in run_one_example
        compileflags, 1) in test.globs
      File "<doctest __main__.example_0[10]>", line 1
         cons={}###line 44:
    sage:     cons={}
        ^
     IndentationError: unexpected indent
**********************************************************************
File "/Users/davidjoyner/sagefiles/sage-4.1.1.alpha0/devel/sage/sage/numerical/mip.pyx", line 45:
    sage:     cons[a]=1
Exception raised:
    Traceback (most recent call last):
      File "/Users/davidjoyner/sagefiles/sage-4.1.1.alpha0/local/bin/ncadoctest.py", line 1231, in run_one_test
        self.run_one_example(test, example, filename, compileflags)
      File "/Users/davidjoyner/sagefiles/sage-4.1.1.alpha0/local/bin/sagedoctest.py", line 38, in run_one_example
        OrigDocTestRunner.run_one_example(self, test, example, filename, compileflags)
      File "/Users/davidjoyner/sagefiles/sage-4.1.1.alpha0/local/bin/ncadoctest.py", line 1172, in run_one_example
        compileflags, 1) in test.globs
      File "<doctest __main__.example_0[11]>", line 1
         cons[a]=Integer(1)###line 45:
    sage:     cons[a]=1
        ^
     IndentationError: unexpected indent
**********************************************************************
File "/Users/davidjoyner/sagefiles/sage-4.1.1.alpha0/devel/sage/sage/numerical/mip.pyx", line 46:
    sage:     cons[b]=1
Exception raised:
    Traceback (most recent call last):
      File "/Users/davidjoyner/sagefiles/sage-4.1.1.alpha0/local/bin/ncadoctest.py", line 1231, in run_one_test
        self.run_one_example(test, example, filename, compileflags)
      File "/Users/davidjoyner/sagefiles/sage-4.1.1.alpha0/local/bin/sagedoctest.py", line 38, in run_one_example
        OrigDocTestRunner.run_one_example(self, test, example, filename, compileflags)
      File "/Users/davidjoyner/sagefiles/sage-4.1.1.alpha0/local/bin/ncadoctest.py", line 1172, in run_one_example
        compileflags, 1) in test.globs
      File "<doctest __main__.example_0[12]>", line 1
         cons[b]=Integer(1)###line 46:
    sage:     cons[b]=1
        ^
     IndentationError: unexpected indent
**********************************************************************
File "/Users/davidjoyner/sagefiles/sage-4.1.1.alpha0/devel/sage/sage/numerical/mip.pyx", line 47:
    sage:     p.addconstraint(cons,max=1)
Exception raised:
    Traceback (most recent call last):
      File "/Users/davidjoyner/sagefiles/sage-4.1.1.alpha0/local/bin/ncadoctest.py", line 1231, in run_one_test
        self.run_one_example(test, example, filename, compileflags)
      File "/Users/davidjoyner/sagefiles/sage-4.1.1.alpha0/local/bin/sagedoctest.py", line 38, in run_one_example
        OrigDocTestRunner.run_one_example(self, test, example, filename, compileflags)
      File "/Users/davidjoyner/sagefiles/sage-4.1.1.alpha0/local/bin/ncadoctest.py", line 1172, in run_one_example
        compileflags, 1) in test.globs
      File "<doctest __main__.example_0[13]>", line 1
         p.addconstraint(cons,max=Integer(1))###line 47:
    sage:     p.addconstraint(cons,max=1)
        ^
     IndentationError: unexpected indent
**********************************************************************
File "/Users/davidjoyner/sagefiles/sage-4.1.1.alpha0/devel/sage/sage/numerical/mip.pyx", line 48:
    sage: p.solve()
Exception raised:
    Traceback (most recent call last):
      File "/Users/davidjoyner/sagefiles/sage-4.1.1.alpha0/local/bin/ncadoctest.py", line 1231, in run_one_test
        self.run_one_example(test, example, filename, compileflags)
      File "/Users/davidjoyner/sagefiles/sage-4.1.1.alpha0/local/bin/sagedoctest.py", line 38, in run_one_example
        OrigDocTestRunner.run_one_example(self, test, example, filename, compileflags)
      File "/Users/davidjoyner/sagefiles/sage-4.1.1.alpha0/local/bin/ncadoctest.py", line 1172, in run_one_example
        compileflags, 1) in test.globs
      File "<doctest __main__.example_0[14]>", line 1, in <module>
        p.solve()###line 48:
    sage: p.solve()
    NameError: name 'p' is not defined
**********************************************************************
1 items had failures:
  11 of  15 in __main__.example_0
***Test Failed*** 11 failures.
For whitespace errors, see the file /Users/davidjoyner/sagefiles/sage-4.1.1.alpha0/tmp/.doctest_mip.py
         [4.9 s]
exit code: 1024

Does this make sense?

nathanncohen · 2009-07-31T06:19:57Z

comment:14

It seems Sage does not like something dealing with the indentation in the doctest of the class, as the example works when I am copying it manually... If you know the standard ( if there are any ) in this situation, please tell me because I am trying to fix this and changing the indentation ten thousand times hoping it will work is not my preferred way of debugging ^^;

nathanncohen · 2009-07-31T06:52:04Z

comment:15

Fixed in patch MIP-2.patch

As a sidenote, this ranks as the least interesting debugging I ever did, and I just achieved it because there was another example of a loop in a dosctring in Sage. Thanks to the brave developper of sage.combinat.dlx who conquered the docstrings ! ;-)

nathanncohen · 2009-07-31T06:52:32Z

Attachment: MIP-2.patch.gz

wdjoyner · 2009-07-31T09:49:05Z

comment:16

I usually debug by just running sage -t with the file open in an editor until it passes:-)

Am I to apply MIP1 then MIP2? If so, there was a problem compiling (amd64, ubuntu 9.04):

wdj@hera:~/sagefiles/sage-4.1.1.alpha1$ ./sage -b                                                             

----------------------------------------------------------
sage: Building and installing modified Sage library files.


Installing c_lib
scons: `install' is up to date.
Updating Cython code....       
Building modified file sage/numerical/mip.pyx.
python `which cython` --embed-positions --incref-local-binop -I/home/wdj/sagefiles/sage-4.1.1.alpha1/devel/sage-OR -o sage/numerical/mip.cpp sage/numerical/mip.pyx                                                           
sage/numerical/mip.pyx --> /home/wdj/sagefiles/sage-4.1.1.alpha1/local//lib/python/site-packages//sage/numerical/mip.pyx                                                                                                      
Time to execute 1 commands: 0.891119003296 seconds                                                             
Finished compiling Cython code (time = 1.45167207718 seconds)                                                  
running install                                                                                                
running build                                                                                                  
running build_py                                                                                               
copying sage/numerical/all.py -> build/lib.linux-x86_64-2.6/sage/numerical                                     
running build_ext                                                                                              
building 'sage.numerical.mip' extension                                                                        
gcc -fno-strict-aliasing -DNDEBUG -g -fwrapv -O3 -Wall -Wstrict-prototypes -fPIC -Ilocal/include/ -I/home/wdj/sagefiles/sage-4.1.1.alpha1/local//include -I/home/wdj/sagefiles/sage-4.1.1.alpha1/local//include/csage -I/home/wdj/sagefiles/sage-4.1.1.alpha1/devel//sage/sage/ext -I/home/wdj/sagefiles/sage-4.1.1.alpha1/local/include/python2.6 -c sage/numerical/mip.cpp -o build/temp.linux-x86_64-2.6/sage/numerical/mip.o -w                         
cc1plus: warning: command line option "-Wstrict-prototypes" is valid for Ada/C/ObjC but not for C++            
sage/numerical/mip.cpp:132:38: error: ../../local/include/glpk.h: No such file or directory                    
sage/numerical/mip.cpp: In function ‘PyObject* __pyx_pf_4sage_9numerical_3mip_3MIP_solveGLPK(PyObject*, PyObject*, PyObject*)’:                                                                                               
sage/numerical/mip.cpp:2777: error: ‘glp_prob’ was not declared in this scope                                  
sage/numerical/mip.cpp:2777: error: ‘__pyx_v_lp’ was not declared in this scope                                
sage/numerical/mip.cpp:2787: error: ‘glp_iocp’ was not declared in this scope                                  
sage/numerical/mip.cpp:2787: error: ‘__pyx_v_iocp’ was not declared in this scope                              
sage/numerical/mip.cpp:2985: error: ‘glp_create_prob’ was not declared in this scope                           
sage/numerical/mip.cpp:2998: error: ‘glp_add_rows’ was not declared in this scope                              
sage/numerical/mip.cpp:3011: error: ‘glp_add_cols’ was not declared in this scope                              
sage/numerical/mip.cpp:3098: error: ‘glp_set_obj_coef’ was not declared in this scope                          
sage/numerical/mip.cpp:3241: error: ‘GLP_DB’ was not declared in this scope                                    
sage/numerical/mip.cpp:3241: error: ‘glp_set_col_bnds’ was not declared in this scope                          
sage/numerical/mip.cpp:3330: error: ‘GLP_UP’ was not declared in this scope                                    
sage/numerical/mip.cpp:3330: error: ‘glp_set_col_bnds’ was not declared in this scope                          
sage/numerical/mip.cpp:3419: error: ‘GLP_LO’ was not declared in this scope                                    
sage/numerical/mip.cpp:3419: error: ‘glp_set_col_bnds’ was not declared in this scope                          
sage/numerical/mip.cpp:3450: error: ‘GLP_FR’ was not declared in this scope                                    
sage/numerical/mip.cpp:3450: error: ‘glp_set_col_bnds’ was not declared in this scope                          
sage/numerical/mip.cpp:3764: error: ‘GLP_FX’ was not declared in this scope                                    
sage/numerical/mip.cpp:3764: error: ‘glp_set_row_bnds’ was not declared in this scope                          
sage/numerical/mip.cpp:3791: error: ‘GLP_DB’ was not declared in this scope                                    
sage/numerical/mip.cpp:3791: error: ‘glp_set_row_bnds’ was not declared in this scope                          
sage/numerical/mip.cpp:3846: error: ‘GLP_UP’ was not declared in this scope                                    
sage/numerical/mip.cpp:3846: error: ‘glp_set_row_bnds’ was not declared in this scope                          
sage/numerical/mip.cpp:3899: error: ‘GLP_LO’ was not declared in this scope                                    
sage/numerical/mip.cpp:3899: error: ‘glp_set_row_bnds’ was not declared in this scope                          
sage/numerical/mip.cpp:3912: error: ‘GLP_FR’ was not declared in this scope                                    
sage/numerical/mip.cpp:3912: error: ‘glp_set_row_bnds’ was not declared in this scope                          
sage/numerical/mip.cpp:3957: error: ‘GLP_MIN’ was not declared in this scope                                   
sage/numerical/mip.cpp:3957: error: ‘glp_set_obj_dir’ was not declared in this scope                           
sage/numerical/mip.cpp:3969: error: ‘GLP_MAX’ was not declared in this scope                                   
sage/numerical/mip.cpp:3969: error: ‘glp_set_obj_dir’ was not declared in this scope                           
sage/numerical/mip.cpp:4059: error: ‘GLP_IV’ was not declared in this scope                                    
sage/numerical/mip.cpp:4059: error: ‘glp_set_col_kind’ was not declared in this scope                          
sage/numerical/mip.cpp:4108: error: ‘GLP_BV’ was not declared in this scope                                    
sage/numerical/mip.cpp:4108: error: ‘glp_set_col_kind’ was not declared in this scope                          
sage/numerical/mip.cpp:4136: error: ‘GLP_CV’ was not declared in this scope
sage/numerical/mip.cpp:4136: error: ‘glp_set_col_kind’ was not declared in this scope
sage/numerical/mip.cpp:4156: error: ‘glp_load_matrix’ was not declared in this scope
sage/numerical/mip.cpp:4165: error: expected type-specifier before ‘glp_iocp’
sage/numerical/mip.cpp:4165: error: expected `;' before ‘glp_iocp’
sage/numerical/mip.cpp:4174: error: ‘glp_init_iocp’ was not declared in this scope
sage/numerical/mip.cpp:4183: error: ‘GLP_ON’ was not declared in this scope
sage/numerical/mip.cpp:4205: error: ‘GLP_MSG_OFF’ was not declared in this scope
sage/numerical/mip.cpp:4229: error: ‘GLP_MSG_ERR’ was not declared in this scope
sage/numerical/mip.cpp:4253: error: ‘GLP_MSG_ON’ was not declared in this scope
sage/numerical/mip.cpp:4265: error: ‘GLP_MSG_ALL’ was not declared in this scope
sage/numerical/mip.cpp:4276: error: ‘glp_intopt’ was not declared in this scope
sage/numerical/mip.cpp:4285: error: ‘glp_mip_obj_val’ was not declared in this scope
sage/numerical/mip.cpp:4314: error: ‘glp_delete_prob’ was not declared in this scope
sage/numerical/mip.cpp:4408: error: ‘glp_mip_col_val’ was not declared in this scope
sage/numerical/mip.cpp:4422: error: ‘glp_delete_prob’ was not declared in this scope
error: command 'gcc' failed with exit status 1
sage: There was an error installing modified sage library code.


real    0m3.367s
user    0m2.880s
sys     0m0.428s

Do you know what this means?

nathanncohen · 2009-07-31T09:54:24Z

comment:17

Yes, this time I know !!! ;-)

The first error is : sage/numerical/mip.cpp:132:38: error: ../../local/include/glpk.h: No such file or directory

And this is because you did not install GLPK ( #6602 ) which is to be a standanrd package. And MIP-2 applies on top of MIP-1 !

Sorry for these details I may have forgotten ! ;-)

wdjoyner · 2009-07-31T13:07:24Z

comment:18

These patches applies to an amd64 ubuntu 9.04 machine passes sage -testall (except for the already reported errors for sage 4.1.1.a1).

Things are improving but there are some remaining issues:

There is a possible typo in the docstring for MIP:

        For example linear function 3 * x - 2 * y + 3 * z
        where x,y, and z are objects is represented as { x : 3, y : -2, z : -3 }

might have a sign error and should I think be

        For example linear function 3 * x - 2 * y + 3 * z
        where x,y, and z are objects is represented as { x : 3, y : -2, z : 3 }

There is no example in the docstring for MIP.solve. There should be at least one
(fairly simple and well-commented) and preferably more. Please check other
docstrings for missing examples. They are required as part of the code
inclusion process. Please read:
http://www.sagemath.org/doc/developer/conventions.html#documentation-strings

nathanncohen · 2009-07-31T16:18:34Z

comment:19

You were right about the typo. And I hope you will find in MIP-3.patch all the docstrings you need ;-)

sagetrac-mvngu · 2009-08-23T12:52:00Z

comment:46

The patches and GLPK should be wrapped up into an spkg. The patch AllMIP.patch if applied as is would fail to compile. You can rectify that by first installing the optional spkg GLPK. But the patch AllMIP.patch is to be applied to the Sage library, and when applied and shipping Sage, Sage would fail to compile because we don't ship optional spkg's. So put everything (the patches plus GLPK) into a self-contained spkg.

nathanncohen · 2009-08-24T09:47:06Z

comment:47

New patch AllMIP-2 available.

All the calls to solve() are flagged optional. This class should now compile even without the libraries glpk ( which have been removed from module_list ) : all is left in this class except the call to solveGlpk, which is now a function defined in the new version of the spkg ( see #6817 ).

It is a bit better this way, as this was already the case with package CBC ( now, the code is "symmetric" between Glpk and Cbc, as both are optional packages )

In the end :

To test this code aply patch AllMIP-2
To install the new version of Glpk which is to make this code useful, type

sage -f http://www-sop.inria.fr/members/Nathann.Cohen/glpk-4.38.spkg

This spkg being currently reviewed at #6817 ( it should be pretty quick, there is nothing new in this patch except a function which had already been reviewed here ! )

nathanncohen · 2009-08-24T09:47:37Z

Attachment: AllMIP-2.patch.gz

Now without solveGlpk !

nathanncohen · 2009-08-24T11:08:19Z

comment:48

Lets make it :

sage -f http://www-sop.inria.fr/members/Nathann.Cohen/glpk-4.38.p0.spkg

wdjoyner · 2009-08-25T17:53:02Z

comment:50

I can only test this with glpk installed (having build problems...). Is that okay?

sagetrac-mvngu · 2009-08-25T18:04:14Z

comment:51

Replying to @wdjoyner:

I can only test this with glpk installed (having build problems...). Is that okay?

That is fine by me. But note that since the patch AllMIP-2.patch depends on an optional package, its doctests should be marked with "# optional" so that running doctests with something like "./sage -t -long /path/to/script.py" would skip over doctests that require optional spkg's. At the moment, most of the doctests in AllMIP-2.patch require that the optional package GLPK be installed, but those doctests that require this package are not flagged with "# optional". See for example, this doctest:

 	39	         sage: ### Computation of a maximum stable set in Petersen's graph ### 
 	40	         sage: g=graphs.PetersenGraph() 
 	41	         sage: p=MIP(sense=1) 
 	42	         sage: obj={} 
 	43	         sage: for i in g.vertices(): 
 	44	         ...       obj[i]=1  
 	45	         ...       p.setinteger(i)  
 	46	         sage: p.setobj(obj) 
 	47	         sage: for (a,b,c) in g.edges(): 
 	48	         ...       cons={}  
 	49	         ...       cons[a]=1  
 	50	         ...       cons[b]=1  
 	51	         ...       p.addconstraint(cons,max=1)  
 	52	         sage: p.solve(objective_only=True) 
 	53	         4.0

The line

 	41	         sage: p=MIP(sense=1)

requires GLPK and some other patches. But it should be written like this:

 	41	         sage: p=MIP(sense=1)  # optional

to flag it as requiring an optional package. Any other tests that require the functionalities of an optional spkg must be flagged as such. When testing these, one would do something along this line:

./sage -t -long -optional /path/to/script.py

wdjoyner · 2009-08-25T18:09:44Z

comment:52

Okay, because of this comment, I'm changing it back to needs work.

nathanncohen · 2009-08-25T18:48:57Z

comment:53

Hmmm... There's something I do not understand here ^^;

At first I thought I had made a mistake by not uploading the last version of my patch, in which I added the required "optional" flags, but in the end it seems there are included already... You can see they are by looking (Ctrl - f) for the word "optional" on the page https://github.com/sagemath/sage-prod/files/10645489/AllMIP-2.patch.gz

I just installed this patch on a brand new install without GLPK, it compiled fine and there were no warnings during the test ( without the -optional flag, obiously)

Could you please check that you downloaded the last version and did not apply a cached file ??

Just to be sure, I upload a flattened version of patch named AllMIP-2-flattened.patch

wdjoyner · 2009-08-25T22:06:12Z

comment:54

Attachment: AllMIP-2-flattened.patch.gz

BTW, the ALLMIP2 patch applied fine for me, as before, and passes sage -testall (mod the known unrelated failures already described). So, positive review from me, but I am testing on a clone of Sage which has glpk installed.

nathanncohen · 2009-08-25T22:14:06Z

comment:55

I tested it on a copy of Sage without GLPK... But as I posted this patch I guess it does not count ^^;

nathanncohen · 2009-08-31T15:54:44Z

comment:56

As the functions dealing with LP have not been reviewed, I prefer to rewrite the MIP class for Sage to make it easier to use. I will post a new version of the MIP patch as soon as possible, along with all the patches for functions using it.

Sorry for the trouble, I'll try to make it quick !

Nathann

nathanncohen · 2009-09-02T17:39:43Z

comment:57

This ticket should be deleted. A new ticket has been created #6869 with a new version of the class, now using symbolics !

Nathann

nathanncohen mannequin added c: numerical labels Jul 9, 2009

nathanncohen mannequin assigned sagetrac-jkantor Jul 9, 2009

nathanncohen mannequin added the s: needs review label Jul 9, 2009

boothby added the s: needs work label Jul 15, 2009

nathanncohen mannequin added s: needs review and removed s: needs work labels Jul 23, 2009

This comment has been minimized.

Sign in to view

sagetrac-mvngu mannequin changed the title ~~[with Patch] Linear Program Solver and Mixed Integer Program Solver in SAGE~~ Linear Program Solver and Mixed Integer Program Solver in Sage Jul 26, 2009

nathanncohen mannequin added s: needs review and removed s: needs work labels Aug 24, 2009

wdjoyner added s: needs work and removed s: needs review labels Aug 25, 2009

nathanncohen mannequin added s: needs review and removed s: needs work labels Aug 25, 2009

nathanncohen mannequin added s: needs work and removed s: needs review labels Aug 31, 2009

sagetrac-mvngu mannequin removed the s: needs work label Sep 2, 2009

sagetrac-mvngu mannequin closed this as completed Sep 2, 2009

sagetrac-mvngu mannequin removed this from the sage-4.1.2 milestone Sep 2, 2009

sagetrac-mvngu mannequin added r: wontfix and removed p: major / 3 labels Sep 2, 2009

This was referenced Jul 26, 2009

GLPK for Sage #6602

Closed

COIN-OR / CBC for SAGE #6603

Closed

Knapsack algorithm #6749

Closed

GLPK for Sage, new version #6817

Closed

LP and MIP Solvers in Sage ( with symbolics ) #6869

Closed

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Linear Program Solver and Mixed Integer Program Solver in Sage #6502

Linear Program Solver and Mixed Integer Program Solver in Sage #6502

nathanncohen mannequin commented Jul 9, 2009

nathanncohen mannequin commented Jul 9, 2009

nathanncohen mannequin commented Jul 9, 2009

sagetrac-carlohamalainen mannequin commented Jul 10, 2009

wdjoyner commented Jul 10, 2009

nathanncohen mannequin commented Jul 23, 2009

nathanncohen mannequin commented Jul 23, 2009

This comment has been minimized.

This comment has been minimized.

nathanncohen mannequin commented Jul 23, 2009

sagetrac-mvngu mannequin commented Jul 26, 2009

wdjoyner commented Jul 26, 2009

sagetrac-mvngu mannequin commented Jul 26, 2009

nathanncohen mannequin commented Jul 30, 2009

wdjoyner commented Jul 31, 2009

nathanncohen mannequin commented Jul 31, 2009

nathanncohen mannequin commented Jul 31, 2009

nathanncohen mannequin commented Jul 31, 2009

wdjoyner commented Jul 31, 2009

nathanncohen mannequin commented Jul 31, 2009

wdjoyner commented Jul 31, 2009

nathanncohen mannequin commented Jul 31, 2009

sagetrac-mvngu mannequin commented Aug 23, 2009

nathanncohen mannequin commented Aug 24, 2009

nathanncohen mannequin commented Aug 24, 2009

nathanncohen mannequin commented Aug 24, 2009

wdjoyner commented Aug 25, 2009

sagetrac-mvngu mannequin commented Aug 25, 2009

wdjoyner commented Aug 25, 2009

nathanncohen mannequin commented Aug 25, 2009

wdjoyner commented Aug 25, 2009

nathanncohen mannequin commented Aug 25, 2009

nathanncohen mannequin commented Aug 31, 2009

nathanncohen mannequin commented Sep 2, 2009

Linear Program Solver and Mixed Integer Program Solver in Sage #6502

Linear Program Solver and Mixed Integer Program Solver in Sage #6502

Comments

nathanncohen mannequin commented Jul 9, 2009

nathanncohen mannequin commented Jul 9, 2009

nathanncohen mannequin commented Jul 9, 2009

sagetrac-carlohamalainen mannequin commented Jul 10, 2009

wdjoyner commented Jul 10, 2009

nathanncohen mannequin commented Jul 23, 2009

nathanncohen mannequin commented Jul 23, 2009

This comment has been minimized.

This comment has been minimized.

nathanncohen mannequin commented Jul 23, 2009

sagetrac-mvngu mannequin commented Jul 26, 2009

wdjoyner commented Jul 26, 2009

sagetrac-mvngu mannequin commented Jul 26, 2009

nathanncohen mannequin commented Jul 30, 2009

wdjoyner commented Jul 31, 2009

nathanncohen mannequin commented Jul 31, 2009

nathanncohen mannequin commented Jul 31, 2009

nathanncohen mannequin commented Jul 31, 2009

wdjoyner commented Jul 31, 2009

nathanncohen mannequin commented Jul 31, 2009

wdjoyner commented Jul 31, 2009

nathanncohen mannequin commented Jul 31, 2009

sagetrac-mvngu mannequin commented Aug 23, 2009

nathanncohen mannequin commented Aug 24, 2009

nathanncohen mannequin commented Aug 24, 2009

nathanncohen mannequin commented Aug 24, 2009

wdjoyner commented Aug 25, 2009

sagetrac-mvngu mannequin commented Aug 25, 2009

wdjoyner commented Aug 25, 2009

nathanncohen mannequin commented Aug 25, 2009

wdjoyner commented Aug 25, 2009

nathanncohen mannequin commented Aug 25, 2009

nathanncohen mannequin commented Aug 31, 2009

nathanncohen mannequin commented Sep 2, 2009