Journal articles: 'Combinatorial and linear optimization'

1

Yannakakis, Mihalis. "Expressing combinatorial optimization problems by Linear Programs." Journal of Computer and System Sciences 43, no. 3 (December 1991): 441–66. http://dx.doi.org/10.1016/0022-0000(91)90024-y.

Full text

APA, Harvard, Vancouver, ISO, and other styles

2

Donets, Georgy, and Vasyl Biletskyi. "On Some Optimization Problems on Permutations." Cybernetics and Computer Technologies, no. 1 (June 30, 2022): 5–10. http://dx.doi.org/10.34229/2707-451x.22.1.1.

Full text

Abstract:

Numerous studies consider combinatorial optimization problems and their solution methods, since a large number of practical problems are described by means of combinatorial optimization models. Among these problems, the most prominent ones are function optimization problems on combinatorial configurations. Many of the studies mentioned above propose approaches and describe methods to solve combinatorial optimization problems for linear and fractionally linear functions on combinatorial sets such as permutations and arrangements. This work describes new approaches and methods to solve some maximization problems for linear, fractionally linear and quadratic functions on permutation set. Algorithms for solving these problems are given. For linear function, we provide a considerably easy method to find the permutation on which the function attains its maximum value. We describe the general algorithm to find fractionally linear function maximum. We consider the cases in which variables of numerator and denominator do not intersect, and when the numerator function and the denominator function have one common variable. We also describe the case in which the numerator function and the denominator function in total have incomplete variable list, i.e. when the total quantity of variables is less than the quantity of numbers in the permutation set. As for solving the problem of finding quadratic function maximum on permutation set, it turned out that there is no universal algorithm to solve this problem for any quadratic function. In this paper, we describe a method of finding maximum on permutation set for quadratic function consisting of two items. We provide examples of solving the considered optimization problems. Keywords: function, permutation, set, transposition, coefficients.

APA, Harvard, Vancouver, ISO, and other styles

3

DE FARIAS, I. R., E. L. JOHNSON, and G. L. NEMHAUSER. "Branch-and-cut for combinatorial optimization problems without auxiliary binary variables." Knowledge Engineering Review 16, no. 1 (March 2001): 25–39. http://dx.doi.org/10.1017/s0269888901000030.

Full text

Abstract:

Many optimisation problems involve combinatorial constraints on continuous variables. An example of a combinatorial constraint is that at most one variable in a group of nonnegative variables may be positive. Traditionally, in the mathematical programming community, such problems have been modeled as mixed-integer programs by introducing auxiliary binary variables and additional constraints. Because the number of variables and constraints becomes larger and the combinatorial structure is not used to advantage, these mixed-integer programming models may not be solved satisfactorily, except for small instances. Traditionally, constraint programming approaches to such problems keep and use the combinatorial structure, but do not use linear programming bounds in the search for an optimal solution. Here we present a branch-and-cut approach that considers the combinatorial constraints without the introduction of binary variables. We review the development of this approach and show how strong constraints can be derived using ideas from polyhedral combinatorics. To illustrate the ideas, we present a production scheduling model that arises in the manufacture of fibre optic cables.

APA, Harvard, Vancouver, ISO, and other styles

4

Barbolina, Tetiana. "Estimates of objective function minimum for solving linear fractional unconstrained combinatorial optimization problems on arrangements." Physico-mathematical modelling and informational technologies, no. 32 (July 6, 2021): 32–36. http://dx.doi.org/10.15407/fmmit2021.32.055.

Full text

Abstract:

The paper is devoted to the study of one class of Euclidean combinatorial optimization problems — combinatorial optimization problems on the general set of arrangements with linear fractional objective function and without additional (non-combinatorial) constraints. The paper substantiates the improvement of the polynomial algorithm for solving the specified class of problems. This algorithm foresees solving a finite sequence of linear unconstrained problems of combinatorial optimization on arrangements. The modification of the algorithm is based on the use of estimates of the objective function on the feasible set. This allows to exclude some of the problems from consideration and reduce the number of problems to be solved. The numerical experiments confirm the practical efficiency of the proposed approach.

APA, Harvard, Vancouver, ISO, and other styles

5

Pichugina, Oksana, and Liudmyla Koliechkina. "Linear constrained combinatorial optimization on well-described sets." IOP Conference Series: Materials Science and Engineering 1099, no. 1 (March 1, 2021): 012064. http://dx.doi.org/10.1088/1757-899x/1099/1/012064.

Full text

APA, Harvard, Vancouver, ISO, and other styles

6

Donets, G. A., and V. I. Biletskyi. "On the Problem of a Linear Function Localization on Permutations." Cybernetics and Computer Technologies, no. 2 (July 24, 2020): 14–18. http://dx.doi.org/10.34229/2707-451x.20.2.2.

Full text

Abstract:

Combinatorial optimization problems and methods of their solution have been a subject of numerous studies, since a large number of practical problems are described by combinatorial optimization models. Many studies consider approaches to and describe methods of solution for combinatorial optimization problems with linear or fractionally linear target functions on combinatorial sets such as permutations and arrangements. Studies consider solving combinatorial problems by means of well-known methods, as well as developing new methods and algorithms of searching a solution. We describe a method of solving a problem of a linear target function localization on a permutation set. The task is to find those locally admissible permutations on the permutation set, for which the linear function possesses a given value. In a general case, this problem may have no solutions at all. In the article, we propose a newly developed method that allows us to obtain a solution of such a problem (in the case that such solution exists) by the goal-oriented seeking for locally admissible permutations with a minimal enumeration that is much less than the number of all possible variants. Searching for the solution comes down to generating various permutations and evaluating them. Evaluation of each permutation includes two steps. The first step consists of function decreasing by transposing the numbers in the first n – 3 positions, and the second step is evaluation of the permutations for the remaining three numbers. Then we analyze the correlation (which is called balance) to define whether the considered permutation is the solution or not. In our article, we illustrate the localization method by solving the problem for n = 5. Keywords: localization, linear function, permutation, transposition, balance, position.

