Discrete Optimization and Operations Research

Energy efficiency has become a crucial issue in Computer Science. New hardware and system-based approaches are explored for saving energy in portable battery-operated devices, personal computers, or large server farms. The main mechanisms that have been developed for saving energy are the ability of transitioning the device among multiple power states, and the use of dynamic voltage scaling (speed scaling).

Linear superiorization (abbreviated: LinSup) considers linear programming (LP) problems wherein the constraints as well as the objective function are linear. It allows to steer the iterates of a feasibility-seeking iterative process toward feasible points that have lower (not necessarily minimal) values of the objective function than points that would have been reached by the same feasiblity-seeking iterative process without superiorization. Using a feasibility-seeking iterative process that converges even if the linear feasible set is empty, LinSup generates an iterative sequence that converges to a point that minimizes a proximity function which measures the linear constraints violation. In addition, due to LinSup’s repeated objective function reduction steps such a point will most probably have a reduced objective function value. We present an exploratory experimental result that illustrates the behavior of LinSup on an infeasible LP problem.

In clustering problems one has to partition a given set of objects into some subsets (called clusters) taking into consideration only similarity of the objects. One of the most visual formalizations of clustering is the graph clustering, that is, grouping the vertices of a graph into clusters taking into consideration the edge structure of the graph whose vertices are objects and edges represent similarities between the objects.In this short survey, we consider the graph correlation clustering problems where the goal is to minimize the number of edges between clusters and the number of missing edges inside clusters. We present a number of results on graph correlation clustering including results on computational complexity and approximability of different variants of the problems, and performance guarantees of approximation algorithms for graph correlation clustering. Some results on approximability of weighted versions of graph correlation clustering are also presented.

This paper considers a network comprised of parallel routes with the Bureau of Public Road (BPR) latency function and suggests an optimal distribution method for incoming traffic flow. The authors analytically derive a system of equations defining the optimal distribution of the incoming flow with minimum social costs, as well as a corresponding system of equations for the Wardrop equilibrium in this network. In particular, the Wardrop equilibrium is applied to the competition model with rational consumers who use the carriers with minimal cost, where cost is equal to the price for service plus the waiting time for the service. Finally, the social costs under the equilibrium and under the optimal distribution are compared. It is shown that the price of anarchy can be infinitely large in the model with strategic pricing.

The understanding of how a networked system behaves and keeps its topological features when facing element failures is essential in several applications ranging from biological to social networks. In this context, one of the most discussed and important topics is the ability to distinguish similarities between networks. A probabilistic approach already showed useful in graph comparisons when representing the network structure as a set of probability distributions, and, together with the Jensen-Shannon divergence, allows to quantify dissimilarities between graphs. The goal of this article is to compare these methodologies for the analysis of network comparisons and robustness.

The exchange model with piecewise linear separable concave utility functions is considered. This consideration extends the author’s original approach to the equilibrium problem in a linear exchange model and its variations. The conceptual base of this approach is the scheme of polyhedral complementarity. It has no analogs and made it possible to obtain the finite algorithms for some variations of the exchange model. Especially simple algorithms arise for linear exchange model with fixed budgets (Fisher’s model). This is due to monotonicity property inherent in the models and potentiality of arising mappings. The algorithms can be considered as a procedure similar to the simplex-method of linear programming. It is natural to study applicability of the approach for more general models. The considered piecewise linear version of the model reduces to a special exchange model with upper bounds on variables and the modified conditions of the goods’ balances. For such a model the monotonicity property is violated. But it remains, if upper bounds are substituted by financial limits on purchases. This is the idea of proposed iterative algorithm for initial problem. It is a generalization of an analogue for linear exchange model.

In this paper, we demonstrate how scheduling problems with controllable processing times can be reformulated as maximization linear programming problems over a submodular polyhedron intersected with a box. We explain a decomposition algorithm for solving the latter problem and discuss its implications for the relevant problems of preemptive scheduling on a single machine and parallel machines.

A cycle cover of a graph is a set of cycles such that every vertex lies in exactly one cycle. We consider the following two cycle cover problems. Problem A: given a complete undirected graph $$G=(V,E)$$, edge costs $$c: E \rightarrow R_+$$ and positive integers $$s_1, \ldots , s_m$$, find a cycle cover $$C_1, C_2, \ldots , C_m$$ of minimum total cost subject to $$C_i$$ has length $$s_i$$ for each $$i=1,\ldots m$$. Problem B: given a complete undirected graph $$G=(V,E)$$, edge costs $$c: E \rightarrow R_+$$, special vertices (depots) $$w_1 \ldots , w_m \in V$$ and positive integers $$s_1, \ldots , s_m$$, find a cycle cover $$C_1, C_2, \ldots , C_m$$ of minimum total cost subject to $$C_i$$ has length $$s_i$$ and contains vertex $$w_i$$ for each $$i=1,\ldots m$$. Problem B is a version of vehicle routing problem with m vehicles and routings of given lengths. Both problems include the TSP as a special case and so do not admit constant-factor approximations unless P$$=$$NP. We consider the metric case. Goemans and Williamson established that a case of Problem A when all cycles have length k is approximable within a factor of 4. In this paper we present the following results. Problem B can be solved by a 4-approximation algorithm in $$O(n^2\log n)$$ time for $$m=2$$ ($$n=|V|$$). Problem A can be solved by a 4-approximation algorithm in $$O(n^3\log n)$$ time for $$m=2$$. Problem A can be solved by a 8-approximation algorithm in $$O(n^{m+1}\log n)$$ time for any $$m\ge 3$$.

Negatively answering a question posed by Mnich and Wiese (Math. Program. 154(1–2):533–562), we show that $$\hbox {P2}|\hbox {prec}, p_{j}{\in }\{1,2\}|C_{\max }$$, the problem of finding a non-preemptive minimum-makespan schedule for precedence-constrained jobs of lengths 1 and 2 on two parallel identical machines, is W[2]-hard parameterized by the width of the partial order giving the precedence constraints. To this end, we show that Shuffle Product, the problem of deciding whether a given word can be obtained by interleaving the letters of $$k$$ other given words, is W[2]-hard parameterized by $$k$$, thus additionally answering a question posed by Rizzi and Vialette (CSR 2013). Finally, refining a geometric algorithm due to Servakh (Diskretn. Anal. Issled. Oper. 7(1):75–82), we show that the more general Resource-Constrained Project Scheduling problem is fixed-parameter tractable parameterized by the partial order width combined with the maximum allowed difference between the earliest possible and factual starting time of a job.

We consider a routing problem with constraints. To solve this problem, we employ a variant of the dynamic programming method, where the significant part (that is, the part that matters in view of precedence constraints) of the Bellman function is calculated by means of an independent calculations scheme. We propose a parallel implementation of the algorithm for a supercomputer, where the construction of position space layers for the hypothetical processors is conducted with use of discrete dynamic systems’ apparatus.

We study the m-Peripatetic Salesman Problem on random inputs. In earlier papers we proposed a polynomial asymptotically optimal algorithm for the m-PSP with different weight functions on random inputs. The probabilistic analysis carried out for that algorithm is not suitable in the case of the m-PSP with identical weight functions.In this paper we present an approach which under certain conditions gives polynomial asymptotically optimal algorithms for the m-PSP on random inputs with identical weight functions and for the m-PSP with different weight functions, as well. We describe in detail the cases of uniform and shifted exponential distributions of random inputs.

We introduce a randomized approximation algorithm for NP-hard problem of finding a subset of m vectors chosen from n given vectors in multidimensional Euclidean space $$\mathbb {R}^k$$ such that the norm of the corresponding sum-vector is maximum. We derive the relation between algorithm’s time complexity, relative error and failure probability parameters. We show that the algorithm implements Polynomial-time Randomized Approximation Scheme (PRAS) for the general case of the problem. Choosing particular parameters of the algorithm one can obtain asymptotically exact algorithm with significantly lower time complexity compared to known exact algorithm. Another set of parameters provides polynomial-time 1 / 2-approximation algorithm for the problem. We also show that the algorithm is applicable for the related (minimization) clustering problem allowing to obtain better performance guarantees than existing algorithms.

We present a polynomial algorithm with guaranteed approximation ratio 5/6 for the metric maximization version of the m-PSP with identical weight functions. This result extends the well-known algorithm by Kostochka and Serdyukov for the metric TSP (1985) to the case of several Hamiltonian cycles and improves the approximation ratio of the algorithm by Gordeeva (2010) for the metric 2-PSP.

We consider the problem of partitioning a finite sequence of points in Euclidean space into a given number of clusters (subsequences) minimizing the sum of squared distances between cluster elements and the corresponding cluster centers. It is assumed that the center of one of the desired clusters is the origin, while the centers of the other clusters are unknown and determined as the mean values over clusters elements. Additionally, there are a few structural restrictions on the elements of clusters with unknown centers: (1) clusters form non-overlapping subsequences of the input sequence, (2) the difference between two consecutive indices is bounded from below and above by prescribed constants, and (3) the total number of elements in these clusters is given as an input. It is shown that the problem is strongly NP-hard. A 2-approximation algorithm which runs in polynomial time for a fixed number of clusters is proposed for this problem.

We consider the strongly NP-hard problem of partitioning a set of Euclidean points into two clusters so as to minimize the sum (over both clusters) of the weighted sum of the squared intracluster distances from the elements of the clusters to their centers. The weights of sums are the cardinalities of the clusters. The center of one of the clusters is given as input, while the center of the other cluster is unknown and determined as the geometric center (centroid), i.e. the average value over all points in the cluster. We analyze the variant of the problem with cardinality constraints. We present an approximation algorithm for the problem and prove that it is a fully polynomial-time approximation scheme when the space dimension is bounded by a constant.

Capacitated Vehicle Routing Problem (CVRP) is the well-known combinatorial optimization problem remaining NP-hard even in the Euclidean spaces of fixed dimension. Thirty years ago, in their celebrated paper, M. Haimovich and A. Rinnoy Kan proposed the first PTAS for the Planar Single Depot CVRP based on their Iterated Tour Partition heuristic. For decades, this result was extended by many authors to numerous useful modifications of the problem taking into account multiple depots, pick up and delivery options, time window restrictions, etc. But, to the best of our knowledge, almost none of these results go beyond the Euclidean plane. In this paper, we try to bridge this gap and propose an EPTAS for the Euclidean CVRP for any fixed dimension.

The problem of integer recognition is to determine whether the maximum of a linear objective function achieved at an integral vertex of a polytope. We consider integer recognition over polytope SATP and its LP relaxation $$SATP_{LP}$$. These polytopes are natural extensions of the well-known Boolean quadric polytope BQP and its rooted semimetric relaxation $$BQP_{LP}$$.Integer recognition over $$SATP_{LP}$$ is NP-complete, since various special instances of 3-SAT problem like NAE-3SAT and X3SAT are transformed to it. We describe polynomially solvable subproblems of integer recognition over $$SATP_{LP}$$ with constrained objective functions. Based on that, we solve some cases of edge constrained bipartite graph coloring.

We investigate the well-known NP-hard problem of finding an optimal communication subgraph in a given edge-weighted graph. This problem appears in different distributed wireless communication networks, e.g., in wireless sensor networks, when it is necessary to minimize transmission energy consumption. We propose new heuristic algorithms based on variable neighborhood search metaheuristic. Our results have been compared with the best known results, and the numerical experiment showed that, on a large number of instances, our algorithms outperform the previous ones, especially in a case of large dimensions.

One of the central questions of polyhedral combinatorics is the question of the algorithmic relationship between vertex and facet descriptions of convex polytopes. In the sense of combinatorial optimization the reason for the relevance of this issue is the possibility of application of convex analysis methods to the decision combinatorial problems [6, 10, 15]. In this paper we consider combinatorial polytopes sufficiently general form. A number of necessary conditions and sufficient conditions for support inequality of polytope to be facet inequality are obtained, an illustration of the use of the developed technology to the connected k-factors polytope are given. Also we discuss the use of facet inequalities in cutting plane algorithms.

We consider a fractional 0-1 programming problem arising in manufacturing. The problem consists in clustering of machines together with parts processed on these machines into manufacturing cells so that intra-cell processing of parts is maximized and inter-cell movement is minimized. This problem is called Cell Formation Problem (CFP) and it is an NP-hard optimization problem with Boolean variables and constraints and with a fractional objective function. Because of its high computational complexity there are a lot of heuristics developed for it. In this paper we suggest a branch and bound algorithm which provides exact solutions for the CFP with a variable number of cells and grouping efficacy objective function. This algorithm finds optimal solutions for 21 of the 35 popular benchmark instances from literature and for the remaining 14 instances it finds good solutions close to the best known.

We consider a coupled-task single machine scheduling problem with equal exact delays and makespan as the objective function. We design a 3-approximation algorithm for the general case of this problem. We also prove that the existence of a $$(1.25-\varepsilon )$$-approximation algorithm implies P = NP. The inapproximability result remains valid for the case when the processing times of the two operations of each job are equal. We prove that this case is approximable within a factor of 1.5.

The routing open shop problem is a generalization of scheduling open shop problem and metric TSP. The jobs are located at nodes of some transportation network while the machines travel on the network to execute the jobs in the open shop environment. The machines are initially located at the same node (the depot) and have to return to the depot after completing all the jobs. The goal is to construct a feasible schedule minimizing the makespan. The problem is known to be NP-hard even for the trivial case with two machines on a link.We discuss the generalization of that problem in which each machine has individual travel times between the nodes of the network. For this model with two machines on a tree we suggest a linear time algorithm for a case when the depot is not predefined and has to be chosen.

The two machine routing open shop being a generalization of the metric TSP and two machine open shop scheduling problem is considered. It is known to be NP-hard even for the simplest case when the transportation network consists of two nodes only. For that simplest case it is known that the optimal makespan for any instance belongs to interval $$[\bar{R},\frac{6}{5}\bar{R}]$$, there $$\bar{R}$$ is the standard lower bound. We generalize that classic result to the case of three-nodes transportation network and present a linear time $$\frac{6}{5}$$-approximation algorithm for that case.

Multiprocessor jobs require more than one processor at the same moment of time. We consider two basic variants of scheduling multiprocessor jobs with various regular criteria. In the first variant, for each job the number of required processors is given and fixed, and the job can be processed on any subset of parallel processors of this size. In the second variant, the subset of dedicated processors required by a job is given and fixed. A sequence dependent setup time is needed between different jobs. We formulate mixed integer linear programming models based on a continuous time representation for the NP-hard scheduling problems under consideration. Using these models, we identify new polynomially solvable cases with the number of jobs bounded above by a constant.

Parallel jobs require more than one processor at the same time. We study speed scaling scheduling of parallel jobs with preemption. We propose “almost-exact” algorithms for problems with rigid jobs and single mode two-processor jobs. Based on configuration linear programs, our algorithms obtain an $$OPT + \varepsilon $$ solution for any fixed $$\varepsilon > 0$$.

We consider a mathematical model belonging to the family of competitive location problems. In the model, there are two competing parties called Leader and Follower, which open their facilities with the goal to capture customers and maximize profit. In our model we assume that Follower is able to open own facilities as well as to close the Leader’s ones. The model can be written as a pessimistic bilevel integer programming problem. We show that the problem of Leader’s profit maximization can be represented as a problem of pseudo–Boolean function maximization. The number of variables the function depends on equals to the number of sites available for opening a facility. We suggest a method of calculation of an upper bound for the optimal value of the function based on strengthening of a bilevel model with valid inequalities and further relaxation of the model by removing the lower–level optimization problem.

In this paper we propose a Variable neighborhood descent based heuristic for the capacitated clustering problem and related handover minimization problem. The performance of the proposed approach is assessed on benchmark instances from the literature. The obtained results confirm that of our approach is highly competitive with the state-of-the-art methods, significantly outperforming all of them on the set of randomly-generated instances tested.

Two competitors, a Leader and a Follower, are sequentially creating their hub and spoke networks to attract customers in a market where prices have fixed markups. Each competitor wants to maximize his profit, rather than a market share. Demand is split according to the logit model. The goal is to find the optimal hub and spoke topology for the Leader. We represent this Stackelberg game as a nonlinear mixed-integer bi-level optimisation problem and show how to reformulate the Follower’s problem as a mixed-integer linear program. Exploiting this reformulation, we solve instances based on a synthetic data using the alternating heuristic as a solution approach. Computational results are thoroughly discussed, consequently providing some managerial insights.

This paper addresses the competitive base stations location problem with sharing. Two mobile operators, the leader and the follower, compete to attract customers from a given market of high-speed internet connection. The leader acts first by placing a number of base stations, anticipating that the follower will react to the decision by creating his own network. The Leader can share BS cites with the follower operator, receiving a rent payment from him. We propose new model of realistic clients behavior, when the choice of the operator is made upon the average quality of service. We provide a formulation of this problem as a nonlinear integer programming problem. We propose a fast tabu search heuristic for this problem and provide some computational results.

In this paper, we consider a competitive location problem in a form of Stackelberg game. Two parties open facilities with the goal to capture customers and maximize own profits. One of the parties, called Leader, opens facilities first. The set of customers is specified after Leader’s turn with random realization of one of possible scenarios. Leader’s goal is to maximize the profit guaranteed with given probability or reliability level provided that the second party, called Follower, acts rationally in each of the scenarios. We suggest an estimating problem to obtain an upper bound for Leader’s objective function and compare the performance of estimating problem reformulations experimentally.

In this paper, we consider a class of optimization problems with a strongly convex objective function and the feasible set given by an intersection of a simple convex set with a set given by a number of linear equality and inequality constraints. Quite a number of optimization problems in applications can be stated in this form, examples being entropy-linear programming, ridge regression, elastic net, regularized optimal transport, etc. We extend the Fast Gradient Method applied to the dual problem in order to make it primal-dual, so that it allows not only to solve the dual problem, but also to construct nearly optimal and nearly feasible solution of the primal problem. We also prove a theorem about the convergence rate for the proposed algorithm in terms of the objective function residual and the linear constraints infeasibility.

We consider the problem of optimizing the sum of several rational functions via reduction to a problem with d.c. constraints. We propose a method of finding a local solution to the fractional program which can be subsequently used in the global search method based on the global optimality conditions for a problem with nonconvex (d.c.) constraints [21–23]. According to the theory, we construct explicit representations of the constraints in the form of differences of two convex functions and perform a local search method that takes into account the structure of the problem in question. This algorithm was verified on a set of low-dimensional test problems taken from literature as well as on randomly generated problems with up to 200 variables and 200 terms in the sum.

We suggest a partial linearization method for network equilibrium problems with elastic demands, which can be set-valued in general. The main element of this method is a partially linearized auxiliary problem. We propose a simple solution method for the auxiliary problem, which is based on optimality conditions. This method can be viewed as alternative to the conditional gradient method for the single-valued case. Some results of preliminary calculations which confirm efficiency of the new method are also presented.

This paper presents an extended version of the separation plane algorithm for subgradient-based finite-dimensional nondifferentiable convex optimization. The extension introduces additional cuts for epigraph of the conjugate of objective function which improve the convergence of the algorithm. The case of affine cuts is considered in more details and it is shown that it requires solution of an auxiliary convex subproblem the dimensionality of which depends on the number of additional cuts and can be kept arbitrary low. Therefore algorithm can make use of the efficient algorithms of low-dimensional nondifferentiable convex optimization which overcome known computational complexity bounds for the general case.

The residual method which is one of the standard regularization procedures for ill-posed optimization problems is applied to an improper convex programming problem. A typical problem for the residual method is reduced to the minimization problem for the quadratic penalty function. For this approach, we establish convergence conditions and estimates for the approximation accuracy. Further, here we present an algorithm for the practical realization of the proposed method.

This paper addresses a rather general problem of nonlinear optimization with the inequality constraints and the goal function defined by the (d.c.) functions represented by the difference of two convex functions. In order to reduce the constrained optimization problem to an unconstrained one, we investigate three auxiliary problems with the max-merit, Lagrange and penalty goal functions. Further, their relations to the original problem are estimated by means of the new Global Optimality Conditions and classical Optimization Theory as well as by examples.

The paper studies the trade in the spot electricity market based on submitting bids of energy consumers and producers to the market operator. We investigate supply function equilibrium (SFE) model, in which generation capacities are integrated into large generation companies that have a common purpose of maximizing their profits. For this case we prove the existence and uniqueness of equilibrium for a linear function of aggregate demand and quadratic costs. The mechanism is tested on the basis of the Siberian electric power system, Russia.

Contemporary domination of chain-stores in retailing is modeled, perceiving a monopolistic retailer as a market leader. A myriad of her suppliers compete in a monopolistic competitive sector, displaying quadratic consumers’ preferences for a differentiated good. The leader announces her markup before the suppliers choose their prices/quantities. She may restrict the range of suppliers or allow for free entry. Then, a market distortion, stemming from double marginalization and excessive variety would be softened whenever the government allows the retailer to apply an entrance fee to the suppliers, or/and per-quantity sales subsidies (doing the opposite to usual Russian regulation).

