| 1. |
- Strömberg, Ann-Brith, 1961, et al.
(författare)
-
Mixed-Integer Linear Optimization: Primal–Dual Relations and Dual Subgradient and Cutting-Plane Methods
- 2020
-
Ingår i: Numerical Nonsmooth Optimization: State of the Art Algorithms. - Cham : Springer International Publishing. ; , s. 499-547, s. 499-547
-
Bokkapitel (övrigt vetenskapligt/konstnärligt)abstract
- This chapter presents several solution methodologies for mixed-integer linear optimization, stated as mixed-binary optimization problems, by means of Lagrangian duals, subgradient optimization, cutting-planes, and recovery of primal solutions. It covers Lagrangian duality theory for mixed-binary linear optimization, a problem framework for which ultimate success—in most cases—is hard to accomplish, since strong duality cannot be inferred. First, a simple conditional subgradient optimization method for solving the dual problem is presented. Then, we show how ergodic sequences of Lagrangian subproblem solutions can be computed and used to recover mixed-binary primal solutions. We establish that the ergodic sequences accumulate at solutions to a convexified version of the original mixed-binary optimization problem. We also present a cutting-plane approach to the Lagrangian dual, which amounts to solving the convexified problem by Dantzig–Wolfe decomposition, as well as a two-phase method that benefits from the advantages of both subgradient optimization and Dantzig–Wolfe decomposition. Finally, we describe how the Lagrangian dual approach can be used to find near optimal solutions to mixed-binary optimization problems by utilizing the ergodic sequences in a Lagrangian heuristic, to construct a core problem, as well as to guide the branching in a branch-and-bound method. The chapter is concluded with a section comprising notes, references, historical downturns, and reading tips.
|
|
| 2. |
|
|
| 3. |
|
|
| 4. |
- Engström, Christopher, 1987-, et al.
(författare)
-
PageRank, a Look at Small Changes in a Line of Nodes and the Complete Graph
- 2016
-
Ingår i: Engineering Mathematics II. - Cham : Springer. - 9783319421049 - 9783319421056 ; , s. 223-247
-
Bokkapitel (refereegranskat)abstract
- In this article we will look at the PageRank algorithm used as part of the ranking process of different Internet pages in search engines by for example Google. This article has its main focus in the understanding of the behavior of PageRank as the system dynamically changes either by contracting or expanding such as when adding or subtracting nodes or links or groups of nodes or links. In particular we will take a look at link structures consisting of a line of nodes or a complete graph where every node links to all others. We will look at PageRank as the solution of a linear system of equations and do our examination in both the ordinary normalized version of PageRank as well as the non-normalized version found by solving corresponding linear system. We will show that using two different methods we can find explicit formulas for the PageRank of some simple link structures.
|
|
| 5. |
- Engström, Christopher, 1987-, et al.
(författare)
-
PageRank, Connecting a Line of Nodes with a Complete Graph
- 2016
-
Ingår i: Engineering Mathematics II. - Cham : Springer. - 9783319421049 - 9783319421056
-
Bokkapitel (refereegranskat)abstract
- The focus of this article is the PageRank algorithm originally defined by S. Brin and L. Page as the stationary distribution of a certain random walk on a graph used to rank homepages on the Internet. We will attempt to get a better understanding of how PageRank changes after you make some changes to the graph such as adding or removing edge between otherwise disjoint subgraphs. In particular we will take a look at link structures consisting of a line of nodes or a complete graph where every node links to all others and different ways to combine the two. Both the ordinary normalized version of PageRank as well as a non-normalized version of PageRank found by solving corresponding linear system will be considered. We will see that it is possible to find explicit formulas for the PageRank in some simple link structures and using these formulas take a more in-depth look at the behavior of the ranking as the system changes.
|
|
| 6. |
- Markström, Klas
(författare)
-
From the ising and potts models to the general graph homomorphism polynomial
- 2017
-
Ingår i: Graph polynomials. - Boca Raton : CRC Press, [2017] | Series: Discrete mathematics and its applications : CRC Press. - 9781498755917 - 9781498755900 ; , s. 123-138
-
Bokkapitel (refereegranskat)abstract
- A number of classical models in statistical physics, such as the Ising model, Potts model, and lattice gas, can be formulated in terms of the generating function for weighted versions of homo-morphisms from G to some graph H. This chapter discusses the generating polynomial for homomorphisms from a graph G to the most general weighted graph on q vertices. For a fixed q, this is an object of polynomial size which contains a wealth of information about the graph G, but as we will later show it is not a complete graph invariant. The chapter describes this generating function as a polynomial, then recalls the definitions of a number of well-known graph polynomials, and partition functions from physics, and then proceeds to study the properties and relationships of these polynomials. There has been several approaches to defining an analogue of the Tutte polynomial for directed graphs as well.
|
|
| 7. |
|
|
| 8. |
- Faye, Bernadette, et al.
(författare)
-
Integers Represented by Ternary Quadratic Forms
- 2021
-
Ingår i: Women in Numbers Europe III. - Cham : Springer Science and Business Media Deutschland GmbH. ; , s. 207-231
-
Bokkapitel (refereegranskat)abstract
- In the case of the representation of an integer by an indefinite ternary quadratic form, the violation of the integral Hasse principle can be explained via the Brauer-Manin obstruction. In this note, we study the occurrences of this phenomenon for several families of non-diagonal ternary quadratic forms.
|
|
| 9. |
- Ghosh, Diptesh, et al.
(författare)
-
Tolerance-based algorithms for the traveling salesman problem
- 2008
-
Ingår i: Mathematical Programming and Game Theory for Decision Making. - New Jersey : World Scientific. - 9812813217 ; , s. 47-59
-
Bokkapitel (refereegranskat)abstract
- Most research on algorithms for combinatorial optimization use the costs of the elements in the ground set for making decisions about the solutions that the algorithms would output. For traveling salesman problems, this implies that algorithms generally use arc lengths to decide on whether an arc is included in a partial solution or not. In this paper we study the eect of using element tolerances for making these decisions. We choose the traveling salesman problem as a model combinatorial optimization problem and propose several greedy algorithms for it based on tolerances. We report extensive computational experiments on benchmark instances that clearly demonstrate that our tolerance-based algorithms outperform their weight-based counterpart. This indicates that the potential for using tolerance-based algorithms for various optimization problems is high and motivates further investigation of the approach.
|
|
| 10. |
- Hackl, Benjamin, et al.
(författare)
-
Uncovering a random tree
- 2022
-
Ingår i: 33rd International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms. - : Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern. ; , s. 10:1-10:17
-
Bokkapitel (övrigt vetenskapligt/konstnärligt)abstract
- We consider the process of uncovering the vertices of a random labeled tree according to their labels. First, a labeled tree with n vertices is generated uniformly at random. Thereafter, the vertices are uncovered one by one, in order of their labels. With each new vertex, all edges to previously uncovered vertices are uncovered as well. In this way, one obtains a growing sequence of forests. Three particular aspects of this process are studied in this extended abstract: first the number of edges, which we prove to converge to a stochastic process akin to a Brownian bridge after appropriate rescaling. Second, the connected component of a fixed vertex, for which different phases are identified and limiting distributions determined in each phase. Lastly, the largest connected component, for which we also observe a phase transition.
|
|