APA, Harvard, Vancouver, ISO, and other styles

7

Engau, Alexander, Miguel F. Anjos, and Anthony Vannelli. "On Interior-Point Warmstarts for Linear and Combinatorial Optimization." SIAM Journal on Optimization 20, no. 4 (January 2010): 1828–61. http://dx.doi.org/10.1137/080742786.

Full text

APA, Harvard, Vancouver, ISO, and other styles

8

Chung, Sung-Jin, Horst W. Hamacher, Francesco Maffioli, and Katta G. Murty. "Note on combinatorial optimization with max-linear objective functions." Discrete Applied Mathematics 42, no. 2-3 (April 1993): 139–45. http://dx.doi.org/10.1016/0166-218x(93)90043-n.

Full text

APA, Harvard, Vancouver, ISO, and other styles

9

Borissova, Daniela, Ivan Mustakerov, and Lyubka Doukovska. "Predictive Maintenance Sensors Placement by Combinatorial Optimization." International Journal of Electronics and Telecommunications 58, no. 2 (June 1, 2012): 153–58. http://dx.doi.org/10.2478/v10177-012-0022-6.

Full text

Abstract:

Predictive Maintenance Sensors Placement by Combinatorial Optimization The strategy of predictive maintenance monitoring is important for successful system damage detection. Maintenance monitoring utilizes dynamic response information to identify the possibility of damage. The basic factors of faults detection analysis are related to properties of the structure under inspection, collect the signals and appropriate signals processing. In vibration control, structures response sensing is limited by the number of sensors or the number of input channels of the data acquisition system. An essential problem in predictive maintenance monitoring is the optimal sensor placement. The paper addresses that problem by using mixed integer linear programming tasks solving. The proposed optimal sensors location approach is based on the difference between sensor information if sensor is present and information calculated by linear interpolation if sensor is not present. The tasks results define the optimal sensors locations for a given number of sensors. The results of chosen sensors locations give as close as possible repeating the curve of structure dynamic response function. The proposed approach is implemented in an algorithm for predictive maintenance and the numerical results indicate that together with intelligent signal processing it could be suitable for practical application.

APA, Harvard, Vancouver, ISO, and other styles

10

Mandi, Jayanta, Emir Demirovi?, Peter J. Stuckey, and Tias Guns. "Smart Predict-and-Optimize for Hard Combinatorial Optimization Problems." Proceedings of the AAAI Conference on Artificial Intelligence 34, no. 02 (April 3, 2020): 1603–10. http://dx.doi.org/10.1609/aaai.v34i02.5521.

Full text

Abstract:

Combinatorial optimization assumes that all parameters of the optimization problem, e.g. the weights in the objective function, are fixed. Often, these weights are mere estimates and increasingly machine learning techniques are used to for their estimation. Recently, Smart Predict and Optimize (SPO) has been proposed for problems with a linear objective function over the predictions, more specifically linear programming problems. It takes the regret of the predictions on the linear problem into account, by repeatedly solving it during learning. We investigate the use of SPO to solve more realistic discrete optimization problems. The main challenge is the repeated solving of the optimization problem. To this end, we investigate ways to relax the problem as well as warm-starting the learning and the solving. Our results show that even for discrete problems it often suffices to train by solving the relaxation in the SPO loss. Furthermore, this approach outperforms the state-of-the-art approach of Wilder, Dilkina, and Tambe. We experiment with weighted knapsack problems as well as complex scheduling problems, and show for the first time that a predict-and-optimize approach can successfully be used on large-scale combinatorial optimization problems.

APA, Harvard, Vancouver, ISO, and other styles

11

Sivakova, Tatiana Vladimirovna, Vladimir Anatolievich Sudakov, and Vasiliy Sergeyevich Shimko. "Research of methods for solving mixed integer linear programming problems." Keldysh Institute Preprints, no. 24 (2024): 1–18. http://dx.doi.org/10.20948/prepr-2024-24.

Full text

Abstract:

The paper discusses mathematical methods and software designed to solve optimization problems with linear objective functions and constraints, subject to additional restrictions on the integrality of variables. The main algorithms for combinatorial optimization are outlined and a comparative analysis of current packages and solvers for solving mixed integer linear programming problems in Python is carried out.

APA, Harvard, Vancouver, ISO, and other styles

12

Cuninghame-Green, R. A. "Book Review: Linear and combinatorial optimization in ordered algebraic structures." Bulletin of the American Mathematical Society 12, no. 1 (January 1, 1985): 148–50. http://dx.doi.org/10.1090/s0273-0979-1985-15325-x.

Full text

APA, Harvard, Vancouver, ISO, and other styles

13

Chowdhury, S. "Analytical approaches to the combinatorial optimization in linear placement problems." IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 8, no. 6 (June 1989): 630–39. http://dx.doi.org/10.1109/43.31519.

Full text

APA, Harvard, Vancouver, ISO, and other styles

14

Matsuda, S. ""Optimal" Hopfield network for combinatorial optimization with linear cost function." IEEE Transactions on Neural Networks 9, no. 6 (1998): 1319–30. http://dx.doi.org/10.1109/72.728382.

Full text

APA, Harvard, Vancouver, ISO, and other styles

15

