The problem of scheduling a freight train as a problem of integer programming
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 suggested formulation of this problem by applying integer programming.
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.
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 is given. The model are considered for the volume planning problem. The objective of the model is to minimize the differences between the total time of the preparation of all crew members. Then two models are considered for the timetabling planning problem. For the volume planning problem, two algorithms are presented. The first one is aheuristic with a complexity of O(n) operations. The second one consists of a heuristic and exact parts, and it is based on the npartition problem approach.
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 instrument of her interest as those of a random variable with a known (for instance, a uniform) probability distribution, one of these models allows the trader to formulate the problem of finding an optimal composition of her portfolio as an integer programming problem. The other model is suggested to use when the trader does not possess any particular information on the probability distribution of the above-mentioned random variable for financial instruments of her interest while being capable of estimating the areas to which the prices of groups of financial instruments (being components of finite-dimensional vectors for each group) are likely to belong. When each such area is a convex polyhedron described by a finite set of compatible linear equations and inequalities of a balance kind, the use of this model allows one to view the trader’s decision on her portfolio composition as that of a player in an antagonistic game on sets of disjoint player strategies. The payoff function of this game is a sum of a linear and a bilinear function of two vector arguments, and the trader’s guaranteed financial result in playing against the stock exchange equals the exact value of the maximin of this function. This value, along with the vectors at which it is attained, can be found by solving a mixed programming problem. Finding an upper bound for this maximin value (and the vectors at which this upper bound is attained) is reducible to finding saddle points in an auxiliary antagonistic game with the same payoff function on convex polyhedra of disjoint player strategies. These saddle points can be calculated by solving linear programming problems forming a dual pair.
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 assuming that some minors of the constraint matrices of the simplices are bounded.