Help optimising an optimisation model

A place to discuss the implementation and style of computer programs.

Moderators: phlip, Moderators General, Prelates

User avatar
ConMan
Shepherd's Pie?
Posts: 1631
Joined: Tue Jan 01, 2008 11:56 am UTC
Location: Beacon Alpha

Help optimising an optimisation model

Postby ConMan » Thu Sep 08, 2016 6:26 am UTC

So, I think this one just barely falls on the "computational" side of computational mathematics, hence my asking here.

I'm taking an online course on modelling discrete optimisation using MiniZinc, and for the final assessment I've hit a roadblock, so I was hoping someone might be able to offer a little insight. I'm still aiming for the submission to be my own work, so general advice is fine. In essence, I need to build the model in stages, adding more constraints as I go, and there's a point where my model doesn't run fast enough to meet submission requirements, so I know I have to improve either the constraints, or the search strategy (i.e. the order in which possible values for each variable are selected to work out whether there's a potential solution), or both.

The problem is a combination packing and scheduling one. Items are stacked on a dock, where they take up (linear) space equal to their size. They then sit there until they're reclaimed and loaded onto a ship. So that gives the first bunch of constraints - essentially they take up little rectangles in space-time of length <size> and duration <stack-time + time spent sitting around doing nothing + reclaim time>. Thankfully, MiniZinc has a built-in "pack the rectangles nicely" global constraint, all well and good and all the test data finds solutions in less than a second.

Second constraint, there are a limited number of "reclaimers", and each item needs to be assigned a reclaimer during its "reclaim time" such that no other item is using the same reclaimer at the same time. Still fine, there's a "don't let these intervals overlap" global constraint that I can apply to make that work, and I can even chuck in a couple of redundant constraints about "don't use more reclaimers than there exist at any time, and don't have a reclaimer spend more time reclaiming than there is time to reclaim stuff" that speed things up a little. Still doing pretty good.

Third constraint, the item can't be reclaimed until the ship it's meant to go on shows up, and just like not doubling up on reclaimers, you can't reclaim two things onto the same ship at the same time. The second part of that is exactly the same as getting the reclaimers constraint working, and the first one is just ensuring that reclaim[s] >= arrival[ship[s]]. At this stage, I haven't had to mess with the search strategy much and all the test data is still running super-fast.