Caballero, Rafael, Alfredo G. Hernández-Díaz, Manuel Laguna, and Julián Molina. "Cross entropy for multiobjective combinatorial optimization problems with linear relaxations." European Journal of Operational Research 243, no. 2 (June 2015): 362–68. http://dx.doi.org/10.1016/j.ejor.2014.07.046.

Full text

APA, Harvard, Vancouver, ISO, and other styles

16

Benson, Steven J., Yinyu Yeb, and Xiong Zhang. "Mixed linear and semidefinite programming for combinatorial and quadratic optimization." Optimization Methods and Software 11, no. 1-4 (January 1999): 515–44. http://dx.doi.org/10.1080/10556789908805761.

Full text

APA, Harvard, Vancouver, ISO, and other styles

17

Libura, Marek, and Yury Nikulin. "Stability and accuracy functions in multicriteria linear combinatorial optimization problems." Annals of Operations Research 147, no. 1 (August 22, 2006): 255–67. http://dx.doi.org/10.1007/s10479-006-0071-2.

Full text

APA, Harvard, Vancouver, ISO, and other styles

18

Huang, Yating, Ming Mao, Yanjun Li, and Weiguo Zhang. "Realization of combinatorial optimization of small-scale S-box." Journal of Physics: Conference Series 2078, no. 1 (November 1, 2021): 012025. http://dx.doi.org/10.1088/1742-6596/2078/1/012025.

Full text

Abstract:

Abstract This method describes a new technology for combinatorial logic optimization in detail, which can combine multiple criteria to reduce the hardware implementation area of the S-box. This technique can be achieved in two steps. The first is to optimize the non-linear part of the S-box. According to the optimization criterion of multiplication complexity, the quality of the S-box nonlinear part optimization can be judged, and the realization of the S-box with the smallest multiplication complexity can be obtained. The second step is to optimize the linear part of the S-box, and optimize on the basis of the results of the first step, focusing on reducing the number of XOR gates, and the optimization is performed through a heuristic-based algorithm. The above combinatorial logic optimization technology can be applied to any small S-box (5 × 5 and below). Finally, the S-box of PRESENT algorithm and CTC2 algorithm are used as examples to illustrate the optimization effect, and the optimal realization under the minimum AND gate condition is obtained.

APA, Harvard, Vancouver, ISO, and other styles

19

Ehrgott, Matthias. "Multiobjective Optimization." AI Magazine 29, no. 4 (December 28, 2008): 47. http://dx.doi.org/10.1609/aimag.v29i4.2198.

Full text

Abstract:

Using some real world examples I illustrate the important role of multiobjective optimization in decision making and its interface with preference handling. I explain what optimization in the presence of multiple objectives means and discuss some of the most common methods of solving multiobjective optimization problems using transformations to single objective optimisation problems. Finally, I address linear and combinatorial optimization problems with multiple objectives and summarize techniques for solving them. Throughout the article, I refer to the real world examples introduced at the beginning.

APA, Harvard, Vancouver, ISO, and other styles

20

Kawase, Yasushi, and Hanna Sumita. "Randomized Strategies for Robust Combinatorial Optimization." Proceedings of the AAAI Conference on Artificial Intelligence 33 (July 17, 2019): 7876–83. http://dx.doi.org/10.1609/aaai.v33i01.33017876.

Full text

Abstract:

In this paper, we study the following robust optimization problem. Given an independence system and candidate objective functions, we choose an independent set, and then an adversary chooses one objective function, knowing our choice. The goal is to find a randomized strategy (i.e., a probability distribution over the independent sets) that maximizes the expected objective value in the worst case. This problem is fundamental in wide areas such as artificial intelligence, machine learning, game theory and optimization. To solve the problem, we propose two types of schemes for designing approximation algorithms. One scheme is for the case when objective functions are linear. It first finds an approximately optimal aggregated strategy and then retrieves a desired solution with little loss of the objective value. The approximation ratio depends on a relaxation of an independence system polytope. As applications, we provide approximation algorithms for a knapsack constraint or a matroid intersection by developing appropriate relaxations and retrievals. The other scheme is based on the multiplicative weights update (MWU) method. The direct application of the MWU method does not yield a strict multiplicative approximation algorithm but yield one with an additional additive error term. A key technique to overcome the issue is to introduce a new concept called (η,γ)-reductions for objective functions with parameters η and γ. We show that our scheme outputs a nearly α-approximate solution if there exists an α-approximation algorithm for a subproblem defined by (η,γ)-reductions. This improves approximation ratios in previous results. Using our result, we provide approximation algorithms when the objective functions are submodular or correspond to the cardinality robustness for the knapsack problem.

APA, Harvard, Vancouver, ISO, and other styles

21

Bourdache, Nadjet, and Patrice Perny. "Active Preference Learning Based on Generalized Gini Functions: Application to the Multiagent Knapsack Problem." Proceedings of the AAAI Conference on Artificial Intelligence 33 (July 17, 2019): 7741–48. http://dx.doi.org/10.1609/aaai.v33i01.33017741.

Full text

Abstract:

We consider the problem of actively eliciting preferences from a Decision Maker supervising a collective decision process in the context of fair multiagent combinatorial optimization. Individual preferences are supposed to be known and represented by linear utility functions defined on a combinatorial domain and the social utility is defined as a generalized Gini Social evaluation Function (GSF) for the sake of fairness. The GSF is a non-linear aggregation function parameterized by weighting coefficients which allow a fine control of the equity requirement in the aggregation of individual utilities. The paper focuses on the elicitation of these weights by active learning in the context of the fair multiagent knapsack problem. We introduce and compare several incremental decision procedures interleaving an adaptive preference elicitation procedure with a combinatorial optimization algorithm to determine a GSF-optimal solution. We establish an upper bound on the number of queries and provide numerical tests to show the efficiency of the proposed approach.

