- Boost - lists.boost.org

A possible GSOC 2011 proposal idea
by Chad Seibert 21 Mar '11

21 Mar '11

Hello Community! Before I write up my proposal, I wish to solicit the community response regarding the integration of an linear programming (LP) solver into Boost. An LP solver is library designed to solve LP problems. An LP problem is any problem of the form max sum(a_i x_i, 0 <= i <= m) subject to: sum(b_ij x_i, 0 <= i <= m) <= c_j, 0 <= j <= n x_i >= 0, 0<= i <= m where m is the number of variables and n is the number of constraints that define the problem. The constants are a_i, b_ij, and c_j; the variables are x_i A concrete example is the following: max 5x_1+2x_2 subject to: 2x_1 + 3x_2 <= 5 x_1 + 5x_2 <= 10 x_1 >= 0, x_2 >= 0 It is the objective of the LP solver to find a pair (x_1, x_2) such that 5x_1 + 2x_2 is maximum (this is unique) and that satisfies the constraints. In order to do this, I will implement the two major algorithms designed to solve these problems: the simplex algorithm and (possibly) Karmakar's algorithm. Furthermore, a programmatic interface and file parsing interface using Boost.Spirit will also be implemented. A second type of LP problem is where we require all the variables to be integers. Such an LP is called an integer programming problem, or ILP. We first note that solving ILP's is NP complete, therefore, there seems to be no efficient way to solve these kinds of problems. Nevertheless, algorithms have been developed to solve them and in practice, perform well. In particular, the cutting plane and branch and bound methods will be implemented. But why should we care about LP problems? The answer is that MANY problems in optimization can be reduced to solving an LP. A list of problems with polynomial time reductions to LP's include: * Scheduling problems * Knapsack problems, including their multi-dimensional variants * Allocation of resources * Covering/Packing problems * Cutting Stock problems and many others. Even the shortest path problem from graph theory can be phrased as an ILP (although one would never do this). If the community is interested in such a project, I have a minimalistic LP solver already written. I just need to "boostify" it and I'll upload within the next week. Thank you for reading this and any feedback would be greatly appreciated! Chad Seibert

9 11

[asio] timer cancelling
by Mr. Robert G Palmer Jr. 21 Mar '11

21 Mar '11

boost 1.45.0 WinXP SP3 What is the difference between boost::deadline_timer.cancel() and the cancellation that happens due to boost::deadline_timer.expires_from_now()? I'm doing an async_read_some() inside of a wrapper function I have written (based on http://lists.boost.org/Archives/boost/2007/04/120339.php) I have a read handler and a timer handler (I want the bytes read value and could probably combine the two handlers into one with the appropriate modification to the bind call). The read handler works, and then I cancel the timer, but the NEXT TIME I call the wrapper function, the timer hander fires with a boost::asio::error::operation_aborted. The timer object is local to the wrapper function, but the io_service is not, it is passed in, so it seems the io_service is holding onto the timer completion handler AND the fact that it was cancelled. Is there a way to clean this out before exiting my wrapper function? Is the 'expires_from_now()' calling the timer handler or is it the first call to run_one()? Thanks, -- Robert G. Palmer, Jr. robert.palmer(a)ingenutec.com

1 0

Re: [boost] [Review] Boost.Type Traits Extension ending tomorrow
by Brent Spillner 21 Mar '11

21 Mar '11

On 3/19/2011 11:52 Joachim Faulhaber wrote: >(1) We can think of the triple <T,U,R> of types that plus_assign *is* >applicable on. >(2) Each of those operations assigned to an operator can be decomposed Maybe the set of functions should be something like is_callable<plus, LeftOperandType, RightOperandType> result_of<plus, LeftOperandType, RightOperandType, ReturnType> retval_convertible_to<plus, LeftOperand, RightOperandType, EquivalentReturnType> Similarly, we could have is_prefix_callable<plusplus, OperandType> and is_postfix_callable<plusplus, OperandType>, which helps eliminate the ambiguity that naming-by-syntax would introduce. I favor making the operator name a template parameter because: - I suspect this will encourage a more maintainable code decomposition within the library - It will likely permit simpler extension to free functions or member functions (think is_callable<push_back, ContainerType, ValueType>) - It will likely be easier to use for higher-level libraries such as Phoenix, Proto, etc. that may pass around operator names for a while before caring about the specific operator to which they refer

