Low performance on max profit problem

[Anonymous]

Hi,

I am currently working on a problem where I need to optimize the profit of "one worker resource" problem :
For a list of trip defined with name, start time, length and gain, I need to return the solution with the best profit,  the sorted list of trip used and without conflict on trips. Basically, I need to select trips in want to choose and ignore the rest as long as I get the best profit.

For the following list :
          { name: "MONAD42", start time: 0, length: 5, gain: 10 },
          { name: "META18", start time: 3, length: 7, gain: 14 },
          { name: "LEGACY01", start time: 5, length: 9, gain: 8 },
          { name: "YAGNI17", start time: 5, length: 9, gain: 7 }
The result is :
          { gain: 18, path: }

I have tried several constraint models but I soon reach a threshold where performance goes down. My goal is  to solve this problem in less than 30s with an input of 50000 trips.

I always start by creating BooleanVar defining if a trip is used and ending with a SumWeight on those BooleanVar and trip gains. The SumWeight var is then passed as the first variable in a DepthFirstSearch with an IndomainMax.
In order to simulate the trip conflict, I tried to impose ExtensionalSupportVA/MDD/STR constraints, Cumulative constaints, Sequence decomposed constaints and Among constraints.

I looked at BinPacking constraints but was not able to apply them to this problems. Perhaps I missed the point ?

Thanks in advance.

[kris]

Hi!

In general, you have two parts in CP that influence solving time. First, the constraints of the model and second, the search. I would suggest that you try to consider both in your solution along the lines I try to sketch below. Of course, the worst complexity of search is always exponential and you might not be able to escape from this if a problem belongs to this class of problems (I mean, NP-hard).

1. You should try to use global constraints to define conflicting situation and the way it can be communicated to search. For example, if you define "start time" as domain variable with domain, for example  {0, 1000..10000} for trip starting at 0. Then you can use cumulative constraint to select trips when assigning minimal start time or moving them to "the end of time" when not selected and not considered. In this way you will be able to make search on start time and not on boolean varibales. You can still use boolean variables by reifiing start time variables.

2. If you have start time variables you can define search on these variables and use heuristic to select based on, for example SmallaestMin. You can use even more advanced search by combining gain (as variable) and start time and select it on SmallestMas (selecting the highest gain first). For this you can use SimpleMatrixSelect (section 2.4 and appendix B.3 in JaCoP Guide).

This is, of course, my quick suggestion but you may consider other solutions. The idea is to avoid search on boolean varibales that loose problem structure and you are not able to use variable selection heuristics.

Best,
/Kris

[Anonymous]

Thanks for your response.

I will try your advices and keep you informed with the progress.