BMW's 3,854-Variable Problem Solved in Six Minutes with Quantum Computing | Hacker News Reader

BMW's 3,854-Variable Problem Solved in Six Minutes with Quantum Computing

tomshardware.com

16 pointsbobjordan11 comments

I was thinking the problem they would solve was the optimal price for a BMW seat heater subscription.

To give you some perspective on how early we are on quantum computing:

4000 integers and a couple hundreds of constraints we can can typically solve today to proven global optimality within seconds.

We could even solve such problems in the early 90’s.

I'm a bit new to this (not QC but linear programming/optimization in general), could you share some libraries or code that is considered state of the art on this?

Gurobi, CPLEX, COPT, Octeract are commercial software solving such problems. HiGHS, CBC and GLPK are open source solvers.

The commercial ones are beating non commercial ones usually. The open source ones are sorted by fastest first.

If you are interested in writing your own solver. I recommend you join the currently running JuliaCon and talk with people in the JuMP channel.

> 4000 integers and a couple hundreds of constraints we can can typically solve today to proven global optimality within seconds

Oh really? I got a problem with 1064 binary variables and 8000ish constraints. Surely you can solve it for me. I do just require a solution not even an optimal solution.

Surely you can solve it for me. https://www.file-upload.net/download-14976197/strassic-7-2.m...

It is not that simple, it really depends on the problem and the formulation.

I said typically. These are NP problems you can always find edge cases that are impossible to solve.

For these edge cases we can always reformulate the problem, aka use different definition of variables and constraints that can better inform the search.

We are talking about real world applications, not toying with pathogenic benchmark toy examples.

Btw out of curiosity I submited your mps file to the NEOS server https://neos-server.org/neos/ and solved it with FICO XPRESS to global optimality.

I had Gurobi struggled with it for over a week. Do you have job id & password or the solution file?

I would really like to see the model of the problem for this kind of sensor placing. I am sure there are complex problems but my model would basically be two crates of beer between each sensor.

Candidly, it took way too long to find their model. Information about each of the challenges can be found here:

https://crowd-innovation.bmwgroup.com/servlet/hype/IMT?docum...

A pdf of the formulation can be found here:

https://crowd-innovation.bmwgroup.com/apps/IMT/UploadedFiles...

and their data set can be found here:

https://crowd-innovation.bmwgroup.com/apps/IMT/UploadedFiles...

If anyone from BMW is reading this, I will contend that you will get more interest if the sites that host your information are search indexable and if the news briefs published about the contest and conference actually refer back to the conference/contest website.

That is really interesting, it is sometimes difficult to imagine the questions they ask themselves. If they include specific sensors with different properties I could see the complexity quickly increasing.

side note: The TLS cert for their site is invalid since today (was valid until 22-07-31).

Reply on news.ycombinator.com