?
FPT Algorithms for the Shortest Lattice Vector and Integer Linear Programming Problems
P. 19-35.
In this paper, we present FPT algorithms for special cases of the shortest vector problem (SVP) and the integer linear programming problem (ILP), when matrices included in the problems’ formulations are near square. The main parameter is the maximal absolute value of rank minors of matrices included in the problem formulation. Additionally, we present FPT algorithms with respect to the same main parameter for the problems, when the matrices have no singular rank sub-matrices.
In book
Valery A. Kalyagin, Panos M. Pardalos, Oleg Prokopyev, Irina Utkina Vol. 247. , Springer, 2018
D. V. Gribanov, D.S. Malyshev, P. M. Pardalos et al., Journal of Combinatorial Optimization 2018 Vol. 35 No. 4 P. 1128-1146
In this paper, we present fixed-parameter tractable algorithms for special cases of the shortest lattice vector, integer linear programming, and simplex width computation problems, when matrices included in the problems’ formulations are near square. The parameter is the maximum absolute value of the rank minors in the corresponding matrices. Additionally, we present fixed-parameter tractable algorithms ...
Added: February 19, 2018
Veselov S. I., Gribanov D., Malyshev D., Moscow University Computational Mathematics and Cybernetics 2019 Vol. 43 No. 1 P. 1-11
The problem of computing the width of simplices generated by the convex hull of their integer vertices is considered. An FPT algorithm, in which the parameter is the maximum absolute value of the rank minors of the matrix consisting from the simplex vertices, is presented. ...
Added: April 22, 2019
Gribanov D., , in : Mathematical Optimization Theory and Operations Research: 20th International Conference, MOTOR 2021, Irkutsk, Russia, July 5–10, 2021, Proceedings. : Cham : Springer, 2021. P. 79-95.
Added: October 29, 2021
Gribanov D., Chirkov A. Y., Optimization Letters 2016 Vol. 10 No. 6 P. 1179-1189
In this paper, we will show that the width of simplices defined by systems of linear inequalities can be computed in polynomial time if some minors of their constraint matrices are bounded. Additionally, we present some quasi-polynomial-time and polynomial-time algorithms to solve the integer linear optimization problem defined on simplices minus all their integer vertices ...
Added: September 12, 2016
Gribanov D., Malyshev D., Журнал Средневолжского математического общества 2016 Т. 18 № 3 С. 19-31
Мы рассматриваем естественные постановки задач о независимом множестве, о вершинном и о реберном доминирующем множестве как задач целочисленного линейного программирования и доказываем полиномиальную разрешимость этих задач для классов графов, имеющих ограниченные по абсолютному значению миноры (расширенных) матриц ограничений. ...
Added: October 20, 2016
Alexander Lazarev, Sologub A., , in : Optimization and applications (OPTIMA-2014). : M. : -, 2014. P. 127-128.
We consider the problem of trainings planning on ISS. Shown that the problem is a combination of a k Partition Problem and an Assignment Problem. NP-compleeteness is proofed. A heuristic and an exact algorithms are proposed. ...
Added: October 16, 2014
Aldunin D. A., Fedin G., Информационные технологии 2019 Т. 25 № 4 С. 250-256
Distant learning has weaknesses related to missing tutor and kind of autodidacticism of the process, which may cause learner’s frustration in uncertain situations and force him or her to drop the learning course. Inasmuch as it is very important to help learner to select a set of needed courses, the article deals with the task ...
Added: September 18, 2019
Bronnikov S., Lazarev A. A., Petrov A. S. et al., , in : VI International Conference on Optimization Methods and Applications "Optimization and applications" (OPTIMA-2015), Petrovac, Montenegro, September 2015. : M. : -, 2015. P. 196-197.
We consider the problem of planning the ISS cosmonaut training with different objectives. A pre-defined set of minimum qualification levels should be distributed between the crew members with minimum training time differences, training expenses or a maximum of the training level with a limitation of the budget. First, a description of the cosmonaut training process ...
Added: October 20, 2015
Omrani H., Oveysi Z., Emrouznejad A. et al., Journal of the Operational Research Society 2022
Conventional DEA performs like a “black box” and provides no information about sub-processes. In some cases, such as banks, providing services is made up of interactive and interdependent processes. Also, in real world applications, inputs could be shared among these sub-processes. Moreover, due to the characteristics of some variables, such as number of employees, only integer values could be assigned to ...
Added: September 3, 2022
Gribanov D., Springer Proceedings in Mathematics & Statistics 2014 No. 104 P. 37-43
We consider the class of polytopes with the property that minors of the constraint matrix are bounded. It is shown that the problem of searching an integer point in the polytope is polynomially solvable if the polytope has a sufficiently large width. It is important that the width estimation depends on the maximum absolute value ...
Added: October 23, 2014
Omrani H., Oveysi Z., Emrouznejad A. et al., Journal of the Operational Research Society 2023 Vol. 74 No. 4 P. 1150-1165
Conventional DEA performs like a “black box” and provides no information about sub-processes. In some cases, such as banks, providing services is made up of interactive and interdependent processes. Also, in real world applications, inputs could be shared among these sub-processes. Moreover, due to the characteristics of some variables, such as number of employees, only integer values could be assigned to ...
Added: September 3, 2022
Gribanov D., Veselov S. I., Optimization Letters 2016 Vol. 10 No. 6 P. 1169-1177
Let A be an \((m \times n)\) integral matrix, and let \(P=\{ x :A x \le b\}\) be an n-dimensional polytope. The width of P is defined as \( w(P)=min\{ x\in \mathbb {Z}^n{\setminus }\{0\} :max_{x \in P} x^\top u - min_{x \in P} x^\top v \}\). Let \(\varDelta (A)\) and \(\delta (A)\) denote the greatest ...
Added: October 12, 2015
Gribanov D., Zolotykh N., Optimization Letters 2022 Vol. 16 No. 7 P. 1991-2018
Let a polyhedron $P$ be defined by one of the following ways:
\begin{enumerate}
\item[(i)] $P = \{x \in \RR^n \colon A x \leq b\}$, where $A \in \ZZ^{(n+k) \times n}$, $b \in \ZZ^{(n+k)}$ and $\rank A = n$,
\item[(ii)] $P = \{x \in \RR_+^n \colon A x = b\}$, where $A \in \ZZ^{k \times n}$, $b \in \ZZ^{k}$ ...
Added: October 29, 2021
Lazarev A. A., Мусатова Е. Г., Хуснуллин Н. Ф., , in : Труды IV Международной конференции "Методы оптимизации и программное обеспечение" (ОПТИМА-2013). : Монтенегро, Петровац : ВЦ РАН, 2013. P. 105.
The central question that motives this paper is the problem of making up a freight train and the routes on the railway. It is necessary from the set of orders available at the stations to determine time-scheduling and destination routing by railways in order to minimize the total completion time. In this paper it was ...
Added: October 21, 2014
Gribanov D., Malyshev D., Discrete Applied Mathematics 2017 Vol. 227 P. 13-20
We consider boolean linear programming formulations of the independent set, the vertex and the edge dominating set problems and prove their polynomial-time solvability for classes of graphs with (augmented) constraint matrices having bounded minors in the absolute value ...
Added: April 23, 2017
Malyshev D., Gribanov D., Discrete Optimization 2018 Vol. 29 P. 103-110
We consider boolean linear programming formulations of the vertex and edge dominating set problems and prove their polynomial-time solvability for classes of graphs with constraint matrices having bounded minors in the absolute value. ...
Added: April 8, 2018
Pardalos P. M., Aydogan E. K., Karaoglan I., Applied Soft Computing Journal 2012 Vol. 12 No. 2 P. 800-806
The aim of this work is to propose a hybrid heuristic approach (called hGA) based on genetic algorithm (GA) and integer-programming formulation (IPF) to solve high dimensional classification problems in linguistic fuzzy rule-based classification systems. In this algorithm, each chromosome represents a rule for specified class, GA is used for producing several rules for each ...
Added: February 4, 2013
Belenky A., Egorova L. G., , in : Optimization and Its Applications in Control and Data Sciences: In Honor of Boris T. Polyak’s 80th Birthday (Springer Optimization and Its Applications). Book 115.: Springer, 2016. P. 51-117.
The paper proposes two new approaches to designing efficient mathematical tools for quantitatively analyzing decision-making processes that small and medium price-taking traders undergo in forming and managing their portfolios of financial instruments traded in a stock exchange. Two mathematical models underlying these approaches are considered. If the trader can treat price changes for each financial ...
Added: October 10, 2016