Skip to content

Optim lp#1108

Merged
opencv-pushbot merged 17 commits intoopencv:masterfrom
nailbiter:optimLP
Jul 30, 2013
Merged

Optim lp#1108
opencv-pushbot merged 17 commits intoopencv:masterfrom
nailbiter:optimLP

Conversation

@nailbiter
Copy link
Copy Markdown
Contributor

I'm working on generic numerical optimization module for openCV within the Google Summer of Code 2013 initiative (mentor: Vadim Pisarevsky). I propose the implementation of the first algorithm in the series: the simplex algorithm. This version is not optimized so far, but is supposed to work on all the problems correctly and without cycling. Please, let me know if any problems encountered.

nailbiter added 9 commits May 31, 2013 07:39
Generic optimization package for openCV project, will be developed
between the June and September of 2013. This work is funded by Google
Summer of Code 2013 project. This project is about
implementing several algorithms, that will find global maxima/minima of a
given function on a given domain subject to a given constraints.

All comments/suggestions are warmly appreciated and to be sent to
alozz1991@gmail.com (please, mention the word "openCV" in topic of
message, for I'm using the spam-filters)
At this point we have a skeleton of a new module (optim) which can
barely compile properly (unlike previous commit). Besides, there is a
first draft of solver and lpsolver (linear optimization solver) in this
commit.
Added LPSolver class together with two nested classes: LPFunction and
LPConstraints. These represent function to be maximized and constraints
imposed respectively. They are implementations of interfaces Function
and Constraints respectively (latter ones are nested classes of Solver
interface, which is generic interface for all optimization algorithms to
be implemented within this project).

The next step is to implement the simplex algorithm! First, we shall
implement it for the case of constraints of the form Ax<=b and x>=0.
Then, we shall extend the sets of problems that can be handled by the
conversion to the one we've handled already. Finally, we shale
concentrate on numerical stability and efficiency.
What we have now corresponds to "formal simplex algorithm", described in
Cormen's "Intro to Algorithms". It will work *only* if the initial
problem has (0,0,0,...,0) as feasible solution (consequently, it will
work unpredictably if problem was unfeasible or did not have zero-vector as
feasible solution). Moreover, it might cycle.

TODO (first priority)
1. Implement initialize_simplex() procedure, that shall check for
feasibility and generate initial feasible solution. (in particular, code
should pass all 4 tests implemented at the moment)
2. Implement Bland's rule to avoid cycling.
3. Make the code more clear.
4. Implement several non-trivial tests (??) and check algorithm against
them. Debug if necessary.

TODO (second priority)
1. Concentrate on stability and speed (make difficult tests)
This version is supposed to work on all problems (please, let me know if
this is not so), but is not optimized yet in terms of numerical
stability and performance. Bland's rule is implemented as well, so
algorithm is supposed to allow no cycling. Additional check for multiple
solutions is added (in case of multiple solutions algorithm returns an
appropriate return code of 1 and returns arbitrary optimal solution).
Finally, now we have 5 tests.

Before Thursday we have 4 directions that can be tackled in parallel:
*) Prepare the pull request!
*) Make the code more clear and readable (refactoring)
*) Wrap the core solveLP() procedure in OOP-style interface
*) Test solveLP on non-trivial tests (possibly test against
http://www.coin-or.org/Clp/)
In particular, the following things are done:
*) Consistent tabulation of 4 spaces is ensured
*) New function dprintf() is introduced, so now printing of the debug
information can be turned on/off via the ALEX_DEBUG macro
*) Removed solveLP_aux namespace
*) All auxiliary functions are declared as static
*) The return codes of solveLP() are encapsulated in enum.
Additional cleaning for simplex method, removing the parts that are
currently unused. Removing developer's notes. Trying to reach production
level.
Change qualifiers on auxiliary functions (for solveLP() procedure) from
const (that does not have much sense) to static (that makes them
invisible for outside world and hopefully exacerbates optimization).
Fixed the code so to eliminate warnings related to shadowing and unused
parameters. In some settings, these warnings may be treated as an errors
and lead to failed build.

