Optimization Problem Solvers

• Integer Programming
• CPLEX [1]
• GLPK [2]
• Decentralized POMDP
• Multi-Agent Decision Process (MADP) Toolbox [3]

For more information about optimization problems, refer to [4].

References

[1] CPLEX: IBM ILOG Optimizer, July 2009, Available: http://tiny.cc/CPLEX.

[2] GLPK: GNU Linear Programming Kit, June. 2012, http://tiny.cc/GLPK.

[3] F. A. Oliehoek, M. T. J. Spaan, and P. Robbel, “MultiAgent Decision Process (MADP) Toolbox 0.3,” 2014.

[4] Practical Optimization: A Gentle Introduction, http://www.sce.carleton.ca/faculty/chinneck/po.html

Finding the optimal values for discrete parameters

One way, used in [1], is use this heuristic: Solve the problem in continuous space. Conduct a bi-dimensional search for the nearest valid (discrete) values. If there were N parameters, there would be at most 2^N possible options. Apply the same utility function or a different one to find the best option. 

Another way, used in [2], is a branch and bound algorithm [3] that uses heuristic evaluation, which allows to optimise over a discrete data set in linear time. In [2], the utilized two versions (Promote and Boost), but the results were similar. 


References
[1] Mu, Mu, et al. "User-level fairness delivered: network resource allocation for adaptive video streaming." 2015 IEEE 23rd International Symposium on Quality of Service (IWQoS). IEEE, 2015.
[2] Georgopoulos, Panagiotis, et al. "Towards network-wide QoE fairness using openflow-assisted adaptive video streaming." Proceedings of the 2013 ACM SIGCOMM workshop on Future human-centric multimedia networking. ACM, 2013.
[3] R. J. Dakin. A Tree-search Algorithm for Mixed Integer Programming Problems. Comput. J., 8(3):250{255, 1965.