COMBINATORIAL OPTIMIZATION MODELS AND SYSTEM CONFIGURATIONS

http://www.mslevin.iitp.ru/

email: mslevin@acm.org

Combinatorial optimizaiton models. Knapsack problem. Algorithmic complexity. Types of algorithms.

Multicriteria decision making. Multicriteria ranking / sorting problem.

Multiple choice problem.

System configuration design: (1) selection of system components, (2) selection of system components with taking into account compatibility of the selected components, (3) building of hierarchical structures (representative problem, path in multi-partite graph, clique, etc.).

Clustering. Assignment problem (location/allocation problems).

Clique, clique in multipartite graph. Combinatorial synthesis of system configuration.

Composite combinatorial schemes for system configuration. Connection of users and access points in communication systems.

Graph coloring problems.

Building of hierarchies (including hotlink assignment problem).

Aggregation of hierarchical structures/configurations.

Combinatorial synthesis with interval multiset estimates.

Restructuring in combinatorial optimization problems (reoptimizaiton).

System reconfiguration. Examples of applied systems.

Satisfiability problem (SAT problem).

Composite problems: timetabling problems (scheduling in universities, sport, hospitals).

Discussion of student works.

In the course, models for system configuration are studied.

For each combinatorial model / family of combninatorial models, the following is examined:

(1) simplified versions of the model(s) (polynomial solvable),

(2) complex models (NP-hard),

(3) approximation schemes / heuristics,

(4) examples for configuration of real-world systems.

The course is targeted to the following:

(1) knowledge transfer to student (traditional educational approach),

(2) joint generation of knowledge (advanced educational approach).

(report as a preliminary material for publication and conference presentation):

(e.g., configuration for hierarchical network for group of bank users).

Some prepared programs (in MATLAB) can be used:

(a) selection of Pareto-efficient points,

(b) outrankling technique (Electre),

(c) greedy algorithm for knapsack problem,

(d) greedy algorithm for multiple choice problem,

(e) agglomerative algorithm for hierarchical clustering.

1. Garey M.R., Johnson D.S., Computers and Intractability. The Guide to the Theory of NP-Completeness. W.H. Freeman and Company, San Francisco, 1979.

1. Simon H.A., Newell A., Heuristic problem solving: the next advance in operations research. Operations Research, 6(1), 1-10, 1958.

2. Zoponidis N., Doumpos M., Multicriteria classification and sorting mehtods: A literature review. EJOR, 138(2), 229-246, 2002.

http://arxiv.org/abs/1211.2245 [math.OC]

1. Garey M.R., Johnson D.S., Computers and Intractability. The Guide to the Theory of NP-Completeness. W.H. Freeman and Company, San Francisco, 1979.

2. Kelleler H., Pferschy U., Pisinger D., Knapsack Problems, Springer, 2004.

3. Martello S., Toth P., Knapsack Problems: Algorithms and Computer Implementation. Wiley, 1990.

(accessible via Internet)

Autom. and Remote Control, 70(3), 519-561, 2009.

Version in Rusian:

"Information Processes", 8(4), 256-300 , 2008.

1. Jain A.K., Murty M.N., Flynn P.J., Data clustering: a review. ACM Comput. Surv., 31(3), 264-323, 1992.

2. Mirkin B., Muchnik I., Combinatorial optimization in clustering. In: D.-Z. Du, P. Pardalos, (Eds.), Kluwer, 261-329, 1998.

In: V. Diekert, M. Volkov, A. Voronkov, (Eds.), CSR 2007, LNCS 4649, Springer,

205-215, 2007.

4. Garey M.R., Johnson D.S., Computers and Intractability. The Guide to the Theory of NP-Completeness. W.H. Freeman and Company, San Francisco, 1979.

Electronic preprint. 20 pp., Jan. 9, 2012.

http://arxiv.org/abs/1201.1712 [cs.SE]

Electronic preprint. 13 pp., Aug. 31, 2011.

http://arxiv.org/abs/1108.6223 [cs.SE]

http://arxiv.org/abs/1203.0648 [cs.SE]

1. Levin M.Sh., Four-layer framework for combinatorial optimization problems domain.

Advances in Engineering Software, 42(12), 1089-1098, 2011.

2. Levin M.Sh., Combinatorial scheme for design of marketing strategy.

Business Informatics, Issue 2, 42-51, 2009 (in Russian).

IEEE Trans. SMC - Part A, 41(2), 370-374, 2011.

1. Pachos V.Th., Polynomial approximation and graph coloring. Computing, 70(1), 41-86, 2003.

2. Johnson D.S., Trick M.A. (Eds.), Cliques, Coloring, and Satisfiability: Second DIMACS Implementation Challendge, Providence, RI, AMS, 1996.

