Mathematics Stack Exchange
Mathematics Stack Exchange

Questions tagged [discrete-optimization]

For questions about discrete optimization, which is a branch of optimization with discrete variables, opposed to continuous optimization in applied mathematics and computer science.

Discrete optimization is a branch of optimization in applied mathematics and computer science. As opposed to continuous optimization, some or all of the variables used in a discrete mathematical program are restricted to be discrete variables — that is, to assume only a discrete set of values, such as integers.

Two notable branches of discrete optimization are: combinatorial optimization, which refers to problems on graphs, matroids and other discrete structures, and integer programming.

These branches are closely intertwined however since many combinatorial optimization problems can be modeled as integer programs (e.g. shortest path) and conversely, integer programs can often be given a combinatorial interpretation.

1151 questions
0
votes
1 answer

Real-World Scheduling Problem for Wind Turbine Tower Installation

The tower of a wind turbine consists of a number $k$ of segments $s_i$ (e.g., 4 or 5), which have to be installed in a certain order $s_1, s_2, ..., s_k$. To build each segment, a specific time $t_i$ (e.g., 3 hours) is required. What complicates the…
Sebastian E
  • 141
  • 5
0
votes
1 answer

Minimize sum of products of partition

I have a set of positive integer numbers $A = \{a_1,\dots,a_N\}$ and I need to find a partition of $A$ into two sets, such that the sum of their products is minimal, i.e., $$ \min_{X,Y : X \cup Y = A} \prod_{x \in X} x + \prod_{y \in Y} y. $$ Is…
DrDizzy
  • 3
0
votes
1 answer

linear programming problem vehicle

I have a problem in which there are 4 ships available to transport people from 3 different bases back to a main base. 1.Vehicle 1 has a capacity of 50, can make 6 round trips and is allowed to visit bases 1 and 2. 2.Vehicle 2 has a capacity of 75,…
user1044924
0
votes
1 answer

What is the minimum of this double sum expression?

Given $n$ non-negative values. Their sum is $k$. $$ \sum_{i=1}^n x_i = k $$ The double sum expression is defined as: $$ \sum_{i=1}^n\big((\sum_{j=i}^n x_j)x_i\big)$$ I think that the expression reaches a minimum when $x_i = k/n$. It is true for…
ly2
  • 3
0
votes
1 answer

A Possible Mistake in Lovasz's "Submodular functions and convexity"

The possible mistake appears in Lovász L. (1983) Submodular functions and convexity. In: Bachem A., Korte B., Grötschel M. (eds) Mathematical Programming The State of the Art. Springer, Berlin, Heidelberg.…
Mark
  • 5,696
0
votes
2 answers

Maximizing a function defined in terms of meta notation

Let $f : \mathbb{N}^n \to \mathbb{N}$ be the function defined by $$f(w) = \sum\limits_{i=1}^m 1_A(M_iw)$$ where $M_i$ is the $i^{\text{th}}$ row of a matrix $M\in \text{Mat}_{m\times n}(\mathbb{N})$, $w$ is a column vector in $\mathbb{N}^n$, and…
Pedro Bach
  • 131
  • 8
0
votes
1 answer

Real division with arbitrary-precision discrete integers, how to?

I need a reliable arbitrary-precision division of discrete real numbers (ℝ), using arbitrary-precision discrete integers (ℤ). It is a classic problem, but it is not easy to verify the good solutions on the Web. I need a division algorithm to…
Peter Krauss
  • 163
  • 8
0
votes
1 answer

Optimization of material usage

I am required to send a request to a vendor for some pipes. They come in either 3m or 4m of length. I have a list of sections of length which are not really related to 3 or 6. However, I am required to find the number of 3m and 4m pipes each to…
Nagesh Eranki
  • 21
0
votes
0 answers

Minimum time needed to collect flowers

Given: Alice has basket that can contain flowers of sizes $1$ to $A$. Bob has basket that can contain flowers of sizes $B$ to $C$. Its given that $B
user313116
0
votes
1 answer

Choosing cells from square matrix

Imagine we have a square matrix with float values with $x$ rows and $x$ columns. We are to choose $x$ cells, such that the sum of the cells is as small as possible, but with the constraint that we can choose only one cell from each row, and only one…
Make42
  • 1,085
0
votes
0 answers

ILP and minimizing maximum relative error

I would like to find settings for a clock generation circuit, that can generate multiple clocks. The clock frequency generated $F_i$ is calculated as follows: $F_i = F_{input} * \frac{M}{D * O_i}$ Here $M$ and $D$ are variables shared for all…
ted
  • 111
-1
votes
2 answers

Problem like 0-1-Knapsack-Problem, with two constrains. Approximate solution in polynomial time wanted.

I have a discrete optimization problem. Let's say we have a shop that sells $N$ different stones. Each stone is characterized by 3 real numbers, say weight $a_i$, diameter $b_i$ and cost $c_i$: $s_i = (a_i, b_i, c_i), \text{for } i = 1, 2, ...,…
Falk Tandetzky
  • 103
1
2