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.

Filter by
Sorted by
Tagged with
1 vote
1 answer
19 views

Can this problem adjust to a Bin Packing problem?

hope you are doing fine. I am facing some mathematical problem which I am not certain of which type is it, nor how to approach its solution. Here is a picture with a representation (simplify) of the ...
user avatar
  • 111
0 votes
1 answer
19 views

Find the closest stack total weight where number of n values should be the same in all stack

Lets say I have potatoes with weight 7,5,4,8,12,10,4,8,12,12,13,12 I want to stack them in the way that all the stacks weight should be closest possible condition each stack should have equal amount ...
user avatar
1 vote
1 answer
56 views

Find the cheapest arrangement of non-overlapping colored rectangles necessary to achieve a sequence of colors behind holes

Input Let the input be a sequence of colors with any length at least 1. For example, (red, blue, red, green, blue). Each color is represented in the input as a string, not as any abstract notion of a ...
user avatar
1 vote
1 answer
50 views

To find the maximum possible value of their greatest common divisor $\gcd (a_1,a_2,\cdots, a_7)$.

The sum of seven distinct positive integers $a_1,a_2,\cdots, a_7$ is $315$. To find the maximum possible value of their greatest common divisor $\gcd (a_1,a_2,\cdots, a_7)$. If they were all equal ...
user avatar
  • 11.9k
1 vote
0 answers
32 views

Which $n^2$ points of a finite grid minimize average $L^1$ distance to a uniformly drawn point?

This is a correctly tagged repost of my question I asked yesterday. I came across the following problem: Given a finite grid in $\mathbb{N}^2$ (or equivalently $\mathbb{Z}^2$) consisting of $a$ rows ...
user avatar
4 votes
2 answers
119 views

No Dijkstra and no BFS? What else is there?

So, this is the scenario I have a graph with 7 points (say A to G) all interconnected (full mesh), and I want the best path to traverse all points starting from A and ending on G, but there are a ...
user avatar
1 vote
1 answer
15 views

Why is the size of a minimum vertex cover always greater than or equal to a maximal matching?

The topic I am dealing with right now is a 2-approximation algorithm for the minimum vertex cover. The proof seems fairly simple but I don't understand one assumption that is made. It is the ...
user avatar
  • 319
0 votes
0 answers
18 views

Is there a formula for the number of "faces"/boundaries of an hypercube defined by a multidimensional grid?

Consider a D dimensional grid, $ X = X_{1} \times X_{2} \times ... \times X_{D} $. Denote the size of $X_{j}$ with $| X_{j} |$. What is the formula for the number of "faces"/boundaries of ...
user avatar
1 vote
0 answers
24 views

Multi-objective optimization by using the optimal values of individual function