4 6

[patch] Patch for eliminating some warnings
by Thomas Heller 21 Mar '11

21 Mar '11

Hi, During testing for phoenix i came over some warnings which were fairly easy to fix. The warnings showed up by compiling with -Wall -Wextra -ansi -pedantic on gcc and clang. They are mostly about unused parameters or extra semicolons. The affected files are: hing file boost/fusion/algorithm/iteration/detail/fold.hpp boost/fusion/sequence/intrinsic/has_key.hpp boost/fusion/view/ext_/segmented_iterator.hpp boost/function/function_template.hpp boost/regex/pending/unicode_iterator.hpp Patch is attached. Safe to apply? Greetings, Thomas

1 0

Re: [boost] [lexical cast] Performance improvements
by Antony Polukhin 20 Mar '11

20 Mar '11

>Just one quick question, does your code have the same behaviour as the existing Lexical Cast when casting out of bounds (int -> unsigned int, int -> short, unsigned int -> int)? > >Chris Yes. It has the same behaviour. For checking bounds it uses boost::numeric::conversion_traits from <boost/numeric/conversion/conversion_traits.hpp> Antony

1 0

[context review] Review starts next Monday, Mars 21st
by Vicente BOTET 20 Mar '11

20 Mar '11

Hi all, The review of Oliver Kowalke Context library starts next Monday Mars 21st 2011, and will end on Mars 30th. Boost.Context is a basic building block library that is used for more higher abstractions. It is used by Boost.Fiber, Boost.Tasklet and Boost.Task from the same author. I really hope to see your vote and your participation in the discussions on the Boost DEVELOPMENT mailing lists! Please use [context review] as prefix of your post to make easier the review follow up. You can already download a frozen version for the review from the Vault, TinyURL: http://tinyurl.com/5r77rel or --------------------------------------------------- About the library: Boost.Context provides a possibility to switch between different user-level context and is intended to be the basis for a higher abstraction like coroutine and fiber. A user-level context represents the current execution state, including all registers and CPU flags, the instruction pointer, the stack pointer. boost::context encapsulates such a user-level context and is able to store/restore its associated user-level context. This allows multiple execution paths running on a single thread using a sort of cooperative scheduling (in contrast a thread is preemptively scheduled) - the running boost::context decides explicitly when its yields to allow another boost::context to run (user-level context switching). A context can only run on a single thread at any point in time but may be migrated between thread. A context switch between threads costs usually thousands of CPU cycles on x86 compared to a user-level context switch with few hundreds of cycles. Boost.Context differes to setjmp()/longjmp() in the fact that the C99 standard does not require that longjmp() preserves the current stack frame, e. g. jumping into a function which was exited via a call to longjmp() is undefined. Boost.Context allows to select the mechanism provided by the operating system (ucontext on UNIX, Windows Fibers on Windows) or a faster implementation provided by this library (fcontext using assembler). --------------------------------------------------- Please always state in your review, whether you think the library should be accepted as a Boost library! Additionally please consider giving feedback on the following general topics: - What is your evaluation of the design? - What is your evaluation of the implementation? - What is your evaluation of the documentation? - What is your evaluation of the potential usefulness of the library? - Did you try to use the library? With what compiler? Did you have any problems? - How much effort did you put into your evaluation? A glance? A quick reading? In-depth study? - Are you knowledgeable about the problem domain? Regards Vicente Review Manager

2 1

Status of boost-build at sourceforge?
by Steve M. Robbins 19 Mar '11

19 Mar '11

Hi, The Boost Sourceforge project has a bunch of directories that appear un-maintained. The following are all a year or more old; are they still relevant? boost-jam 2010-03-22 707,245 downloads boost-build 2007-10-01 174,174 downloads boost-subparts 2006-11-09 In particular: Debian has packages based on boost-build, but I'm not sure really if these 3-year old files have any value today. Do they? Thanks, -Steve

1 0

GSOC: concept_traits
by Vicente Botet 19 Mar '11

19 Mar '11

