5 ms·
BMW's 3,854-Variable Problem Solved in Six Minutes with Quantum Computing
- pkaye 4y agoI was thinking the problem they would solve was the optimal price for a BMW seat heater subscription.
- deleted 4y ago[deleted]
- whatever1 4y agoTo 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.
- moralestapia 4y agoI'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?
- freemint 4y agoGurobi, 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.
- freemint 4y ago> 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.mps.html 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.
- whatever1 4y agoI 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.
- whatever1 4y agoBtw out of curiosity I submited your mps file to the NEOS server https://neos-server.org/neos/ https://neos-server.org/neos/ and solved it with FICO XPRESS to global optimality.
- freemint 4y agoI had Gurobi struggled with it for over a week. Do you have job id & password or the solution file?
- raxxorraxor 4y agoI 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.
- kxyvr 4y agoCandidly, 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?documentTableId=7025713833818081544&userAction=Browse&templateName=&documentId=740c3d47812c470b208a495d85f18206 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/00/f_4d24e50eb1e74b5219eed953673dbcb4/210713_UC4_Sensors.pdf?v=1658096993 https://crowd-innovation.bmwgroup.com/apps/IMT/UploadedFiles... and their data set can be found here: https://crowd-innovation.bmwgroup.com/apps/IMT/UploadedFiles/00/f_424a1e36e809bcf39d5d5f6291b33182/Data-Sensor_position.zip?v=1658096993 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.
- raxxorraxor 4y agoThat 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).