APA, Harvard, Vancouver, ISO, and other styles

22

Žilinskas, J. "BRANCH AND BOUND WITH SIMPLICIAL PARTITIONS FOR GLOBAL OPTIMIZATION." Mathematical Modelling and Analysis 13, no. 1 (March 31, 2008): 145–59. http://dx.doi.org/10.3846/1392-6292.2008.13.145-159.

Full text

Abstract:

Branch and bound methods for global optimization are considered in this paper. Advantages and disadvantages of simplicial partitions for branch and bound are shown. A new general combinatorial approach for vertex triangulation of hyper‐rectangular feasible regions is presented. Simplicial partitions may be used to vertex triangulate feasible regions of non rectangular shape defined by linear inequality constraints. Linear inequality constraints may be used to avoid symmetries in optimization problems.

APA, Harvard, Vancouver, ISO, and other styles

23

Tominaga, Daisuke, Kazuki Mori, and Sachiyo Aburatani. "Linear and Nonlinear Regression for Combinatorial Optimization Problem of Multiple Transgenesis." IPSJ Transactions on Bioinformatics 9 (2016): 7–11. http://dx.doi.org/10.2197/ipsjtbio.9.7.

Full text

APA, Harvard, Vancouver, ISO, and other styles

24

Maculan, Nelson, Gérard Plateau, and Abdel Lisser. "Integer linear models with a polynomial number of variables and constraints for some classical combinatorial optimization problems." Pesquisa Operacional 23, no. 1 (January 2003): 161–68. http://dx.doi.org/10.1590/s0101-74382003000100012.

Full text

Abstract:

We present integer linear models with a polynomial number of variables and constraints for combinatorial optimization problems in graphs: optimum elementary cycles, optimum elementary paths and optimum tree problems.

APA, Harvard, Vancouver, ISO, and other styles

25

Thuillier, Kerian, Anne Siegel, and Loïc Paulevé. "CEGAR-Based Approach for Solving Combinatorial Optimization Modulo Quantified Linear Arithmetics Problems." Proceedings of the AAAI Conference on Artificial Intelligence 38, no. 8 (March 24, 2024): 8146–53. http://dx.doi.org/10.1609/aaai.v38i8.28654.

Full text

Abstract:

Bioinformatics has always been a prolific domain for generating complex satisfiability and optimization problems. For instance, the synthesis of multi-scale models of biological networks has recently been associated with the resolution of optimization problems mixing Boolean logic and universally quantified linear constraints (OPT+qLP), which can be benchmarked on real-world models. In this paper, we introduce a Counter-Example-Guided Abstraction Refinement (CEGAR) to solve such problems efficiently. Our CEGAR exploits monotone properties inherent to linear optimization in order to generalize counter-examples of Boolean relaxations. We implemented our approach by extending Answer Set Programming (ASP) solver Clingo with a quantified linear constraints propagator. Our prototype enables exploiting independence of sub-formulas to further exploit the generalization of counter-examples. We evaluate the impact of refinement and partitioning on two sets of OPT+qLP problems inspired by system biology. Additionally, we conducted a comparison with the state-of-the-art ASP solver Clingo[lpx] that handles non-quantified linear constraints, showing the advantage of our CEGAR approach for solving large problems.

APA, Harvard, Vancouver, ISO, and other styles

26

Magnanti, Thomas L. "Optimization: From Its Inception." Management Science 67, no. 9 (September 2021): 5349–63. http://dx.doi.org/10.1287/mnsc.2021.3955.

Full text

Abstract:

Optimization has been one of the most fundamental and extensive contributions of management science/operations research, with an enormous number of contributions and subfields developed by many researchers and practitioners. When the journal Management Science launched in 1954, little was known about optimization, including some results in nonlinear optimization and the simplex method and duality developed for linear programming. However, linear programming computations were limited to problems with at most 101 linear constraints. Then some early contributions by seminal researchers began to develop foundations for the field. I will review a few of these early contributions, focusing on the traveling sales problem and integer programming, decomposition, and column generation. I will summarize some research and applied contributions since then, including the enormous development of computations. I will focus on linear and integer programs with some material on combinatorial optimization. This paper was accepted by David Simchi-Levi, Special Section of Management Science: 65th Anniversary.

APA, Harvard, Vancouver, ISO, and other styles

27

Arroyo Montoro, Fernando, Sandra Gómez-Canaval, Karina Jiménez Vega, and Alfonso Ortega de la Puente. "A Linear Time Solution for N-Queens Problem Using Generalized Networks of Evolutionary Polarized Processors." International Journal of Foundations of Computer Science 31, no. 01 (January 2020): 7–21. http://dx.doi.org/10.1142/s0129054120400018.

Full text

Abstract:

In this paper we consider a new variant of Networks of Polarized Evolutionary Processors (NPEP) named Generalized Networks of Evolutionary Polarized Processors (GNPEP) and propose them as solvers of combinatorial optimization problems. Unlike the NPEP model, GNPEP uses its numerical evaluation over the processed data from a quantitative perspective, hence this model might be more suitable to solve specific hard problems in a more efficient and economic way. In particular, we propose a GNPEP network to solve a well-known NP-hard problem, namely the [Formula: see text]-queens. We prove that this GNPEP algorithm requires a linear time in the size of a given instance. This result suggests that the GNPEP model is more suitable to address problems related to combinatorial optimization in which integer restrictions have a relevant role.

APA, Harvard, Vancouver, ISO, and other styles

28