Suggested by Nikita Manovich.
@nailbiter
Copy link
Copy Markdown
Contributor Author

Dear Nikita!

Thank You for prompt response. I've made a modifications that will
hopefully fix this issue. Please, let me know in case of errors.
Unfortunately I have only Linux system at hand.

Best Regards,
Alex

2013/7/11 Nikita Manovich notifications@github.com

Hi,

Builds are fail. Could you please fix the problem?

http://build.opencv.org/builders/precommit_windows/builds/4210
http://build.opencv.org/builders/precommit_ubuntu/builds/4225
http://build.opencv.org/builders/precommit_ubuntu_nosse/builds/1741
http://build.opencv.org/builders/precommit_macos/builds/4111
http://build.opencv.org/builders/precommit_android/builds/3124


Reply to this email directly or view it on GitHubhttps://github.com//pull/1108#issuecomment-20796853
.

@ghost
Copy link
Copy Markdown

ghost commented Jul 11, 2013

Hi,

The problem exists. You can find more information here http://pullrequest.opencv.org/.
http://build.opencv.org/builders/precommit_ubuntu/builds/4231

Fixed all of the warnings.
@nailbiter
Copy link
Copy Markdown
Contributor Author

Dear Nikita!

Try this one, please.

Best Regards,
Alex

2013/7/11 Nikita Manovich notifications@github.com

Hi,

The problem exists. You can find more information here
http://pullrequest.opencv.org/.
http://build.opencv.org/builders/precommit_ubuntu/builds/4231


Reply to this email directly or view it on GitHubhttps://github.com//pull/1108#issuecomment-20804963
.

@ghost ghost assigned vpisarev Jul 11, 2013
@ghost
Copy link
Copy Markdown

ghost commented Jul 11, 2013

Vadim,

Could you please look at the pull request?

Copy link
Copy Markdown
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

mat.hpp is big header with inline implementations of Mat ops. It should not be included in the external headers since it's not required there.

Copy link
Copy Markdown
Contributor Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

but I use cv::Mat as arguments to solveLP() how should I use them without
including mat.hpp?

2013/7/11 Vadim Pisarevsky notifications@github.com

In modules/optim/include/opencv2/optim.hpp:

+// In no event shall the Intel Corporation or contributors be liable for any direct,
+// indirect, incidental, special, exemplary, or consequential damages
+// (including, but not limited to, procurement of substitute goods or services;
+// loss of use, data, or profits; or business interruption) however caused
+// and on any theory of liability, whether in contract, strict liability,
+// or tort (including negligence or otherwise) arising in any way out of
+// the use of this software, even if advised of the possibility of such damage.
+//
+//M*/
+
+#ifndef OPENCV_OPTIM_HPP
+#define OPENCV_OPTIM_HPP
+
+#include
+#include "opencv2/core.hpp"
+#include "opencv2/core/mat.hpp"

mat.hpp is big header with inline implementations of Mat ops. It should
not be included in the external headers since it's not required there.


Reply to this email directly or view it on GitHubhttps://github.com//pull/1108/files#r5140743
.

Copy link
Copy Markdown
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

you use references to cv::Mat, not cv::Mat itself. Just try to move this include to precomp.hpp and build it

Attempting to fix issues pointed out by Vadim Pisarevsky during the pull
request review. In particular, the following things are done:
*) The mechanism of debug info printing is changed and made more
procedure-style than the previous macro-style
*) z in solveLP() is now returned as a column-vector
*) Func parameter of solveLP() is now allowed to be column-vector, in
which case it is understood to be the transpose of what we need
*) Func and Constr now can contain floats, not only doubles (in the
former case the conversion is done via convertTo())
*)different constructor to allocate space for z in solveLP() is used,
making the size of z more explicit (this is just a notation change, not
functional, both constructors are achieving the same goal)
*) (big) mat.hpp and iostream headers are moved to precomp-headers from
optim.hpp
Copy link
Copy Markdown
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

this and the next line should be removed from the file. #define should be moved to .cpp file.

#include "opencv2/core.hpp" should be added

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

None yet

Projects

None yet

Development

Successfully merging this pull request may close these issues.

3 participants