We want to minimize the following function: \begin{align} &\min_{x_1,y_1,x_2,y_2} \underbrace{\frac{x_1^2+y_1^2+x_2^2+y_2^2}{(x_1y_2-x_2y_1)^2}}_{f}+(\alpha-1)\underbrace{\frac{(x_1+\beta y_1)^...
user avatar
  • 13
1 vote
0 answers
36 views

How do you represent the number of iterations in the formulation of an optimization problem?

Let's say I want to minimize some function for f(x), with respect to x, in the minimum number of iterations. How would I represent the number of iterations in the formulation of this optimization ...
user avatar
  • 133
2 votes
1 answer
155 views

An efficient algorithm to generate a set of tuples satisfying a given upper bound for a distance between two arbitrary elements

Let $T_i^n$ denote a particular tuple of $n$ natural numbers (here $i < n!$ and we assume that the tuple contains all elements of the set $\{0, 1, \ldots, n-2, n-1\}$, i.e. there are no duplicates)....
user avatar
0 votes
0 answers
26 views

Christofides Algorithm for the TSP: A "polynomial time approximation algorithm"?

I'm currently studying the travelling salesman problem and Christofides algorithm. I think I understand that TSP is an NP-hard problem, and so the complexity of calculating a solution grows ...
user avatar
2 votes
1 answer
31 views

Assignment Problem: Roles and Candidates with Salary Budget

The problem: A company has $n$ roles to be filled. There are $m$ candidates. Each candidate $c$ the company hires may fulfill one or more roles. Each assignment of a candidate $c$ to a role $r$ ...
user avatar
  • 497
0 votes
0 answers
45 views

Discrete Optimization Problem: What is the optimal course schedule?

Linda Johansen, an incoming first-year MBA student, would like to determine her course schedule for her first two semesters of business school. Linda has created a list of twenty potential courses ...
user avatar
0 votes
1 answer
38 views

How to sort into X bins Y times with minimum overlap?

Let's say I'm hosting a series of dinner parties for a total of $N$ guests. Each night, there are $X$ tables, and we are meeting for a total of $Y$ nights. I want to preassign the guests to tables ...
user avatar
  • 3,908
0 votes
0 answers
23 views

Need help in using optimization theory to solve variables

$$\lvert H(f)\rvert=K\lvert\frac{1}{t_1^4}e^{-j2\pi ft_1}+\frac{1}{t_2^4}e^{-j2\pi ft_2}+\frac{1}{t_3^4}e^{-j2\pi ft_3}\rvert (1)$$ where K is constant,$|.|$means amplitude.I have the image of the ...
user avatar
0 votes
0 answers
26 views

Looking for resources on Dynamic Generalized Assignment problem

I'm trying to find previous research on the dynamized version of the Generalized Assignment Problem. That is, how to efficiently maintain an optimal solution in the case where existing workers can be ...
user avatar
2 votes
1 answer
28 views

Maximum flow with minimal number of vertices used

In many of the research problems I encountered recently, the following version of the minimum cost maximum flow problem came up. We are given a directed graph $D$, a source vertex $s$ and a terminal ...
user avatar
  • 43
0 votes
1 answer
26 views

Integer partition weighted minimum of maximum

Given a non-negative integer $n$ and a positive real weight vector $w$ with dimension $m$, partition $n$ into a length-$m$ non-negative integer vector that sums to $n$ (call it $v$) such that $\max ...
user avatar
0 votes
0 answers
24 views

Latin square analogy - finding a balanced arrangement of elements

I've come across a practical problem in discrete mathematics, and I suspect that some clever mind knows a better solution than brute force. Imagine that we are hosting a competition in which each of ...
user avatar
1 vote
0 answers
26 views

The optimal value function over all doubly stochastic matrices

Let $I = J = \{1,\dots,n\}$. Define set $X \subset \Bbb R^{I \times J}$ as all $n \times n$ doubly stochastic matrices $x = (x_{ij})$ satisfying $$\sum_{j=1}^n x_{ij} = 1, \quad \forall i $$ $$\sum_{i=...
user avatar
  • 97
0 votes
0 answers
18 views

Discretize the nonlinear Hammerstein operator

I would like to know please how to discretize the following special instance of nonlinear Hammerstein operator (in matlab if it is possible): $F : H^{1}[0,1] \rightarrow L^{2}[0,1],$ $ F(x)(s):=\int_{...
user avatar
  • 23
0 votes
1 answer
53 views

linear programming problem vehicle [closed]

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 ...
user avatar
2 votes
0 answers
61 views

Explicitly describe the cryptomorphism between greedoids and greedy set operators

A greedoid $\mathcal{F}$ on a finite ground set $E$ is cryptomorphic to an operator $\sigma$ (usually - and improperly - called the closure operator of the greedoid) such that: $X \subseteq \sigma(X)$...
user avatar
  • 4,122
0 votes
1 answer
55 views

Lower bound for the number of $4$-element sets generated from an arbitrary family of $3$-element sets in the worst case

Suppose we have $x_3$ distinct $3$-element sets chosen arbitrarily among the $\binom{7}{3}=35 \ge x_3$ subsets of $U=\{1,2,3,4,5,6,7\}$. Consider the $x_4$ distinct $4$-element sets that can be ...
user avatar
  • 1,879
2 votes
1 answer
76 views

Convergence Analysis of A Vector Sequence with Discretization Recurrences (with Toy Examples)

I'm confused by how to analyse if a vector sequence is convergent or not. Here I first post the original problem as follows: (Although this post is long, the problem meaning is easy to understand but ...
user avatar
  • 160
0 votes
1 answer
60 views

Minimum cost of forming a magic square

Hello i have a question regarding finding the minimum cost of converting a 3 x 3 matrix in to a magic square. So i have a simple question, why can't we solve it by finding the sum of the each row then ...
user avatar
1 vote
1 answer
23 views

assymetric graph coloring formulation

I'm reading this articel which is about formulating VCP to eleminate symmetric solution, they say: And then In order to eliminate some of the symmetrical solutions, they say these two constraint is ...
user avatar
0 votes
0 answers
21 views

Optimization of a function for a variable constrained to a set

I am familiar with the method of Lagrange multipliers for optimizing a function subject to some constraint. However, I have always seen this expressed along the lines of extremising $f(x,y)$ subject ...
user avatar
  • 101
1 vote
0 answers
26 views

How to bundle pairs of trips?

I have a database of real-time trip demands: ...
user avatar
  • 47
6 votes
3 answers
203 views

Given 10 statements relating to one another, what is the maximum number of true statements?

(I don't know whether this can be classified as an actual mathematics question. Feel free to take this down if it doesn't qualify.) Given the following statements, \begin{align} 1. &\text{ At ...
user avatar
0 votes
1 answer
32 views

Find minimum weight of tree of graph

Given a connected graph with $|V| = 10$ and $|E| = 20$, with $3$ edges of weight $3$, $4$ edges of weight $4$ and the remaining of weight $9$. What is the lowest weight in the subgraph spanning tree ...
user avatar
  • 593
0 votes
0 answers
25 views

Constrained coloring of bigraph nodes

I have a graph $G(U,V,E)$ representing a set of documents ($U$) and queries ($V$). Every document has 1-5 queries it is connected to, and every query has 1-50 documents it is connected to. There are ~...
user avatar
  • 176
0 votes
2 answers
44 views

How to conclude for maximum and minimum values of n according to the given constraints?

In a 128 days time, each of 9 friends goes to gym on exactly 78 days. There are $n$ days on which at least 5 of the friends gym. Maximum and minimum possible value of n is ? What i did was consider a ...
user avatar
0 votes
0 answers
26 views

Finding a binary vector that satisfies non-linear constraints

I’m looking for good heuristics for finding at least one (of a probably large set, although possibly none) high dimensional ($|v|>5000$) binary vector that satisfies a set of non-linear/non-...
user avatar
  • 176
0 votes
0 answers
28 views

Simplify an expression containing ceils and floors

I have an optimization problem that contains the variables $r$ and $s$ where $$r,s\in\mathbb{Z}$$ $$r\geq s\geq0$$ $c$ is a constant with $c\in\mathbb{Q}$ and $c\geq1$. I would like to minimize the ...
user avatar
  • 33
0 votes
1 answer
45 views

Finding a subset minimizing distance of the mean from a specific point.

Let $X := \{x_1, x_2,..., x_n\} \subset \mathbb{R}$, $d\in \mathbb{R}$, $k \in \mathbb{N}$. I am interested in the following optimization problem $$\min_{A \subseteq X, |A|=k} \left|\sum_{x_i\in A}\...
user avatar
  • 306
0 votes
1 answer
49 views

Real World Problem - Groups Visiting Various Stations

Context: This is a real world problem that I am trying to solve that I would appreciate some help with - I'm sure there's a Mathematical concept that will help me, but I'm struggling to remember back ...
user avatar
  • 4,955
0 votes
1 answer
38 views

Vertex is an extreme point

Given a polyhedron $P \subseteq \Bbb R^n$, a point $x \in P$ is called a vertex if there exists a vector $c$ such that $c · x > c · y$ for all $y \neq x \in P$. A point $x \in P$ is called an ...
user avatar
  • 996
0 votes
1 answer
25 views

How to evaluate the upper-bound for a multiobjective optimization problem?

Given a product set $P$, where each product $p_i \in P$ has a cost $p_i.c$ and a value $p_i.v$. Therefore, $\forall p_i \in P$, $p_i.c > 0$ and $p_i.v > 0$. The cost-efficient of a product is ...
user avatar
  • 11
2 votes
1 answer
48 views

Minimum number of balls and pigeonhole principle

A box contains 6 red, 8 green, 10 blue, 12 yellow and 15 white balls. What is the minimum number of balls to choose so we get 9 balls of the same color? I know that the answer to this problem is 6 + 8 ...
user avatar
  • 503
2 votes
1 answer
66 views

Traveling Salesman Problem where not all cities need to be visited

If there are a total of X possible cities to travel to, but our salesman only has to visit a fixed number of them Y<X, how do we choose the Y cities to travel to and the order? Has this problem ...
user avatar
2 votes
1 answer
43 views

Best guess of the asymptotic value of a finite sequence of terms

Consider an infinite sequence: $$S_\infty := (a_1,a_2,\cdots).$$ Further, suppose that the $a_i$ are all finite and the limit $a_\infty := \lim_{i \to \infty} a_i$ is well-defined and $a_\infty$ is ...
user avatar
  • 170
5 votes
1 answer
63 views

Minimum swaps necessary for every person to meet every other person at every location

The setting: There are 9 people. There are 3 locations. At any time, there are 3 people at each location. People can only swap locations at the same time. The goal: Every person visits each ...
user avatar
  • 153
0 votes
1 answer
26 views

Sequentially Dependance in Multiple Knapsack Problem

I have a combinatorial problem, which is similar to the multiple knapsack problem. An addition is that putting an item into a knapsack takes some time and I have to satisfy some time budget. Consider ...
user avatar
  • 1
0 votes
1 answer
52 views

Optimal Card Game Schedule

I have the responsibility of creating a schedule for a card game league. While creating the schedule, the following problem has arisen... Let $n,g,s \in \mathbb{N+}$ where $s \leq n$. Let $P = \{1, 2, ...
user avatar
  • 213
2 votes
1 answer
62 views

Finding Minimum Spanning Tree in O(n+m) time

I am now learning about MST and algorithms for finding it, like Prim's, Kruskal's and etc. However, what if we have a connected, undirected simple graph and all edges have a weight, BUT the possible ...
user avatar
  • 21
1 vote
1 answer
52 views

Beatrix's board and holes

This is the last question from UKMT's JMC 2016: Beatrix places dominoes on a 5 × 5 board, either horizontally or vertically, so that each domino covers two small squares. She stops when she cannot ...
user avatar
  • 5,041
0 votes
1 answer
27 views

Route Planning algortihms and optimization

Not sure if this is the right place to ask, but I have the following math-related problem. We need to schedule deliveries, about 20 per week. We have varying van availability, one with a capacity of 3 ...
user avatar
2 votes
1 answer
85 views

Prepare all dishes with the least different ingredients - what is this problem called?

I am trying to find the best way to solve the following problem: A cook has to prepare $n$ dishes, and for each dish he has $k$ different recipes. Each recipe is a non-empty subset of the set $I$ of ...
user avatar
  • 23

1
2 3 4 5
19