Iemets, Oleg A., and Tatyana N. Barbolina. "Properties of Combinatorial Optimization Unconstrained Problems on Arrangements with Linear and Linear-Fractional Objective Functions." Journal of Automation and Information Sciences 49, no. 1 (2017): 41–52. http://dx.doi.org/10.1615/jautomatinfscien.v49.i1.40.

Full text

APA, Harvard, Vancouver, ISO, and other styles

29

Ma, Lei, Weiyu Wang, Yaozong Zhang, Yu Shi, Zhenghua Huang, and Hanyu Hong. "Multi-features combinatorial optimization for keyframe extraction." Electronic Research Archive 31, no. 10 (2023): 5976–95. http://dx.doi.org/10.3934/era.2023304.

Full text

Abstract:

<abstract><p>Recent advancements in network and multimedia technologies have facilitated the distribution and sharing of digital videos over the Internet. These long videos contain very complex contents. Additionally, it is very challenging to use as few frames as possible to cover the video contents without missing too much information. There are at least two ways to describe these complex videos contents with minimal frames: the keyframes extracted from the video or the video summary. The former lays stress on covering the whole video contents as much as possible. The latter emphasizes covering the video contents of interest. As a consequence, keyframes are widely used in many areas such as video segmentation and object tracking. In this paper, we propose a keyframe extraction method based on multiple features via a novel combinatorial optimization algorithm. The key frame extraction is modeled as a combinatorial optimization problem. A fast dynamic programming algorithm based on a forward non-overlapping transfer matrix in polynomial time and a 0-1 integer linear programming algorithm based on an overlapping matrix is proposed to solve our maximization problem. In order to quantitatively evaluate our approach, a long video dataset named 'Animal world' is self-constructed, and the segmentation evaluation criterions are introduced. A good result is achieved on 'Animal world' dataset and a public available Keyframe-Sydney KFSYD dataset <sup>[<xref ref-type="bibr" rid="b1">1</xref>]</sup>.</p></abstract>

APA, Harvard, Vancouver, ISO, and other styles

30

Žilinskas, Julius. "MULTIDIMENSIONAL SCALING WITH CITY‐BLOCK DISTANCES BASED ON COMBINATORIAL OPTIMIZATION AND SYSTEMS OF LINEAR EQUATIONS." Mathematical Modelling and Analysis 14, no. 2 (June 30, 2009): 259–70. http://dx.doi.org/10.3846/1392-6292.2009.14.259-270.

Full text

Abstract:

Multidimensional scaling is a technique for exploratory analysis of multidimensional data. The essential part of the technique is minimization of a multimodal function with unfavorable properties like invariants and non‐differentiability. In this paper a two‐level optimization based on combinatorial optimization and systems of linear equations is proposed exploiting piecewise quadratic structure of the objective function with city‐block distances. The approach is tested experimentally and improvement directions are identified.

APA, Harvard, Vancouver, ISO, and other styles

31

Zhao, Xiangling, Yun Dong, and Lei Zuo. "A Combinatorial Optimization Approach for Air Cargo Palletization and Aircraft Loading." Mathematics 11, no. 13 (June 21, 2023): 2798. http://dx.doi.org/10.3390/math11132798.

Full text

Abstract:

The current air cargo loading plan handles the Air Cargo Palletization Problem (ACPP) and the Aircraft Weight and Balance Problem (WBP) separately, which has an impact on the optimization of the payload and the aircraft’s center of gravity (CG). Thanks to improvements in computer processing power, the joint combinatorial optimization of ACPP and WBP is now feasible. Three integer linear programming models are proposed: a Bi-objective Optimization Model (BOM), a Combinatorial Optimization Model (COM), and an Improved Combinatorial Optimization Model (IOM). The objectives of the models are the maximum loading capacity and the lowest CG deviation from a specified target CG. The models also consider a wide range of restrictions in the actual packing and stowage procedures, such as volume, weight, loading position, aircraft balance, and other aspects of aircraft and unit load devices. Four scenarios with various conditional metrics for three models are solved for the B777F aircraft using Gurobi. The results of the computations demonstrate that the BOM has the fastest solution speed, but the CG deviation is the largest, and in several cases the CG deviation results are unacceptable. The COM has the longest solution time, which is difficult to tolerate in practice. Despite taking a little longer to solve computationally than the BOM, the IOM offers the best optimization solution.

APA, Harvard, Vancouver, ISO, and other styles

32

Iemets, O. O., and T. M. Barbolina. "Solving Linear Unconstrained Problems of Combinatorial Optimization on Arrangements Under Stochastic Uncertainty." Cybernetics and Systems Analysis 52, no. 3 (May 2016): 457–66. http://dx.doi.org/10.1007/s10559-016-9846-x.

Full text

APA, Harvard, Vancouver, ISO, and other styles

33

Iemets, O. O., and T. M. Barbolina. "Lexicographic Equivalence in Mixed Combinatorial Optimization of Linear-Fractional Functions on Arrangements." Cybernetics and Systems Analysis 53, no. 2 (March 2017): 244–54. http://dx.doi.org/10.1007/s10559-017-9924-8.

Full text

APA, Harvard, Vancouver, ISO, and other styles

34

Hayalioglu, M. S., and S. O. Degertekin. "Minimum-weight design of non-linear steel frames using combinatorial optimization algorithms." Steel and Composite Structures 7, no. 3 (June 25, 2007): 201–17. http://dx.doi.org/10.12989/scs.2007.7.3.201.

Full text

APA, Harvard, Vancouver, ISO, and other styles

35

Tan, Dai Lun, Hong Xia Chen, and Ze Jian Cui. "A Class of Collocating Problem in Production and its Optimization Models." Applied Mechanics and Materials 513-517 (February 2014): 1215–20. http://dx.doi.org/10.4028/www.scientific.net/amm.513-517.1215.

