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
9
votes
1 answer

Best way to divide multiple equal groups into known unequal groups. Christmas Lights

I'm not a math guru, but I do like Christmas lights. I am helping set up a decent sized lighting display for my work, I have measured all outlines and props to figure out how many lights we are going to need for each area. The lights come with 100…
Tim Larson
  • 93
  • 2
8
votes
2 answers

Question about swindler-writer

This question arose from my curiosity. In one particular publishing house writer's salary depends on the amount of text he produces $-$ $p=20$ dollars for $s=1800$ symbols. How much money can earn a swindler-writer by pressing $n=40$ buttons on the…
Norbert
  • 56,803
2
votes
0 answers

is it a discrete optimization problem?

I have a function 'F' which has five input variables p1,p2,p3,p4,p5. Each one of the variable from p1 to p5 can have values from the sets S1,S2,S3,S4 and S5 respectively. S1,S2,S3,S4 and S5 are subsets of {A,B,C,D,E,F} Now my aim is to minimise the…
Surjya Narayana Padhi
  • 151
2
votes
1 answer

Knapsack Question Variant

Given a matrix $M = \left(a_{ij}\right)$ with non-negative integer entries, and a cost threshold $\alpha$, I want to find the maximum number of rows of $M$ I can select subject to a cost function $L$ not exceeding $\alpha$. The cost function $L$ is…
MathManiac5772
  • 664
2
votes
2 answers

Laminar family (of pairwise distinct non-empty sets) has at most $2n-1$

Show that a laminar family (of pairwise distinct non-empty sets) has at most $2n-1$ members, where $n$ is number of elements of a family of subsets. I tried to get only at most $n-1$ members, but we are asked to prove it is at most $2n-1$…
Naani Masi
  • 51
  • 5
1
vote
1 answer

how to minimize $sum(sum(\mod(A^T X A,2)))$

I have a constant binary matrix A (entries 0 or 1) and an unknown matrix X which is also binary. I'd like to find $X$ that minimizes $sum(sum(mod(A^T X A,2)))$; that is the number of 1's in $\mod(A^T X A,2)$. $A$ is a constant binary $k \times n$…
unknown
  • 1,018
1
vote
0 answers

Transformation of discrete, quadratic optimization problem into system of linear equations

I am reading the paper Poisson Image Editing by Pérez, Gangnet and Blake. On page 3, they derive a discrete quadratic optimization problem: $$\min_f \sum_{\left\langle p, q\right\rangle \cap \Omega \neq \emptyset} (f(p) - f(q) - v_{pq})^2 \text{…
chaosflaws
  • 274
1
vote
1 answer

Solving a many-to-one assignment problem with additional constraints

Assume there are $M$ items and $N$ people with $M \ge N$. A single item can be assigned to more than one person; however, item $i$ cannot be assigned more than $d_i$ times in total. Furthermore, each item has a category $c_i$ and a single person…
d125q
  • 2,370
  • 17
  • 19
1
vote
1 answer

limited spots for group items. different priority per group

Im not sure this is the right place to ask but it's a math problem so i think i'm at the right spot! list $L$ can hold $n$ items We have 3 groups $g_1$, $g_2$, $g_3$ each with their own $n$ items List $L$ needs to be filled with the items from…
Marcel
  • 113
1
vote
2 answers

Elements that always stay together in multiple sets

I have a problem that I have encountered a number of times in practice, and I'm curious if there is a formal name for it so I can look for other people's solutions (I wrote an algorithm to solve it, but maybe it could be faster). The problem is as…
Sam van Herwaarden
  • 227
1
vote
1 answer

Algorithm for optimal distribution of objects on a numberline

I need to distribute objects with a defined width on a numberline, which is already populated with other objects. There should be no overlap of objects and I have several constraints. E.g. no two green blocks in a row. The objective is to distribute…
mpt
  • 11
0
votes
0 answers

Maximisation with a Leontief function as constraint

Can anyone help me figure out how to maximise this problem knowing that the constraint is a leontief function? $$ \max_{WS,W,S}\pi_{WS} = p_{WS}.WS - (p_W . W + p_S.S)\\ \text{subject to } WS = \min\left(\frac{S}{a_S}; \frac{W}{a_W} \right) $$ I…
Meg
  • 15
0
votes
1 answer

Non-uniform discretization

Let $x \in [0, R]$. I want to discretize this variable in a way s.t. each interval is half wide than the previous one. How can I give an expression of $x_i$? All I'm given is that $\displaystyle \sum_{i=0}^{N-1} \dfrac{1}{2^i} = 2^{1-N} (-1 + 2^N)$.
ErikLAndre
  • 79
0
votes
1 answer

Optimising profit in responding to offers of customers

I have an linear algebra problem to solve. Currently I have n number of customer lists and m number of offers. I have matrix (P) with dimension m x n. Elements of P indicates probability of responding to the relevant offer for each customers. I…
user1925750
  • 31
1
2