can Cost be int32_t and handle negative costs?

[mgalati13]

Is there any reason why using Cost=int32_t would be an issue if some of the edge costs are negative? I am thinking about using VROOM in a column generation algorithm which would be minimizing reduced costs (so, some of the edges costs would be negative).

[jcoupey]

I don't have any reason in mind right now why this would fail. BUT it's very easy to overlook some details that may require adjustments to get that working. So your best bet is to try! You want to use debug mode so that the assertions we have in place may catch unwanted situations.

I'd be interested by any feedback regarding using negative values, alternatively maybe you can simply shift your value scale to have only positive costs?

Anyway I'd also be interested on feedback if you use VROOM as a part of solving another non VRP-related problem.

[nurikk]

Id love to see cost int64, sometimes (1-2k tasks on 400-500km distance) might cause error in this place https://github.com/VROOM-Project/vroom/blob/990565b465ae270adfc6317a11a3687f9f25e99d/src/utils/helpers.h#L39

[jcoupey]

@nurikk the error you're seeing is related to many high costs in the input problem, not having signed values for costs. You can raise the limit by switching to uint64_t here.

[nurikk]

@nurikk the error you're seeing is related to many high costs in the input problem, not having signed values for costs. You can raise the limit by switching to uint64_t here.

Yeah, but I’m quite reluctant to fork out the project only for one line change. I ended up getting distance matrices values scaled down by 100 😁

[nurikk]

@nurikk the error you're seeing is related to many high costs in the input problem, not having signed values for costs. You can raise the limit by switching to uint64_t here.

btw i'm noticed that in typedef https://github.com/VROOM-Project/vroom/blob/990565b465ae270adfc6317a11a3687f9f25e99d/src/structures/typedefs.h#L38 capacity is defined as int64_t (signed) but in input_parser https://github.com/VROOM-Project/vroom/blob/990565b465ae270adfc6317a11a3687f9f25e99d/src/utils/input_parser.cpp#L73 it's retrieved as GetUint unsigned is it intentional or some bug? I can raise a PR with change

[mgalati13]

I was able to test this by changing both Cost and Duration. I don't think we should change Duration to int32_t, as unsigned makes sense here. But, I was unable to change just Cost because there is a copy of duration matrix to cost matrix under certain conditions.

I tested a very basic example and it seemed fine.

I also benchmarked Solomon VRPTW adn there was no negative effect on time or objective obtained.

So, on the surface, it seems like Cost=int32_t works fine with negative costs.

[jcoupey]

Thanks @mgalati13 for this feedback. Please send some more if you go deeper into using negative costs. Also still interested by any outcome if you manage to use VROOM as a sub-routine in a broader optimization approach! ;-)

[mgalati13]

@jcoupey - I will definitely report back once I get further along. Admittedly this is just a research idea and might take a while to flush out. I did my thesis on column generation and I want to try to utilize VROOM as a sub-routine to exactly solve these VRP variants using VROOM in conjunction with the typical resource-constrained shortest path pricing approach. Theoretically, we could also use VROOM to solve other variants of VRPs not yet covered by VROOM using a similar idea.

[mgalati13]

In my thesis, I called this nested polyhedra: https://coral.ise.lehigh.edu/magh/pub/decomp_Defense09.pdf

[nurikk]

In my thesis, I called this nested polyhedra: https://coral.ise.lehigh.edu/magh/pub/decomp_Defense09.pdf

You should definitely choose more readable text colours. Half of the document can’t be read

[mgalati13]

Those are overlays - which display as you click through. If you are viewing it in a browser, expand to fit to window, and then page down through the overlays / slides.

[jcoupey]

Closing here since the discussion in not active any more. Note that this topic may be somehow related to #738.