The existence of immigration proof partition for communities (countries) in a multidimensional space is studied. This is a Tiebout type equilibrium its existence previously was stated only in one-dimensional setting. The migration stability means that the inhabitants of a frontier have no incentives to change jurisdiction (an inhabitant at every frontier point has equal costs for all possible adjoining jurisdictions). It means that inter-country boundary is represented by a continuous curve (surface).Provided that the population density is measurable two approaches are suggested: the first one applies an one-dimensional approximation, for which a fixed point (via Kakutani theorem) can be found after that passing to limits gives the result; the second one employs a new generalization of Krasnosel’skii fixed point theorem for polytopes. This approach develops [8] and extends the result to an arbitrary number of countries, arbitrary dimension, possibly continuous dependence on additional parameters and so on.

This paper is devoted to Nash equilibrium search in quadratic n-person game, where payoff function of each player is quadratic with respect to its strategic variable. Interactions between players are defined by corresponding bilinear terms in the payoffs. First, the statement is considered without any assumptions on payoffs’ concavity. We use Nikaido-Isoda approach in order to reduce Nash equilibrium problem to optimization problem with nonconvex implicitly defined objective function. We propose global search algorithm based on the linearization of implicit part of the objective by linear support minorants. This technique allows to determine numerically whether the game has no equilibria. Then payoffs are assumed to be concave with respect to its strategic variables, and we suggest d.c. decomposition of the objective, thus corresponding local search method is applicable. Computational results are provided in the paper. Local search method is compared with extragradient equilibrium search algorithm.

We consider stochastic programming problems with probabilistic and quantile objective functions. The original distribution of the random variable is replaced by a discrete one. We thus consider a sequence of problems with discrete distributions. We suggest conditions, which guarantee that the sequence of optimal strategies converges to an optimal strategy of the original problem. We consider the case of a symmetrical distribution, the case of the loss function increasing in the random variable, and the case of the loss function increasing in the optimization strategy.

In this paper, a new Leaky-LMS (LLMS) algorithm that modifies and improves the Zero-Attracting Leaky-LMS (ZA-LLMS) algorithm for sparse system identification has been proposed. The proposed algorithm uses the sparsity of the system with the advantages of the variable step-size and l ₀ -norm penalty. We compared the performance of our proposed algorithm with the conventional LLMS and ZA-LLMS in terms of the convergence rate and mean-square-deviation (MSD). Additionally, the computational complexity of the proposed algorithm has been derived. Simulations performed in MATLAB showed that the proposed algorithm has superiority over the other algorithms for both types of input signals of additive white Gaussian noise (AWGN) and additive correlated Gaussian noise (ACGN).

The separating plane method with additional clippings and stockpiling (SPACLIP-S) for nonsmooth optimization is proposed in this paper. Both the theoretical and experimental investigations of the method showed that this method is efficient and widely applicable to nonsmooth optimization problems with convex objective functions. Computational experiments demonstrated a rather high performance of SPACLIP-S when applied to the Web page ranking problem. Web page ranking approach is widely used by search engines such as Google and Yandex to order Web pages. Page ranking problem is one of the most important problems in information retrivial due to wide range of applications. In this paper an iterative regularization method with a new penalty function for solving PageRank problem is also presented. Finally, experimental results of comparison of SPACLIP-S and other algorithms for solving test PageRank problems are provided.

In Euclidean plane geometry, Apollonius’ problem is to construct a circle in a plane that is tangent to three given circles. We will use a solution to this ancient problem to solve several versions of the following geometric optimization problem. Given is a set of customers located in the plane, each having a demand for a product and a budget. A customer is satisfied if her total, travel and purchase, costs do not exceed her budget. The task is to determine location of production facilities in the plane and one price for the product such that the revenue generated from the satisfied customers is maximized.

In this paper the location and design problem is considered. The point of this is that a Company is going to open markets to attract the largest share of total customers demand. This share varies flexibly depending on the markets location and its design variant. The Company vies for consumers demand with some pre-existing competitors markets. The mathematical model is nonlinear, therefore, there are difficulties in the application of exact methods and commercial solvers for it. The ways of constructing upper bounds of the objective function are described. Two algorithms based on the Variable Neighborhood Search approach are proposed. To study the algorithms a series of test instances similar to the real data of the applied problem has been constructed, experimental analysis is carried out. The results of these studies are discussed.

In the present paper, we formulate the network equilibrium problem with mixed demand containing the fixed and variable components. We present the equilibrium conditions and the conditions for existence of solution of this problem. In addition, we show that the network equilibrium problem with mixed demand generalizes the network equilibrium problems with fixed demand and elastic demand and establish the connection with the auction equilibrium problem. Preliminary computational experiments are also presented.