Hi, Now that we will have operator traits with the reviewed library and member traits macros with Boost.TTI, it left just to define the traits for the concepts/requirements of standard library and why not some boost libraries. This would completely resurrect the abandoned ConceptTraits library. Could be this an acceptable subject for GSOC? Thanks, Vicente -- View this message in context: http://boost.2283326.n4.nabble.com/GSOC-concept-traits-tp3388859p3388859.ht… Sent from the Boost - Dev mailing list archive at Nabble.com.

2 3

[1.47] New libraries
by Daniel James 19 Mar '11

19 Mar '11

As far as I'm aware, there are three new libraries intended for 1.47 - chrono, ratio and geometry. Any others? Daniel

13 19

[Review] Boost.Type Traits Extension by Frederic Bron
by Edward Diener 19 Mar '11

19 Mar '11

This is my review of the Boost Type Traits Extension by Frederick Brron. * What is your evaluation of the design? The design is very straightforward, and easy to use. Although I do not anticipate the need to check the return from the operator traits I am glad that is part of the library. The only suggestion I would like to make regarding the design is in the default argument for the return value, which tells the implementation not to check for the return value. While it is wildly improbable that any user of the operator traits would actually want to have a trait whose return is actually 'void', it is still theoretically possible. Therefore I think that the default for the return value, which means to not check for the return value, should be an unspecified marker type in the type_traits::detail namespace. It is a convention of all Boost libraries that any library's detail namespace is to be used only by the implementation of that library and not by a user of that library. So using an unspecified marker type in the type traits detail namespace should be fine. * What is your evaluation of the implementation? I did not look at the source code. I do have a large reservation from reading the documentation, so let me explain it now. The ideal situation when using template metaprogramming constructs, such as the type traits operators metafunctions, is that an instantiation of the metafunction should never produce a compiler error. This is particularly true of metafunctions which return a boolean constant value, since the boolean value can encapsulate the notion of true or false when using the metafunction based on input types. Of course it may be the nature of C++ that this ideal situation can not be met. But then the user of the metafunction has to be able to instruct his end-users about whatever limitation exists and make allowance for it. In the type traits operators library there are documented two major situations where the use of a type will produce a compiler error and not just a false boolean constant value. This is a painful situation. I realize these two situations are fully documented in the "Known Issues" area of the Operator Type Traits documentation. But now let us take a look at the template metaprogrammer who wishes to use some subset of the type traits operators in his own library based on a type his end-user may pass to him. What this programmer wishes to do is to use a type traits operator if a type passed to him supports it, otherwise not use the operator at all. Unfortunately the end-user of that library passes a type which may or may not support such functionality, not knowing that the type will trigger a compiler error because the type traits operators are being used internally and some known issues exist which that type encompasses. What that template metaprogrammer must then do is to add another template parameter to his template, and documentation which explains to his end-user the specific situations whch trigger compiler errors in the type traits operators, that if a type is being passed which could cause the type traits compiler error conditions he must set this other parameter to false so that the compiler error can be avoided. This is a difficult way to program metafunctions successfully. So it is very disappointing that these "Known Issues" exist and it would be very worthwhile if a way could be found around them, by something different in the internal implementation, if that were possible. * What is your evaluation of the documentation? The documentation is thorough and complete. * What is your evaluation of the potential usefulness of the library? I think it is very useful. * Did you try to use the library? With what compiler? Did you have any problems? Tested with VC 8,9,10 and everything worked as expected. I have also integrated into another library on which I am working and that was successful also. * How much effort did you put into your evaluation? A glance? A quick reading? In-depth study? I read the docs, tested the library under Windows, and tried it in my own library, so it was pretty thorough. * Are you knowledgeable about the problem domain? Yes. And finally, every review should answer this question: * Do you think the library should be accepted as a Boost library? Be sure to say this explicitly so that your other comments don't obscure your overall opinion. I vote for the library to be accepted into Boost. I would also like to see if the "Known Issues" could not be solved, not necessarily by the author of the library who has put so much effort and work into it, but possibly by other Boost experts who might find some solution to these issues which mar the library somewhat for me. But even if these issues could never be solved the library is worthwhile enough to be accepted. Edward Diener

3 5