search

fslaborg / flips

Fsharp LInear Programming System
https://flipslibrary.com/#/
MIT License
251 stars 32 forks source link

Question - Division or multiplication between decisions in linear expression #186

Closed wenLiangcan closed 2 years ago

wenLiangcan commented 2 years ago

I want to express the relationship of two decisions by division, but there's no such operator in LinearExpression. It is not possible to declare a constraint on the result of the multiplication of two decisions neither. Is there any way to achieve this or any plan to adding support?

matthewcrews commented 2 years ago

It is actually not possible since Flips is intended for Linear Programming and Mixed-Integer Programming. What you are describing in Nonlinear Programming.

It is often possible to formulate problems without the product of two decisions. Could you describe what you are trying to do? I'll see if I can help.

wenLiangcan commented 2 years ago

Thanks @matthewcrews , i'm trying to solve an excercise from the book The Art of Multiprocessor Programming as a practice to learn the usage of Flips.

The excercise describes a variable, the number of cache misses, witch is depends on another variable N, the number of CPU cores

CacheMisses = N / (N + 10)

The details of the problem as below:

A financial risk management program is sped up by making 85% of the application concurrent, while 15% remains sequential. However, it turns out that during a concurrent execution the number of cache misses grows in a way dependent on N, the number of cores used. The dependency is CacheMisses = N / (N + 10) . Profiling the program reveals that 20% of the operations performed are memory accesses for both the sequential and parallel parts. The cost of other operations, including cache accesses, is 1 unit, and accessing memory has a cost of 3N + 11 units for the parallel part and a cost of 14 for the sequential part. Compute the optimal number of processors on which the program should run.

I do not have professional knowledge on linear programming, maybe this problem isn't suited to solve in this way?

I also found this link, says Gurobi suppots constraint on product of variables. As my understanding, Gurobi is an optimization solver for linear programming problem right?

TysonMN commented 2 years ago

CacheMisses = 1 + 0.1 * N

wenLiangcan commented 2 years ago

@TysonMN Thank you so much

wenLiangcan commented 2 years ago

By rethinking, i found out that 1 + 0.1 * N equals to (N + 10) / 10 but not N / (N + 10) 😂. The dependency of cache misses is actually not linear.

TysonMN commented 2 years ago

Oh, yeah. Sorry for my misdirection.