Concept: Distributed Constraint Satisfaction

prubypruby Member Posts: 8
edited September 2015 in Smart Contracts and Dapps
Hi guys,

Just floating a concept for a DApp I'd consider developing, seeing if anyone has any ideas or improvements before I do so. I was considering some applications of Ethereum which typically involve mixed integer linear programming (MIP). . Many interesting optimisation and constraint satisfaction problems can be modelled as mixed integer linear programs including complicated multi-party auctions, decision making in many business situations, rostering of people in to a timetable, and so on.

In particular, I was thinking about how you could implement the equivalent of the authority scheduling an electricity network on Ethereum. This often involves complicated constraints - for example, here in New Zealand, we have two major islands. One island generates most of the electricity, and most of it is used at the very far end of the other. The capacity of the various bits of the network in the middle is the major determiner of price along the way.

Integer optimisation itself is _way_ too compute intensive to do within a DApp, as it typically involves large clusters of machines to do at scale. On the other hand, verifying a solution is relatively cheap and could be done practically.

This DApp would take a message with a linear optimisation problem and a time frame it must be solved in. This would be in the form of a unique identifier, a list of variables (each specified as linear or integer variables with a minimum and maximum), a goal as a linear function of those variables, and a set of linear constraints on those variables. Optionally, a sum could also be transferred to the script to act as a reward for the best solution.

Any party would then be free to submit solutions to this problem, which would be verified against the original constraints. Any solution not satisfying the constraints or not improving the goal would be rejected. Any solution improving the goal would be accepted and become the current solution, with the address source of that logged. Once the time frame of the problem has elapsed, no further solutions would be accepted and the reward, if any, would be paid out to the submitter of the best solution.

With this:
* We can solve a wide range of optimisation problems in public, with the results being fair and verifiable. If the current solutions aren't good enough, anyone can contribute a better solution within the time frame.
* The public could solve useful computer problems for rewards in ether.

Any thoughts from the crowd brain?


  • prubypruby Member Posts: 8
    OK, one specific question for the community - are there any hard constraints on the size of parameters to function calls? MIP problems are often quite large, and if there are hard limits could have to be composed in pieces.
Sign In or Register to comment.