Full text

Abstract:

The paper gives a general description of a typical combinatorial optimization problem-the collocation problem of production, and respectively establish the integer linear programming model based on the collocation ways and the integer linear programming model based on the optimal collocation amounts and the integer nonlinear programming model based on the local optimum. In the solving methods of the models, we have mainly analyzed the enumeration method and the method by using LINGO optimization software to solve the model. The instance shows that the models and solutions are all effective. The first model reflects the mechanism of the collocation problem better and gets the global optimal solution most likely, but more difficult to solve large-scale; the second model can quickly obtain the optimal the numbers of the finished products and all kinds of materials consumptions, but still need to enumerate the collocation ways step by step; the third model can gets the local optimal solution and the specific collocation ways through solving the model circularly. The optimization models and solution methods in this paper can be extended to the similar sub-problems of the combinatorial optimization problems, such as assembly problem, packing problem, the cutting problem, etc.

APA, Harvard, Vancouver, ISO, and other styles

36

Wright, Margaret H. "Interior methods for constrained optimization." Acta Numerica 1 (January 1992): 341–407. http://dx.doi.org/10.1017/s0962492900002300.

Full text

Abstract:

Interior methods for optimization were widely used in the 1960s, primarily in the form of barrier methods. However, they were not seriously applied to linear programming because of the dominance of the simplex method. Barrier methods fell from favour during the 1970s for a variety of reasons, including their apparent inefficiency compared with the best available alternatives. In 1984, Karmarkar's announcement of a fast polynomial-time interior method for linear programming caused tremendous excitement in the field of optimization. A formal connection can be shown between his method and classical barrier methods, which have consequently undergone a renaissance in interest and popularity. Most papers published since 1984 have concentrated on issues of computational complexity in interior methods for linear programming. During the same period, implementations of interior methods have displayed great efficiency in solving many large linear programs of ever-increasing size. Interior methods have also been applied with notable success to nonlinear and combinatorial problems. This paper presents a self-contained survey of major themes in both classical material and recent developments related to the theory and practice of interior methods.

APA, Harvard, Vancouver, ISO, and other styles

37

CHRISTOF, THOMAS, and GERHARD REINELT. "DECOMPOSITION AND PARALLELIZATION TECHNIQUES FOR ENUMERATING THE FACETS OF COMBINATORIAL POLYTOPES." International Journal of Computational Geometry & Applications 11, no. 04 (August 2001): 423–37. http://dx.doi.org/10.1142/s0218195901000560.

Full text

Abstract:

A convex polytope can either be described as convex hull of vertices or as solution set of a finite number of linear inequalities and equations. Whereas both representations are equivalent from a theoretical point of view, they are not when optimization problems over the polytope have to be solved. It is a challenging task to convert one description into the other. In this paper we address the efficient computation of the facet structure of several polytopes associated with combinatorial optimization problems. New results are presented which are of interest for theoretical investigations as well as for practical optimization.

APA, Harvard, Vancouver, ISO, and other styles

38

Lewis, Adrian S., and Michael L. Overton. "Eigenvalue optimization." Acta Numerica 5 (January 1996): 149–90. http://dx.doi.org/10.1017/s0962492900002646.

Full text

Abstract:

Optimization problems involving eigenvalues arise in many different mathematical disciplines. This article is divided into two parts. Part I gives a historical account of the development of the field. We discuss various applications that have been especially influential, from structural analysis to combinatorial optimization, and we survey algorithmic developments, including the recent advance of interior-point methods for a specific problem class: semidefinite programming. In Part II we primarily address optimization of convex functions of eigenvalues of symmetric matrices subject to linear constraints. We derive a fairly complete mathematical theory, some of it classical and some of it new. Using the elegant language of conjugate duality theory, we highlight the parallels between the analysis of invariant matrix norms and weakly invariant convex matrix functions. We then restrict our attention further to linear and semidefinite programming, emphasizing the parallel duality theory and comparing primal-dual interior-point methods for the two problem classes. The final section presents some apparently new variational results about eigenvalues of nonsymmetric matrices, unifying known characterizations of the spectral abscissa (related to Lyapunov theory) and the spectral radius (as an infimum of matrix norms).

APA, Harvard, Vancouver, ISO, and other styles

39

KUNER, PETER, and BIRGIT UEBERREITER. "PATTERN RECOGNITION BY GRAPH MATCHING—COMBINATORIAL VERSUS CONTINUOUS OPTIMIZATION." International Journal of Pattern Recognition and Artificial Intelligence 02, no. 03 (September 1988): 527–42. http://dx.doi.org/10.1142/s0218001488000303.

Full text

Abstract:

A generalization of subgraph isomorphism for the fault-tolerant interpretation of disturbed line images has been achieved. Object recognition is effected by optimal matching of a reference graph to the graph of a distorted image. This optimization is based on the solution of linear and quadratic assignment problems. The efficiency of the procedures developed for this objective has been proved in practical applications. NP-complete problems such as subgraph recognition need exhaustive computation if exact (branch-and-bound) algorithms are used. In contrast to this, heuristics are very fast and sufficiently reliable for less complex relational structures of the kind investigated in the first part of this paper. Constrained continuous optimization techniques, such as relaxation labeling and neural network strategies, solve recognition problems within a reasonable time, even in rather complex relational structures where heuristics can fail. They are also well suited to parallelism. The second part of this paper is devoted exclusively to them.

APA, Harvard, Vancouver, ISO, and other styles

40

Kalita, Akash, and Aadhith Rajinikanth. "Enhancing Bucket Sort Efficiency: A Combinatorial Approach to Algorithm Optimization." International Journal for Research in Applied Science and Engineering Technology 12, no. 10 (October 31, 2024): 1034–43. http://dx.doi.org/10.22214/ijraset.2024.64726.

