Timeline for Python integer optimization with PuLP involving polynomials that I think can be faster
Current License: CC BY-SA 4.0
17 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 7, 2023 at 23:29 | answer | added | Reinderien | timeline score: 3 | |
| Dec 5, 2023 at 16:43 | history | edited | Matt Samuel | CC BY-SA 4.0 |
added 8 characters in body
|
| Dec 5, 2023 at 13:01 | history | edited | Matt Samuel | CC BY-SA 4.0 |
edited title
|
| Dec 4, 2023 at 11:46 | history | edited | Matt Samuel | CC BY-SA 4.0 |
edited body
|
| Dec 4, 2023 at 0:40 | history | edited | Matt Samuel | CC BY-SA 4.0 |
added 1224 characters in body
|
| Dec 3, 2023 at 23:23 | history | edited | Matt Samuel | CC BY-SA 4.0 |
added 151 characters in body
|
| Dec 3, 2023 at 23:18 | comment | added | Reinderien | Let us continue this discussion in chat. | |
| Dec 3, 2023 at 22:51 | comment | added | Matt Samuel | @Reinderien The reason it doesn't do that is because I don't know how to do that. That would be OK. The first and foremost goal was initially to simply verify positivity. It's about these particular polynomials I have a conjecture about being positive in this way. This was the way I figured out how to verify positivity, but I implemented it to actually display the result positively so it could be examined by a human. Your example would be fine. | |
| Dec 3, 2023 at 22:47 | comment | added | Reinderien |
Must each sub expression have two terms? Why not write (y_5 - z_1)*(y_1-z_2)+(y_5-z_1)*(y_3-z_5) as (y_5 - z_1)*(y_1-z_2+y_3-z_5)?
|
|
| Dec 3, 2023 at 22:39 | comment | added | Matt Samuel |
@Reinderien So we're not trying to factorize here per se. We want any expression in terms of products of terms like (y_5 - z_1) with nonnegative coefficients. So (y_5 - z_1)*(y_1-z_2)+(y_5-z_1)*(y_3-z_5) would be good, and the reason this is so hard is because you could also express the same polynomial as (y_5 - z_1)*(y_1-z_5)+(y_5-z_1)*(y_3-z_2). We're not looking for a unique expression or factorized, just positive in terms of terms like that. The assumption is that this is always possible (if it's not in a certain case, we don't care about that case).
|
|
| Dec 3, 2023 at 22:36 | comment | added | Reinderien | What defines success here? Must the expression be as factored as possible, even if that means nesting depth greater than one? | |
| Dec 3, 2023 at 22:32 | comment | added | Matt Samuel |
@Reinderien So I use symegine's function expand which will fully expand the result in terms of monomials with integer coefficients. The variables don't have anything substituted, these are abstract polynomials. It arbitrarily assigned indexes to the monomials and populates "monom_to_vec" which is a lookup translating the monomial to the index. Then, given an expanded polynomial, poly_to_vec will fill in those coordinates which are the integer coefficients of the monomials in a numpy array. So the value at the index in the array is the coefficient of the monomial. Is this clearer?
|
|
| Dec 3, 2023 at 22:25 | comment | added | Reinderien | Can you explain more about how you're linearizing all of those products? Are any of the variables binary? Or are the coefficients to those products constants and not variables? | |
| Dec 3, 2023 at 22:06 | history | edited | Matt Samuel | CC BY-SA 4.0 |
deleted 2517 characters in body
|
| Dec 3, 2023 at 21:54 | history | edited | Matt Samuel | CC BY-SA 4.0 |
added 4680 characters in body
|
| Dec 3, 2023 at 21:17 | history | edited | Matt Samuel | CC BY-SA 4.0 |
deleted 29 characters in body
|
| Dec 3, 2023 at 21:10 | history | asked | Matt Samuel | CC BY-SA 4.0 |