3. Garey M.R., Johnson D.S., Computers and Intractability. The Guide to the Theory of NP-Completeness. W.H. Freeman and Company, San Francisco, 1979.

In: V. Diekert, M. Volkov, A. Voronkov, (Eds.), CSR 2007, LNCS 4649, Springer,

205-215, 2007.

"Information Processes", 11(4), 466-475, 2011 (in Russian).

http://arxiv.org/abs/1212.1735 [math.OC]

4. Bose P., Kranakis E., Kriznc D., Martin M., Czyzowicz M.V., Pelc A., Gasieniec L., Strategies for hotlink assignment. LNCS 1969, Springer, 23-34, 2000.

5. Fuhrmann S., Krumke S., Multiple hotlink assignment. LNCS 2204, Springer, 189-200, 2001.

Electronic preprint. 72 pp., Nov. 29, 2011.

http://arxiv.org/abs/1111.6983 [cs.SE]

http://arxiv.org/abs/1205.2046 [cs.SY]

Electronic Scientific Journal "Information Processes", 12(2), 141-154, 2012 (in Russian)

http://arxiv.org/abs/1207.6051 [cs.SY]

http://arxiv.org/abs/1102.1745 [cs.DS]

2. Bockenhauer H.-J., Hromkovic J., Momke T., Widmayer P., On the hardness of reoptimization. LNCS 4910, Springer, 50-65, 2008.

IEEE Region 8 Int. Conf. Sibircon 2010, vol. 1, 204-208, 2010.

In: K.G. Mehrotra et al. (Eds.), Proc. of 24th Int. Conf. IEA/AIE 2011, LNCS 6704, Part II, Springer, 459-468, 2011.

1. Garey M.R., Johnson D.S., Computers and Intractability. The Guide to the Theory of NP-Completeness. W.H. Freeman and Company, San Francisco, 1979.

2. Johnson D.S., Trick M.A. (Eds.), Cliques, Coloring, and Satisfiability: Second DIMACS Implementation Challendge, Providence, RI, AMS, 1996.

1. de Werra D., An introduction to timetabling. EJOR, 19(2), 151-162, 1985.

2. Nemhauser G.I., Trick M.A., Scheduling a major college basketball conference. Operations Research, 46(1), 1-8, 1998.

3. Schaerf A., A survey of automated timetabling. Artif. Intell. Review, 13(2), 87-127, 1999.

1. Levin M.Sh., Safonov A.V., Design and redesign for equipment configuration in communication network.

"Information technologies and computer systems", issue 4, 63-73, 2006 (in Russian).

2. Levin M.Sh., Safonov A.V., Improvement of regional telecommunications networks.

J. of Communications Technology and Electronics, 56(6), 770-778, 2011.

Version in Russian:

"Information Processes", 10(3),212-223, 2010 (in Russian).

2nd Int. Congress on Ultra Modern Telecommunications and Control Systems and Workshops

ICUMT-2010, Moscow, 109-114, 2010.

1. Levin M.Sh., Petukhov M.V., Connection of users with a telecommunications network: multicriteria assignment problem.

J. of Communications Technology and Electronics, 55(12), 1532-1541, 2010.

Version in Russian::

(multicriteria assignment problem). "Information Processes", 9(4), 332-342, 2009 (in Russian).

Proc. of 23rd Int. Conf. IEA/AIE 2010, "Trends in Applied Intelligent Systems",

LNCS 6097, part II, Springer, pp. 277-287, 2010.

Automation and Remote Control, 68(9), 1654-1661, 2007.

Version in Russian:

"Information Processes", 7(2), 191-198, 2007 (in Russian).

"Information Processes" 7(2), 183-190, 2007

3. Levin M.Sh., Sharov S.Yu., Hierarchical morphological design of Web-hosting system.

Int. Journal of Integrated Design & Process Science, 13(1), 1-14, 2009.

7th IEEE Int. Conf. on Industrial Informatics INDIN 2009, Cardiff, UK, pp. 101-105, 2009.

http://arxiv.org/abs/1203.2031 [cs.SE]

"Information Processes", 9(2), 83-92, 2009 (in Russian).

Composite combinatorial scheme of test planning (example for microprocessor systems)

IEEE Region 8 Int. Conf. "Sibircon-2008", Novosibirsk, 291-295, 2008.

Electronic preprint. http://arxiv.org/abs/1102.2524 [cs.DS], 11 pp., Febr. 12, 2011

2. Levin M.Sh., Zamkovoy A.A., Multicriteria Steiner tree with the cost of Steiner vertices.

J. of Communications Technology and Electronics,

56(12), 1527-1542, 2011.

Version in Russian:

"Information Processes", 11(1), 140-160, 2011 (in Russian).