Ask Your Question

Revision history [back]

How to solve a combined problem of IP, Boolean Satisfiability and Maximization?

I have a problem in mind that I want to solve, and after doing some research I believe it is a maximization problem that uses both Integer Programming and Boolean Satisfiability.

Now, it's easy enough for me to declare the variables, and assign them a range. But I simply don't know how to go on from there with SAGE. So I was hoping that if I explain a thought up example of what I need to do, someone could point me in the right direction.

So I have some sum equations with a lot of variables, and all of the variables are positive integers, including zero. For example, one such equation could be like this:

(A or B) + (C or D or E)=10

This means, that at LEAST one combination of the variables in those two groups must sum up to 10. It could for example be A+C, B+D, A+E, but A+B doesn't matter. And there could be more than one combination thereof that sums up to 10, that also doesn't matter, just whether there's at least one that does.

Now I combine the sum equations I have, into groups, which is where the Boolean part comes in. Any such group can either be true or false. True, if all the sum equations can be solved, i.e. at least one combination in the equation sums up to the desired number. False, if even one of the equations cannot be solved.

So one such group could consist of two equations: (A or B) + (C or D or E)=10 (A or D) + (B or E)=10

Because I have a lot of different variables, and a lot of equations, I doubt all the groups I will need to make, can all be solved, i.e. all are true. And that is where the Maximization problem comes in. The problem I actually need to solve, is to make as many as the aforementioned groups of equations True. Once I know this, and which groups and thus equations can be solved, I have my solution. And if there are more than one way to achieve the maximum number of solved groups, all those count and are of interest to me.

So this is where I'm at, with a problem I want to solve, and no idea on how to go about solving it with SAGE.

How to solve a combined problem of IP, Boolean Satisfiability and Maximization?

I have a problem in mind that I want to solve, and after doing some research I believe it is a maximization problem that uses both Integer Programming and Boolean Satisfiability.

Now, it's easy enough for me to declare the variables, and assign them a range. But I simply don't know how to go on from there with SAGE. Sage. So I was hoping that if I explain a thought up example of what I need to do, someone could point me in the right direction.

So I have some sum equations with a lot of variables, and all of the variables are positive integers, including zero. For example, one such equation could be like this:

(A or B) + (C or D or E)=10

This means, that at LEAST one combination of the variables in those two groups must sum up to 10. It could for example be A+C, B+D, A+E, but A+B doesn't matter. And there could be more than one combination thereof that sums up to 10, that also doesn't matter, just whether there's at least one that does.

Now I combine the sum equations I have, into groups, which is where the Boolean part comes in. Any such group can either be true or false. True, if all the sum equations can be solved, i.e. at least one combination in the equation sums up to the desired number. False, if even one of the equations cannot be solved.

So one such group could consist of two equations: (A or B) + (C or D or E)=10 (A or D) + (B or E)=10

Because I have a lot of different variables, and a lot of equations, I doubt all the groups I will need to make, can all be solved, i.e. all are true. And that is where the Maximization problem comes in. The problem I actually need to solve, is to make as many as the aforementioned groups of equations True. Once I know this, and which groups and thus equations can be solved, I have my solution. And if there are more than one way to achieve the maximum number of solved groups, all those count and are of interest to me.

So this is where I'm at, with a problem I want to solve, and no idea on how to go about solving it with SAGE.Sage.

How to solve a combined problem of IP, Boolean Satisfiability and Maximization?

I have a problem in mind that I want to solve, and after doing some research I believe it is a maximization problem that uses both Integer Programming and Boolean Satisfiability.

Now, it's easy enough for me to declare the variables, and assign them a range. But I simply don't know how to go on from there with Sage. So I was hoping that if I explain a thought up example of what I need to do, someone could point me in the right direction.

So I have some sum equations with a lot of variables, and all of the variables are positive integers, including zero. For example, one such equation could be like this:

(A or B) + (C or D or E)=10

This means, that at LEAST one combination of the variables in those two groups must sum up to 10. It could for example be A+C, B+D, A+E, but A+B doesn't matter. And there could be more than one combination thereof that sums up to 10, that also doesn't matter, just whether there's at least one that does.

Now I combine the sum equations I have, into groups, which is where the Boolean part comes in. Any such group can either be true or false. True, if all the sum equations can be solved, i.e. at least one combination in the equation sums up to the desired number. False, if even one of the equations cannot be solved.

So one such group could consist of two equations: (A or B) + (C or D or E)=10 E)=10

(A or D) + (B or E)=10

Because I have a lot of different variables, and a lot of equations, I doubt all the groups I will need to make, can all be solved, i.e. all are true. And that is where the Maximization problem comes in. The problem I actually need to solve, is to make as many as the aforementioned groups of equations True. Once I know this, and which groups and thus equations can be solved, I have my solution. And if there are more than one way to achieve the maximum number of solved groups, all those count and are of interest to me.

So this is where I'm at, with a problem I want to solve, and no idea on how to go about solving it with Sage.

How to solve a combined problem of IP, Boolean Satisfiability and Maximization?

I have a problem in mind that I want to solve, and after doing some research I believe it is a maximization problem that uses both Integer Programming and Boolean Satisfiability.

Now, it's easy enough for me to declare the variables, and assign them a range. But I simply don't know how to go on from there with Sage. So I was hoping that if I explain a thought up example of what I need to do, someone could point me in the right direction.

So I have some sum equations with a lot of variables, and all of the variables are positive integers, including zero. For example, one such equation could be like this:

(A or B) + (C or D or E)=10

This means, that at LEAST one combination of the variables in those two groups must sum up to 10. It could for example be A+C, B+D, A+E, but A+B doesn't matter. And there could be more than one combination thereof that sums up to 10, that also doesn't matter, just whether there's at least one that does.

Now I combine the sum equations I have, into groups, which is where the Boolean part comes in. Any such group can either be true or false. True, if all the sum equations can be solved, i.e. at least one combination in the equation sums up to the desired number. False, if even one of the equations cannot be solved.

So one such group could consist of two equations: equations:

(A or B) + (C or D or E)=10

(A or D) + (B or E)=10

Because I have a lot of different variables, and a lot of equations, I doubt all the groups I will need to make, can all be solved, i.e. all are true. And that is where the Maximization problem comes in. The problem I actually need to solve, is to make as many as the aforementioned groups of equations True. Once I know this, and which groups and thus equations can be solved, I have my solution. And if there are more than one way to achieve the maximum number of solved groups, all those count and are of interest to me.

So this is where I'm at, with a problem I want to solve, and no idea on how to go about solving it with Sage.