Large model

[Mauro Rozenberg]

Hello.
I'm starting a new project but it's getting too large (too many
variables).
Let me explain you what I'm doing because I'm sure there are better
ways to solve it.
The problem I'm trying to optimize is a conference where costumer have
several meetings with other costumers. Each costumer (there are 500)
gave me a priority list of other costumers they want to meet with.
The model has 500 costumer that can meet with the same 500 in 24
different 30 minute blocks each of the 2 days. So, I made the
cartesian product of all this which gave me 12 millon binary variables
(500 x 500 x 24 x 2). Way too much for such a simple problem.
The variable I'm trying to maximize is the sum of a certain value I
gave to each meeting according to costumers' priority. And the
contrains are that a costumer can have no more than 1 meeting in each
block, not having more meetings than rooms, etc.

Thanks,
Mauro.

[Sergio Bruno]

Mauro,

nice problem.

your variable is Meet(cust1,cust2,timslot,day) in {0,1}
you could declare an integer variable Meet(cust,timslot,day) in
custumers that tells you who meets who. This would reduce number of
variables and memory comsumption. but still your instance would be
probably hard to solve.
Unless you have several other constraints, I would suggest you to try
to fit your problem in some classic literature problem (network flow ,
matching, ..) and use a specialized algorithm.

best
Sergio

> --
> You received this message because you are subscribed to the Google Groups "AIMMS - The Modeling System" group.
> To post to this group, send email to ai...@googlegroups.com.
> To unsubscribe from this group, send email to aimms+un...@googlegroups.com.
> For more options, visit this group at http://groups.google.com/group/aimms?hl=en.
>
>

[Marcel Roelofs]

Another question you can ask yourself is: how many people are
interested in meeting in the first place. If MeetingPriority(c1,c2) is
0 when c1 isn't interested in meeting c2, then you can use this as a
domain condition on your variable. If the average person is only
interested in meeting let's say 5% of the other participants, then ...
poof ... only 600000 variables left. Still a lot, but much more
manageable then 12 million. How many meetings are realisticly
realizable on average is determined by the amount of available rooms,
but 48 is certainly the max. On the other hand, how many people are
capable of having 48 meaningful 30-minute meetings in 2 days? If c1
wants to meet c2, but c2 doesn't want to meet c1, then do you want to
consider them meeting at all?

I would say, lots of opportunity to reduce the domain size.

Cheers,
Marcel

[Mauro Rozenberg]

Exactly! Most of the meeting are worthless (their value or priority is
0).
How do I insert a domain condition? Shall I put in the Index Domain
'c1, c2, day, time | value(c1, c2) > 0'?

Thanks!
Mauro.

> > Mauro.- Ocultar texto de la cita -
>
> - Mostrar texto de la cita -

[Marcel Roelofs]

Yes, or maybe even

(c1,c2,day,time) | value(c1,c2) and value(c2,c1)

if you only intend to consider a meeting if both parties want it.

Cheers,
Marcel

[Hanagandi]

Hi:
We had solved this problem for a large prime brokerage company with
3000 attendees in their conference.
That problem also had tiers of attendees (like silver, gold, platinum,
etc) and we exploited that to do a sequential solve - each
progressively smaller and smaller. We were able to solve the problem
in less than 1 hr using CPLEX.

-vijay
_____________
Vijay Hanagandi
Optimal Solutions, Inc.,
17 Kershaw Ct.,
Bridgewater, NJ 08807

Phones:
(908) 393 1316 (Land)
(812) 205 8551 (Cell)
-------------------------------------------------------------------------------
We are presenting at the 2011 INFORMS Practice Meeting in Chicago
(April 10-12). Please feel free to attend our presentation on Run
Strategy
-------------------------------------------------------------------------------

[Sergio Bruno]

Exactly! This should make your life easier.let's hope that the problem is solvable in reasonable time.

Em 23/03/2011 15:19, "Mauro Rozenberg" <maur...@gmail.com>escreveu:

Exactly! Most of the meeting are worthless (their value or priority is
0).
How do I insert a domain condition? Shall I put in the Index Domain
'c1, c2, day, time | value(c1, c2) > 0'?

Thanks!
Mauro.

On 23 mar, 12:37, Marcel Roelofs <marcel.roel...@gmail.com> wrote:

> Another question you can ask y...

> > Mauro.- Ocultar texto de la cita -
>
> - Mostrar texto de la cita -

--
You received this message because you are subscribed to the Google Groups "AIMMS - The Modeling...