Full text

Abstract:

Abstract: The efficiency of sorting algorithms is critical to numerous computational processes, including data management, search operations, and real-time applications. Among these algorithms, Bucket Sort is notable for its linear-time performance when data is uniformly distributed over a defined range. However, its efficiency suffers significantly with non-uniform data distributions, resulting in unbalanced buckets and increased sorting time. In our research, we explore how combinatorial algorithms can enhance Bucket Sort’s efficiency by optimizing bucket partitioning, dynamic allocation, and internal sorting strategies. Through rigorous mathematical proofs and analysis, we demonstrate that the application of combinatorial techniques yields substantial improvements in average-case performance, particularly in handling skewed data distributions. Practical case studies in large-scale data processing illustrate the adaptability and effectiveness of these optimizations, supporting their potential in real-world applications.

APA, Harvard, Vancouver, ISO, and other styles

41

Atserias, Albert, Meena Mahajan, Jakob Nordström, and Alexander Razborov. "Proof Complexity and Beyond." Oberwolfach Reports 21, no. 1 (September 30, 2024): 871–934. http://dx.doi.org/10.4171/owr/2024/15.

Full text

Abstract:

Proof complexity is a multi-disciplinary research area that addresses questions of the general form “how difficult is it to prove certain mathematical facts?” The current workshop focussed on recent advances in our understanding that the analysis of an appropriately tailored concept of “proof” underlies many of the arguments in algorithms, geometry or combinatorics research that make the core of modern theoretical computer science. These include the analysis of practical Boolean satisfiability (SAT) solving algorithms, the size of linear or semidefinite programming formulations of combinatorial optimization problems, the complexity of solving total NP search problems by local methods, and the complexity of describing winning strategies in two-player round-based games, to name just a few important examples.

APA, Harvard, Vancouver, ISO, and other styles

42

Iemets, Oleg A., and Tatyana N. Barbolina. "Polynomial Method for Solving Unconditional Linear Fractional Problem of Combinatorial Optimization on Arrangements." Journal of Automation and Information Sciences 49, no. 3 (2017): 46–56. http://dx.doi.org/10.1615/jautomatinfscien.v49.i3.60.

Full text

APA, Harvard, Vancouver, ISO, and other styles

43

Khachai, M. Yu. "Approximation issues of combinatorial optimization problems induced by optimal piecewise-linear learning procedures." Pattern Recognition and Image Analysis 21, no. 2 (June 2011): 144–47. http://dx.doi.org/10.1134/s1054661811020489.

Full text

APA, Harvard, Vancouver, ISO, and other styles

44

Barvinok, A. I. "Problems of combinatorial optimization, statistical sums and representations of the full linear group." Mathematical Notes of the Academy of Sciences of the USSR 49, no. 1 (January 1991): 3–9. http://dx.doi.org/10.1007/bf01137054.

Full text

APA, Harvard, Vancouver, ISO, and other styles

45

Semenova, N. V., L. N. Kolechkina, and A. M. Nagirna. "Vector optimization problems with linear criteria over a fuzzy combinatorial set of alternatives." Cybernetics and Systems Analysis 47, no. 2 (March 2011): 250–59. http://dx.doi.org/10.1007/s10559-011-9307-5.

Full text

APA, Harvard, Vancouver, ISO, and other styles

46

Bartosova, Viera, Svetlana Drobyazko, Sergii Bogachov, Olga Afanasieva, and Maria Mikhailova. "Ranking of Search Requests in the Digital Information Retrieval System Based on Dynamic Neural Networks." Complexity 2022 (April 11, 2022): 1–16. http://dx.doi.org/10.1155/2022/6460838.

Full text

Abstract:

The article is devoted to the problem of optimization of search request ranking algorithms in the digital information retrieval system. The algorithm of functioning of the neural network ranking unit based on Hopfield neural network is built. The ability to generate a ranked list of pages found as a result of the request in the digital information retrieval system can be provided by solving two problems of integer optimization: the problem of assignment of combinatorial sets of criteria for assessing the relevance of web page search and the problem of sorting of numbers—relevance values. The architecture of the neural network model based on the dynamic Hopfield neural network with binary output function designed for combinatorial optimization of the final list of documents found in the digital information retrieval system was synthesized. Promising variants of neural network models with binary output function of neurons for synthesis of the optimal evaluation plan with a combinatorial set of criteria by solving the problem of assignment were built. It has been proven that the built models differ in the rules for determining the coefficients of synaptic connections and external shifts; each of the created rules can be used independently or in different combinations with one another. In the course of analytical research, it was found that the optimization formulation of the problem of sorting of relevance values of search pages is identical to the problem of assignment of combinatorial groups of evaluation criteria provided that the elements of the performance matrix of the latter are defined as linear combinations of relevance values.

APA, Harvard, Vancouver, ISO, and other styles

47

Xu, Shenghe, Shivendra S. Panwar, Murali Kodialam, and T. V. Lakshman. "Deep Neural Network Approximated Dynamic Programming for Combinatorial Optimization." Proceedings of the AAAI Conference on Artificial Intelligence 34, no. 02 (April 3, 2020): 1684–91. http://dx.doi.org/10.1609/aaai.v34i02.5531.

Full text

Abstract:

In this paper, we propose a general framework for combining deep neural networks (DNNs) with dynamic programming to solve combinatorial optimization problems. For problems that can be broken into smaller subproblems and solved by dynamic programming, we train a set of neural networks to replace value or policy functions at each decision step. Two variants of the neural network approximated dynamic programming (NDP) methods are proposed; in the value-based NDP method, the networks learn to estimate the value of each choice at the corresponding step, while in the policy-based NDP method the DNNs only estimate the best decision at each step. The training procedure of the NDP starts from the smallest problem size and a new DNN for the next size is trained to cooperate with previous DNNs. After all the DNNs are trained, the networks are fine-tuned together to further improve overall performance. We test NDP on the linear sum assignment problem, the traveling salesman problem and the talent scheduling problem. Experimental results show that NDP can achieve considerable computation time reduction on hard problems with reasonable performance loss. In general, NDP can be applied to reducible combinatorial optimization problems for the purpose of computation time reduction.

APA, Harvard, Vancouver, ISO, and other styles

48

Sitek, Paweł, Krzysztof Bzdyra, and Jarosław Wikarek. "A Hybrid Method for Modeling and Solving Supply Chain Optimization Problems with Soft and Logical Constraints." Mathematical Problems in Engineering 2016 (2016): 1–16. http://dx.doi.org/10.1155/2016/1532420.

Full text

Abstract:

This paper presents a hybrid method for modeling and solving supply chain optimization problems with soft, hard, and logical constraints. Ability to implement soft and logical constraints is a very important functionality for supply chain optimization models. Such constraints are particularly useful for modeling problems resulting from commercial agreements, contracts, competition, technology, safety, and environmental conditions. Two programming and solving environments, mathematical programming (MP) and constraint logic programming (CLP), were combined in the hybrid method. This integration, hybridization, and the adequate multidimensional transformation of the problem (as a presolving method) helped to substantially reduce the search space of combinatorial models for supply chain optimization problems. The operation research MP and declarative CLP, where constraints are modeled in different ways and different solving procedures are implemented, were linked together to use the strengths of both. This approach is particularly important for the decision and combinatorial optimization models with the objective function and constraints, there are many decision variables, and these are summed (common in manufacturing, supply chain management, project management, and logistic problems). TheECLiPSesystem with Eplex library was proposed to implement a hybrid method. Additionally, the proposed hybrid transformed model is compared with the MILP-Mixed Integer Linear Programming model on the same data instances. For illustrative models, its use allowed finding optimal solutions eight to one hundred times faster and reducing the size of the combinatorial problem to a significant extent.

APA, Harvard, Vancouver, ISO, and other styles

49

Agarwal, Mridul, Vaneet Aggarwal, Abhishek Kumar Umrawal, and Chris Quinn. "DART: Adaptive Accept Reject Algorithm for Non-Linear Combinatorial Bandits." Proceedings of the AAAI Conference on Artificial Intelligence 35, no. 8 (May 18, 2021): 6557–65. http://dx.doi.org/10.1609/aaai.v35i8.16812.

Full text

Abstract:

We consider the bandit problem of selecting K out of N arms at each time step. The joint reward can be a non-linear function of the rewards of the selected individual arms. The direct use of a multi-armed bandit algorithm requires choosing among all possible combinations, making the action space large. To simplify the problem, existing works on combinatorial bandits typically assume feedback as a linear function of individual rewards. In this paper, we prove the lower bound for top-K subset selection with bandit feedback with possibly correlated rewards. We present a novel algorithm for the combinatorial setting without using individual arm feedback or requiring linearity of the reward function. Additionally, our algorithm works on correlated rewards of individual arms. Our algorithm, aDaptive Accept RejecT (DART), sequentially finds good arms and eliminates bad arms based on confidence bounds. DART is computationally efficient and uses storage linear in N. Further, DART achieves a regret bound of Õ(K√KNT) for a time horizon T, which matches the lower bound in bandit feedback up to a factor of √log 2NT. When applied to the problem of cross-selling optimization and maximizing the mean of individual rewards, the performance of the proposed algorithm surpasses that of state-of-the-art algorithms. We also show that DART significantly outperforms existing methods for both linear and non-linear joint reward environments.

APA, Harvard, Vancouver, ISO, and other styles

50

Wilder, Bryan, Bistra Dilkina, and Milind Tambe. "Melding the Data-Decisions Pipeline: Decision-Focused Learning for Combinatorial Optimization." Proceedings of the AAAI Conference on Artificial Intelligence 33 (July 17, 2019): 1658–65. http://dx.doi.org/10.1609/aaai.v33i01.33011658.

Full text

Abstract:

Creating impact in real-world settings requires artificial intelligence techniques to span the full pipeline from data, to predictive models, to decisions. These components are typically approached separately: a machine learning model is first trained via a measure of predictive accuracy, and then its predictions are used as input into an optimization algorithm which produces a decision. However, the loss function used to train the model may easily be misaligned with the end goal, which is to make the best decisions possible. Hand-tuning the loss function to align with optimization is a difficult and error-prone process (which is often skipped entirely).We focus on combinatorial optimization problems and introduce a general framework for decision-focused learning, where the machine learning model is directly trained in conjunction with the optimization algorithm to produce highquality decisions. Technically, our contribution is a means of integrating common classes of discrete optimization problems into deep learning or other predictive models, which are typically trained via gradient descent. The main idea is to use a continuous relaxation of the discrete problem to propagate gradients through the optimization procedure. We instantiate this framework for two broad classes of combinatorial problems: linear programs and submodular maximization. Experimental results across a variety of domains show that decisionfocused learning often leads to improved optimization performance compared to traditional methods. We find that standard measures of accuracy are not a reliable proxy for a predictive model’s utility in optimization, and our method’s ability to specify the true goal as the model’s training objective yields substantial dividends across a range of decision problems.

APA, Harvard, Vancouver, ISO, and other styles

Journal articles on the topic 'Combinatorial and linear optimization'

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles