Is it possible to program weighted constraints in JaCoP?
I need something (for boolean variables) like "if v1=1 and v2=1 then I have to pay 10 more for a solution including this assignment, otherwise 0"
I I need to find the solution with a global cost of 80 (for example) or, in another case, to minimize the global cost of the solutions.
Thank you very much,
Francesco
If you would like to refer to this comment somewhere else in this project, copy and paste the following link:
You can do weighted constraints in many different ways.
The best way if it is possible (memory is not an issue) then you should use ExtensionalSupport* constraints. For your example, you specify a tuple where first variable is v1, second v2, and the third is the cost of the assignment. You can specify different costs for any combination of v1 and v2. This way you will get GAC for your constraints, but you may have a lot of possible assignments and thus run out of memory to express them in this extensional form.
You can also use logical constraints, Eq, IfThen, IfThenNot, Reified, etc, e.g. new Eq(new And(new XeqC(v1, 1), new XeqC(v2, 1)), new XeqC(additionalCost, 10)). However, these type of constraints should only be used if for few assignments there is some cost and for majority of others (still possible assignments) the cost is 0.
If you are more specific about your particular problem, I may give you a better hint what would be the best way to approach your problem.
best,
Radek
If you would like to refer to this comment somewhere else in this project, copy and paste the following link:
Hi, I have a system I think that can be solved by Weighted constraints.
I have tasks which are messaging between each other.
Each task is running on an agent. An agent runs only one task at a time. Agents are running on some containers in a network.
Agents which are in the same container are physically running in the same machine at the network.
Task messaging rate is inconsistent. For example task A is messaging task B with 30 messages/minute at a time.
But after a few time the messaging rate could be 80 messages/minute. I want to move the task that is highly messaging with other task to the same container.
I want to schedule these tasks to that agents with weighted constraints(calculate with a cost function).
Problem definition example:
-Cost of running task A and B at different machine which has 80(messaging rate) cost.
-And an task(task C) has a strict commitment on a machine(container X) because of a physical device for example .This means that cost of task C not running at the container X has cost 9999(infinite).
-Moving a task(task D) from one container to other has a cost of 30.Moving task D from container Z to container Y.
-Initial locations of tasks are known.
-Agents' containers are known.
Is there any way of calculating minimum cost and constraint values of variables using weighted constraints for that example?
Can we define cost functions in Jacob?
thanks.
Zafer.
If you would like to refer to this comment somewhere else in this project, copy and paste the following link:
There is a number of questions in your text, mostly about modeling with constraints. I will not be able to give you a model in my answer but I will try to point out different possibilities.
First, of course you can optimize with JaCoP and find the minimum of your cost function. Any IntVar can be used to define cost for minimization. You suggest the result of weighted sum and it is perfectly OK.
In your CP model, you are not limited to linear equations as in ILP models. You can use all constraints provided by JaCoP. One hint is to use reified constraints to find out communication needs in your case. If, for example, you will introduce a variable m_i defining the machine for executing task i you may check if tasks i and j are on different machines by imposing constraint Reified(new XneqY(m_i, m_j), b_ij). If b_ij = 1 then it means that tasks i and j have been assigned to different machines otherwise there are assigned to the same machine. You may later use this variable to compute, for example communication costs.
Regards,
/Kris
If you would like to refer to this comment somewhere else in this project, copy and paste the following link:
I guess it is not possible to put everything in one container. What makes it impossible? Only the hard constraints that assign some items to some predefined containers or is there other constraint capacity like that restricts total number
of items per container?
I will simplify your description a bit. You have a problem of assigning tasks to machines and for some pairs of tasks if they are assigned to different machines you pay communication costs. Some tasks are preassigned to some machines and can not be moved, others can be moved with a given communication cost. Now, you have to figure out if you can reassign tasks in such a way that you reduce overall communication costs.
You should have one set of variables ( A ) specifying current assignment of tasks to machines. You also have one set of variables ( B ) specifying the future assignment of tasks to machines. If task is fixed to a machine then you have equality constraint between respective assignment variables ( a_i = b_i ).
Now, for every a_i and b_i and moveCost_i you specify an ExtensionalSupport* constraint detailing possible costs for different moving options. It may be more efficient to try simple approach Eq(new XeqY(a_i, b_i), XeqC(moveCost_i, 0))
and have moveCost have only two values in the domain 0 and actualCost of moving task.
Very similiar approach you use to connect b_i and b_j and costCommunication_ij, if b_i and b_j are different then cost of communication is different from zero.
Now, you have Sum constraints summing all the costs and the sum variable is your global cost variable.
This approach could be improved if you analyse communication graph between tasks and focus on large groups of tasks (cliques or almost cliques) and start to assign those first in search. I will also focus on MaxRegret variable ordering heuristic when you choose pairs that if assigned to different machines yield the highest communication costs and you put them together on one machine ( same_ij = 1 , see below).
It is not an easy problem because anything that is sum over many many variables will be tough on CP to optimize. You need to have good search to find good solutions.
You also have a potential problem of symmetry as some containers may be indistinguishable. If it is the case you should introduce binary variables same_ij that specify if two tasks execute on the same machine. You create master search that decides about relative placement of tasks. Depending on the answer to my intial question you may be always able to extend master solution to a final solution that actually assigns tasks to specific machines. Even if tasks are fixed to a specific containers this constraint will immediately propagate when same_ij are being assigned values.
Also, for some pairs of tasks that communication costs are low you could ignore the corresponding same_ij variable from the optimization search and only fix it later when you find an optimal solution for partial problem (only significant pairs). You loose proof of optimality but you may not be far away from global optimal solution.
Hope that helps.
Radek
If you would like to refer to this comment somewhere else in this project, copy and paste the following link:
Is it possible to program weighted constraints in JaCoP?
I need something (for boolean variables) like "if v1=1 and v2=1 then I have to pay 10 more for a solution including this assignment, otherwise 0"
I I need to find the solution with a global cost of 80 (for example) or, in another case, to minimize the global cost of the solutions.
Thank you very much,
Francesco
Hi,
You can do weighted constraints in many different ways.
The best way if it is possible (memory is not an issue) then you should use ExtensionalSupport* constraints. For your example, you specify a tuple where first variable is v1, second v2, and the third is the cost of the assignment. You can specify different costs for any combination of v1 and v2. This way you will get GAC for your constraints, but you may have a lot of possible assignments and thus run out of memory to express them in this extensional form.
You can also use logical constraints, Eq, IfThen, IfThenNot, Reified, etc, e.g. new Eq(new And(new XeqC(v1, 1), new XeqC(v2, 1)), new XeqC(additionalCost, 10)). However, these type of constraints should only be used if for few assignments there is some cost and for majority of others (still possible assignments) the cost is 0.
If you are more specific about your particular problem, I may give you a better hint what would be the best way to approach your problem.
best,
Radek
Hi, I have a system I think that can be solved by Weighted constraints.
I have tasks which are messaging between each other.
Each task is running on an agent. An agent runs only one task at a time. Agents are running on some containers in a network.
Agents which are in the same container are physically running in the same machine at the network.
Task messaging rate is inconsistent. For example task A is messaging task B with 30 messages/minute at a time.
But after a few time the messaging rate could be 80 messages/minute. I want to move the task that is highly messaging with other task to the same container.
I want to schedule these tasks to that agents with weighted constraints(calculate with a cost function).
Problem definition example:
-Cost of running task A and B at different machine which has 80(messaging rate) cost.
-And an task(task C) has a strict commitment on a machine(container X) because of a physical device for example .This means that cost of task C not running at the container X has cost 9999(infinite).
-Moving a task(task D) from one container to other has a cost of 30.Moving task D from container Z to container Y.
-Initial locations of tasks are known.
-Agents' containers are known.
Is there any way of calculating minimum cost and constraint values of variables using weighted constraints for that example?
Can we define cost functions in Jacob?
thanks.
Zafer.
Hi!
There is a number of questions in your text, mostly about modeling with constraints. I will not be able to give you a model in my answer but I will try to point out different possibilities.
First, of course you can optimize with JaCoP and find the minimum of your cost function. Any IntVar can be used to define cost for minimization. You suggest the result of weighted sum and it is perfectly OK.
In your CP model, you are not limited to linear equations as in ILP models. You can use all constraints provided by JaCoP. One hint is to use reified constraints to find out communication needs in your case. If, for example, you will introduce a variable m_i defining the machine for executing task i you may check if tasks i and j are on different machines by imposing constraint Reified(new XneqY(m_i, m_j), b_ij). If b_ij = 1 then it means that tasks i and j have been assigned to different machines otherwise there are assigned to the same machine. You may later use this variable to compute, for example communication costs.
Regards,
/Kris
Hi Zafer,
Your post is missing one important info.
I guess it is not possible to put everything in one container. What makes it impossible? Only the hard constraints that assign some items to some predefined containers or is there other constraint capacity like that restricts total number
of items per container?
I will simplify your description a bit. You have a problem of assigning tasks to machines and for some pairs of tasks if they are assigned to different machines you pay communication costs. Some tasks are preassigned to some machines and can not be moved, others can be moved with a given communication cost. Now, you have to figure out if you can reassign tasks in such a way that you reduce overall communication costs.
You should have one set of variables ( A ) specifying current assignment of tasks to machines. You also have one set of variables ( B ) specifying the future assignment of tasks to machines. If task is fixed to a machine then you have equality constraint between respective assignment variables ( a_i = b_i ).
Now, for every a_i and b_i and moveCost_i you specify an ExtensionalSupport* constraint detailing possible costs for different moving options. It may be more efficient to try simple approach Eq(new XeqY(a_i, b_i), XeqC(moveCost_i, 0))
and have moveCost have only two values in the domain 0 and actualCost of moving task.
Very similiar approach you use to connect b_i and b_j and costCommunication_ij, if b_i and b_j are different then cost of communication is different from zero.
Now, you have Sum constraints summing all the costs and the sum variable is your global cost variable.
This approach could be improved if you analyse communication graph between tasks and focus on large groups of tasks (cliques or almost cliques) and start to assign those first in search. I will also focus on MaxRegret variable ordering heuristic when you choose pairs that if assigned to different machines yield the highest communication costs and you put them together on one machine ( same_ij = 1 , see below).
It is not an easy problem because anything that is sum over many many variables will be tough on CP to optimize. You need to have good search to find good solutions.
You also have a potential problem of symmetry as some containers may be indistinguishable. If it is the case you should introduce binary variables same_ij that specify if two tasks execute on the same machine. You create master search that decides about relative placement of tasks. Depending on the answer to my intial question you may be always able to extend master solution to a final solution that actually assigns tasks to specific machines. Even if tasks are fixed to a specific containers this constraint will immediately propagate when same_ij are being assigned values.
Also, for some pairs of tasks that communication costs are low you could ignore the corresponding same_ij variable from the optimization search and only fix it later when you find an optimal solution for partial problem (only significant pairs). You loose proof of optimality but you may not be far away from global optimal solution.
Hope that helps.
Radek
Hi,
It really helped. I will tell about my contraints detail when I totally finish it.
Thanks a lot..
Zafer.