Can we solve a Large integer programming problem having 100 million variable for optimisation

• 

  Andrew M  (Report)

  October 09, 2018 14:34

  I would be surprised if you could do that directly. I think you'll run into several challenges along the way:

  • If a variable corresponds to a quantum bit, then you'd be limited to the number of bits on the system (~2000).
  • When composing your model as an Ising problem, if your quadratic terms don't correspond to a Chimera graph, you will need to have chains of physical qubits that encode your logical qubits. This will further limit your number of bits.
  • If your problem is an optimization that is not quadratic (something like "a and b and c must not all be true") you will need to incorporate auxiliary variables to encode it as a quadratic optimization.

  There are some things that might make some flavor of optimization possible:

  • Could you optimize on subsets of your variables? You might be able to sequentially select different subsets in some sort of hill climbing procedure.
  • Could you do traditional computing to determine with high probability that certain bits must be the same? This could probabilistically decompose your problem to one that could be used to find a "good enough" solution.

  I'm looking at the opening of this compute resource to develop experience with technology that will be useful in the next few years, but suffers from some big limitation now. To that end, could you try out a related a toy problem to determine what's hard? From there, you might ask what might be come easy or possible with near-term advances in quantum annealer architecture?

  Good luck!

  -- Andrew Matteson

  1

  Comment actions Permalink
• 

  virendra p  (Report)

  October 11, 2018 04:59

  Hi Andrew,

  In problem solving capability using D-wave, there its mentioned that, it is able solve Airline scheduling problem.

  Can you please brief about which scheduling problem it solved using D-wave and size(variables and constraints) of problem and relevant details.

  Regards,

  Virendra

  0

  Comment actions Permalink
• 

  Andrew M  (Report)

  October 16, 2018 13:23

  Hi Virenda,

  I'm not part of D-wave staff. Maybe you can reach out to their support team?

  --Andrew

  0

  Comment actions Permalink
• 

  Igor S  (Report)

  October 18, 2018 20:53

  There was a presentation at ISC about it; unfortunately I cannot find the slides :(

   

  FYI:

  https://2018.isc-program.com/?page_id=10&id=inv_sp118&sess=sess172 

  1

  Comment actions Permalink

Please sign in to leave a comment.