Now, the bit I'm stuck on: the reclaimers can only move so fast. So in theory, all I need to do is add a constraint that for two items being reclaimed by the reclaimer, the distance between them can't exceed the distance the reclaimer can move between one finishing and the other starting. But. Doing it the obvious way (looping over all pairs of items on the same reclaimer) is far too slow - I was getting no results in a reasonable time frame for the test datasets other than the trivial ones. I added an additional array that would identify, for a given item, what the "next" item using the same reclaimer would be, to reduce the number of pairs to check, and at this point I've reduced the time to get a solution down to around 15 minutes, where my limit is 5. I also added some more redundant constraints, and messed with the search order so that it's trying values for the "chunkiest" variables first (which reclaimer to use, the location on the dock, and which item is reclaimed next all have fairly small domains, whereas the decisions around when to stack and reclaim are from a relatively large time domain so I've left them until last).

There are two stages after this, but I'm pretty sure that if I can get this stage working then I can scrape by some passing marks for the rest. Any thoughts on improving my model are welcome - in the interest of sticking to the course's honour code, I'll avoid discussing too much specific code here but I can go into a little more detail over PM. Also, I'm completely open to being told that I've potentially done something wrong earlier on that happened to produce correct results *then*, but is messing me up now.
pollywog wrote:
Wikihow wrote:* Smile a lot! Give a gay girl a knowing "Hey, I'm a lesbian too!" smile.
I want to learn this smile, perfect it, and then go around smiling at lesbians and freaking them out.

korona
Posts: 495
Joined: Sun Jul 04, 2010 8:40 pm UTC

Re: Help optimising an optimisation model

Postby korona » Thu Sep 08, 2016 7:19 am UTC

I find it a bit hard to follow what the problem is. Can you state the data that is associated with each { item, ship, reclaimer }? Which part of that data is given by the input and what variables are optimized over? What is the objective function? What are the exact constraints?

EDIT: Is the assignment openly available? In that case you could maybe just link it.

EDIT: What about introducing variables timereq[i] = "time between reclamation i and i + i at a certain reclaimer" and itemdist[i] = "distance between item i and item i + 1 where both items are reclaimed by that reclaimer" (even though I don't understand what the distance of two items is if they are all stored on a stack and only the top element can be reclaimed?) and ensuring that timereq[i] * reclaimer_speed >= itemdist[i]? That only introduces a linear (and not quadratic) number of constraints.

User avatar
Zamfir
I built a novelty castle, the irony was lost on some.
Posts: 7302
Joined: Wed Aug 27, 2008 2:43 pm UTC
Location: Nederland

Re: Help optimising an optimisation model

Postby Zamfir » Thu Sep 08, 2016 8:47 am UTC

Not sure if this helpful, but something like this has helped me in the past on similar problems:

What if you recast the model to focus on the reclaimers? For example, you maintain a 2d array of reclaimers and time, where every slot is a position integer (or a float). There is a second , boolean, 2d array recording whether a reclaimer is 'moving' or 'reclaiming'. Positions cannot differ too much from their predecessor (limited by the speed constraint, and zero if reclaiming). The reclaimer has to spend sufficient time reclaiming at some positions to move an item. Different reclaimers cannot be reclaiming at the same position at the same time. A ship and an item have to be present before a reclaimer can reclaim, which then pulls in the other aspects of the problem into the model.

Alternatively, each reclaimer is a list of reclaim actions, each action is a tuple (start time, end time, reclaim position), again with constraints to make it consistent. This has less variables, but it might be time consuming to check for clashes between reclaimers.

User avatar
ConMan
Shepherd's Pie?
Posts: 1631
Joined: Tue Jan 01, 2008 11:56 am UTC
Location: Beacon Alpha

Re: Help optimising an optimisation model

Postby ConMan » Thu Sep 08, 2016 11:04 pm UTC

The good side of MiniZinc is that you can basically use all the data structures you need and apply the relevant constraints to the bits where it makes most sense. So, for example, I currently have arrays that, for each item, contain the west and east positions, the times that stacking and reclaiming start and end, the duration between those, etc. I could *also* have, for example, a 2d array of dimension length x time that would say what item is taking up a particular spot on the dock at a given time, and through careful selection of constraints make it match up with the other arrays, but I'm *pretty* sure it won't be particularly helpful (but there might be some other view of the problem that could help, and I will try Zamfir's suggestion of tracking what the reclaimers are doing because it sounds plausible).

Also, please feel free to ignore the word "stack". It's the word used in the assignment to mean "put onto the dock in its given location", but it is not a stack in the programming sense - you can always access all items that are on the dock.
pollywog wrote:
Wikihow wrote:* Smile a lot! Give a gay girl a knowing "Hey, I'm a lesbian too!" smile.
I want to learn this smile, perfect it, and then go around smiling at lesbians and freaking them out.

korona
Posts: 495
Joined: Sun Jul 04, 2010 8:40 pm UTC

Re: Help optimising an optimisation model

Postby korona » Fri Sep 09, 2016 3:43 pm UTC

ConMan wrote:The good side of MiniZinc is that you can basically use all the data structures you need and apply the relevant constraints to the bits where it makes most sense. So, for example, I currently have arrays that, for each item, contain the west and east positions, the times that stacking and reclaiming start and end, the duration between those, etc.

Sure, but I was not talking about your model but about the problem itself. The problem statement is incredibly vague. If there was a more precise statement it would be much easier to talk about possible models. Something along the lines of:

Input: You are given the following data:
* A number R of reclaimers, each of which move at a maximal speed Vmax (Do they have some fixed starting point on the dock? Are they point-like or do they have an extent along the dock axis?)
* A number S of ships where every ship has an arrival time A(i) (Or maybe this arrival time is not part of the input but a variable? Do they have a departure time?)
* A list of items that each have a one-dimensional size L(i) and a destination ship D(i) (Is this ship part of the input or a variable?)
...

Problem: Chose the following variables:
* The time Tsched(i) and the location Xsched(i) at which item i arrives at the dock
...
so that the following conditions hold
* No two items overlap each other on the dock
...
and the makespan of the schedule is minimized. (Or maybe some other objective is optimized? Or we might just have to find a feasible solution?)

User avatar
ConMan
Shepherd's Pie?
Posts: 1631
Joined: Tue Jan 01, 2008 11:56 am UTC
Location: Beacon Alpha

Re: Help optimising an optimisation model

Postby ConMan » Sun Sep 11, 2016 10:45 pm UTC

Fair enough. The data is (everything is in integers):

Number of reclaimers (nr)
Number of items/stockpiles (ns)
Number of ships (nsh)
Array of the sizes of the stockpiles (size)
Array of the ships for each stockpile (ship)
Length of the dock (len)
Maximum time to fit everything in (maxtime)
Array of arrival times for ships (arrival)
Time it takes to load an object of size 1 (stack_time)
Time it takes to reclaim an object of size 1 (reclaim_time)
Time it takes reclaimer to move 1 distance unit (reclaim_speed)

Then the output is arrays for each item of:
The westmost position (westend)
The eastmost position (eastend = westend + size)
The time stacking starts (stack)
The time stacking ends (endstack = stack + size * stack_time)
The time reclaiming starts (reclaim)
The time reclaiming ends (finished = reclaim + size * reclaim_time)
Which reclaimer is used (which)

Constraints at this stage are:
Everything fits onto the pad over time
Each reclaimer is only used once at any point in time
Each ship on has one thing reclaimed onto it at any point in time
Stuff is only reclaimed onto ships after the ship arrives
Reclaimers don't move too fast (they have no fixed start point, so I can just assume they start where they need to, and for simplicity they always just sit at the westend point for the item when they reclaim it)

At this stage, I'm just searching for feasible solutions - there's an objective function to minimise in the next step which is the total time all the ships are around, but I'll deal with that next.

So the broad version of the model for the constraints up to the ship-related ones is basically just:

Code: Select all

diffn( westend, stack, size, duration ); (where duration = the time from stack to finished)
diffn( reclaim, which, rectime, oneperstock ); (rectime = size * reclaim_time, oneperstock is just an array of 1s)
diffn( reclaim, ship, rectime, oneperstock );
forall(s in 1..ns)( arrival[ship[s]] <= reclaim[s] );


Where diffn(x, y, dx, dy) is a global constraint that says that the rectangles with corners at (x, y) and size (dx, dy) don't overlap.

Then I created the predicate:

Code: Select all

rec_speed ( var POSITION: startpos, var TIME: starttime, var POSITION: endpos, var TIME: endtime ) =
                    abs( endpos - startpos ) <= ( endtime - starttime ) * reclaim_speed;


And then used it in the constraint

Code: Select all

forall(s in 1..ns where next[s] <= ns)( rec_speed(westend[s], westend[next[s]], finished[s], reclaim[next[s]] );

Where next is the array of the next item to be reclaimed on the same reclaimer (including some extra dummy ones on the end for the last item reclaimed by each reclaimer).

And, as I said, I've added a few redundant constraints to the model to improve the running speed, but it still hasn't been enough to let me pass at this stage. The search strategy I'm using at the moment is to search the variables in the order which, westend, next, reclaim, stack, on the basis that the first variables are the ones with smaller domains that will help constrain the possible values for the later ones. I haven't seen a huge difference in the run times starting with the minimum values of each domain and the median, which are the two main deterministic search methods supported by MiniZinc.
pollywog wrote:
Wikihow wrote:* Smile a lot! Give a gay girl a knowing "Hey, I'm a lesbian too!" smile.
I want to learn this smile, perfect it, and then go around smiling at lesbians and freaking them out.


Return to “Coding”

Who is online

Users browsing this forum: No registered users and 7 guests