514 research outputs found
Cloud Branching
No full textBranch-and-bound methods for mixed-integer programming (MIP) are traditionally based on solving a linear programming (LP) relaxation and branching on a variable which takes a fractional value in the (single) computed relaxation optimum. In this paper we study branching strategies for mixed-integer programs that exploit the knowledge of multiple alternative optimal solutions (a cloud) of the current LP relaxation. These strategies naturally extend state-of-the-art methods like strong branching, pseudocost branching, and their hybrids.
We show that by exploiting dual degeneracy, and thus multiple alternative optimal solutions, it is possible to enhance traditional methods. We present preliminary computational results, applying the newly proposed strategy to full strong branching, which is known to be the MIP branching rule leading to the fewest number of search nodes. It turns out that cloud branching can reduce the mean running time by up to 30% on standard test sets
Ten years of feasibility pump, and counting
No full textThe Feasibility Pump (fp) is probably the best-known primal heuristic for mixed-integer programming. The original work by Fischetti et al. (Math Program 104(1):91–104, 2005), which introduced the heuristic for 0–1 mixed-integer linear programs, has been succeeded by more than twenty follow-up publications which improve the performance of the fp and extend it to other problem classes. Year 2015 was the tenth anniversary of the first fp publication. The present paper provides an overview of the diverse Feasibility Pump literature that has been presented over the last decade
List of Members of Fort Berthold Delegation, May 2, 1949
No full textThis document, dated May 2, 1949, by an unknown author, consists of a typewritten list of names beginning with Fort Berthold Indian Agency Superintendent Ben Reifel, followed by the names and towns of nine of the ten members serving on the Tribal Business Council of the Three Affiliated Tribes of the Fort Berthold Reservations.
Below the list of Tribal Business Council Members is a short list titled Delegates.
Handwritten at the top of the page is Ft. Berthold Delegation and below that, May 2, 1949. To the right of this is written, s. JRes 11.
See also:
Letter from Ira Waters, Fred Lone Bear, and George Parshal to Senator Langer Regarding Conflict Surrounding Delegates Sent by Tribal Council for Senate Joint Resolution 33 Hearing, April 25, 1949
Hearings before the Subcommittee on Indian Affairs of the Committee on Public Lands House of Representatives Eighty-First Congress First Session on H.J. Res. 33 Providing for the Ratification by Congress of the Contract to Purchase Indian Lands by the United States from the Three Affiliated Tribes of Fort Berthold, North Dakota
An Act to Vest Title to Certain Lands of the Three Affiliated Tribes of the Fort Berthold Reservation, North Dakota, in the United States, and to Provide Compensation Thereforhttps://commons.und.edu/langer-papers/1953/thumbnail.jp
Berthold Viertel
No full textThe author and director Berthold Viertel (1885-1953), born and raised in Vienna, left a broad but fragmented autobiographical project, which changed a lot over time through exile and remigration. Katharina Prager analyses Viertels autobiographical practice and his re- and deconstructions of collective memory of a "different" Vienna around the year 1900, a counter image of the idealistic presentations by his friend Stefan Zweig. She connects his memories of "critical modernness" with studies about the Wiener Moderne in relation to 15 biographical spaces of memory. Berthold Viertel is shown as a prominent actor and networking expert in the cultural scene of Vienna, and as a typical representative of a critical avant-garde, whose lines of tradition he tried to preserve by his writing
Improving Conflict Analysis in MIP Solvers by Pseudo-Boolean Reasoning
No full textConflict analysis has been successfully generalized from Boolean satisfiability (SAT) solving to mixed integer programming (MIP) solvers, but although MIP solvers operate with general linear inequalities, the conflict analysis in MIP has been limited to reasoning with the more restricted class of clausal constraint. This is in contrast to how conflict analysis is performed in so-called pseudo-Boolean solving, where solvers can reason directly with 0-1 integer linear inequalities rather than with clausal constraints extracted from such inequalities.
In this work, we investigate how pseudo-Boolean conflict analysis can be integrated in MIP solving, focusing on 0-1 integer linear programs (0-1 ILPs). Phrased in MIP terminology, conflict analysis can be understood as a sequence of linear combinations and cuts. We leverage this perspective to design a new conflict analysis algorithm based on mixed integer rounding (MIR) cuts, which theoretically dominates the state-of-the-art division-based method in pseudo-Boolean solving.
We also report results from a first proof-of-concept implementation of different pseudo-Boolean conflict analysis methods in the open-source MIP solver SCIP. When evaluated on a large and diverse set of 0-1 ILP instances from MIPLIB2017, our new MIR-based conflict analysis outperforms both previous pseudo-Boolean methods and the clause-based method used in MIP. Our conclusion is that pseudo-Boolean conflict analysis in MIP is a promising research direction that merits further study, and that it might also make sense to investigate the use of such conflict analysis to generate stronger no-goods in constraint programming
List of Items Related to Needs of the Three Affiliated Tribes of the Fort Berthold Reservation, Undated
No full textThis undated list was filed in one of two folders labeled Fort Berthold Indians in US Representative Usher Burdick\u27s files. Almost all of the items in the folder with it were from the 1950s. The items on the list all relate to the needs of the Three Affiliated Tribes of the Fort Berthold Reservation. A handwritten note on the list adds, S. 3311 referring to US Senate Bill 3311.https://commons.und.edu/burdick-papers/1037/thumbnail.jp
Unsealed Architecture: to "Climate-Friendly" cities
No full textWe hosted our second guest, Professor Manfred BERTHOLD from Vienna Technical University, in the first of three thematic seminar series organized by the Department of Architecture, "Notes from the Field". Berthold presented some of his projects related to "Climate-Friendly" cities.
Manfred Berthold:
The architect Manfred Berthold - since 2009 professor at the Institute for Architecture and Design at the Vienna University of Technology - has supervised more than 500 master's and diploma theses in the past 10 years. The question always arises as to the quality of the achievements of architecture graduates in a non-university comparison - a cross-university quality assessment could be the Europe-wide "Campus Masters" competition organized by Baunetz. Manfred Berthold is the author of the book Architecture Costs Space (2010, Springer-Verlag). In 2017 and 2011, he received the Best Teacher Award from the Vienna University of Technology as the best university teacher in Faculty of Architecture and Spatial Planning. To Berthold, architecture seals our landscape. In densely populated areas of industrialized countries, surface sealing represents one of the most pressing basic ecological problems. In terms of climate protection, built-up soil can no longer serve as water permeability and soil fertility and as a carbon dioxide store. With urban and traffic planning that is gentle on the soil, the climate of tomorrow is being shaped today
Branching on multi-aggregated variables
No full textAbstract. In mixed-integer programming, the branching rule is a key component to a fast convergence of the branch-and-bound algorithm. The most common strategy is to branch on simple disjunctions that split the domain of a single integer variable into two disjoint intervals. Multi-aggregation is a presolving step that replaces variables by an affine linear sum of other variables, thereby reducing the problem size. While this simplification typically improves the performance of MIP solvers, it also restricts the degree of freedom in variable-based branching rules. We present a novel branching scheme that tries to overcome the above drawback by considering general disjunctions defined by multi-aggregated variables in addition to the standard disjunctions based on single vari-ables. This natural idea results in a hybrid between variable- and con-straint-based branching rules. Our implementation within the constraint integer programming framework SCIP incorporates this into a full strong branching rule and reduces the number of branch-and-bound nodes on a general test set of publicly available benchmark instances. For a specific class of problems, we show that the solving time decreases significantly.
- …
