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 ...

learn more… | top users | synonyms

0
votes
0answers
7 views

find an error of a quantized nonlinear equation

I have an equation to find an optimal phase in the complex I/Q plane so that: $\phi=\arcsin \frac{I^2+Q^2-1}{2IQ}$. now the $\phi$ is being discreticised / quantized to N bits so that $\phi_k=k\frac{2\...
0
votes
1answer
26 views

MILP how to make constraints numbers as a decision variable

I am trying to build a MILP. I need to set the number of linear constraints in the model as a decision variable. For example: ...
6
votes
2answers
106 views

What is the optimal route for visiting Pokéstops in Pokémon Go?

Okay, I've got a fun problem for you, which was not suited for the gaming stackexchange: Pokéstops are GPS locations with a certain radius. When you are in the radius, you can get certain ingame ...
0
votes
0answers
16 views

How to prove a mixed integer function $f(x,n_1,n_2)$ is convex [on hold]

I have a mixed-integer function (with continous and disceret variables); $f(x,n_1,n_2)$ , $x\in[0,a]$ and $n_1,n_2\in N_{0}$. How can I show for a given $x$, $f(x,n_1,n_2)$ is convex with respect to $...
0
votes
0answers
26 views

related to biconcave optimization

I have a bivariate function $f(x,y)$ both $x,y$ can assume values within closed interval i.e. $x_1\leq x\leq x_2$ and similarly $y_1 \leq y \leq y_2$. I know that for a fix value of $x$ the function ...
0
votes
0answers
10 views

Under which conditions discretization of convex\concave function is submodular?

Say, I have $f(x)$ with $x \in [0,1]$, then by discretization I mean $f(x_h)$ with $x_h \in \{0, h, 2h, \dots, 1\}$. I know about Lovasz extension, but it works in other way: given submodular ...
0
votes
1answer
44 views

Maximum Coin Changes That Does Not Add To a Dollar

What is the maximal amount of money attained from coins of 1, 5, 10, 25 cent denominations that none of its subset amounts to 100 cents? We can find the solution with exhaustive or naive dynamic ...
1
vote
0answers
19 views

Upper Bound for discrete objective value

I really need your help with the following problem: Let $ N \ge 3 $ be given, then consider $$ L(N)=\max\left\lbrace \sum_{j=2}^{N-1} \frac{c_j}{j} \, \middle| \, c_j \in \mathbb{N}, \nexists 0\le d \...
1
vote
0answers
27 views

Optimizing the product of two integers

How to efficiently solve the following optimization problem? Find $a$ and $b$ which minimize $ c = a * b $ under the constraints $ c \geq C $, $ a \leq A $, $ b \leq B $, where a, b, A, B, C are ...
2
votes
1answer
51 views

Any algorithm in literature to solve my problem? Should call it “Segment ordering”?

A slot with length $L$. I have $n$ segments, they have a positive integer length $x_1, x_2, \cdots, x_n$, respectively, and $\sum\limits_{i=1}^n x_i = L$. My goal is to fill the slot with these ...
1
vote
1answer
49 views

Binary Stochastic Programming with Independent or Positively Correlated Co-efficients

A manufacturer can select a maximum of $N$ stores to fulfill orders from a total of $M$ stores who are looking for inventory, $N\le M$. The case when $N\geq M$ is trivially solved when all stores ...
3
votes
1answer
42 views

Get an approximate factorization for a number $n$

For a given number $n$, I am interested in the closest number that can be written as a product of a given set of prime factors. More precisely, I am interested in a solution of the following problem ...
-1
votes
1answer
16 views

Sum of convex and decreasing function

I have a sum of decreasing function and a convex function over some domain. Can I say that the sum is also a convex function (i.e. there exists a unique minimum)?
3
votes
0answers
81 views

Optimal cyclic permutations (Formulate as standard problem)

How can we find cyclic permutations $\prod_i$ to be applied to each of corresponding $i$'th rows of a square matrix $X$ of size $n \times n$ such that a given sum of pairwise costs $\sum_{ij}C\left[\...
1
vote
2answers
36 views

Maximizing the sum of the squares of numbers whose sum is constant

I wonder how one goes about to find the maximum of $\sum v_i^2$, the $v_i$'s being positive integers whose sum $\sum_i v_i$ is fixed.
-1
votes
1answer
44 views

If $G$ and $H$ are two graphs, then what does $G \Delta H$ indicate in graph theory?

I came across this notation in a book titled "Combinatorial Optimization Theory and Algorithms" by Bernhard Korte and Jens Vygen.
1
vote
0answers
17 views

Recommend a optimization book with more coding examples?

I am interested in continuous optimization problems. However, I feel it is very difficult for me to understand the classic books such as Convex Optimization or Numerical Optmization. My problem with ...
2
votes
0answers
35 views

Finding a maximum with some constraints

I would like to maximize the term $ l_1b_1+l_2b_2+l_3b_3-2 $ such that the following conditions hold: $ 1>l_1>l_2>l_3>0 $, $ l_1,l_2,l_3 \in \mathbb{Q} $, $ b_1,b_2,b_3 \in \mathbb{N} $...
0
votes
0answers
17 views

Different formulation of this problem? Packing subsets into $k$ parts.

I am currently working on the following problem which I would like to formulate in a different way to see if any work on this has been done. Let $S = \{1, 2, \dots, n\}$ be a set and $H = \{h_1, h_2, ...
2
votes
0answers
10 views

Is there a known optimal solution for searching an ordered list with non-uniform query cost?

Let $D$ be the set of integers from $1$ to $n$ inclusive for $n \geq 1$, and let $$f(i) = \begin{cases} 0& i \leq k \\ i - k& i > k \end{cases}\,\,\,\forall\, i \in D$$ for some $k \...
0
votes
0answers
24 views

Optimal number of operations in the given scenario?

Suppose $$A_1=\{x_1+x_2+x_3,\quad x_2+x_3+x_4,\quad x_3+x_4+x_5\} \\ A_2=\{x_0+x_1+x_2, \quad x_0+x_1+x_8, \quad x_0+x_7+x_8\} \\ A_3=\{x_{10}+x_{11}+x_{12}, \quad x_{11}+x_{12}+x_7, \quad x_7+x_8+x_{...
0
votes
0answers
24 views

Book Recommendation for Infinite Dimensional Stochastic Optimization Problem in Discrete Time

Let $X(k)$ be i.i.d. discrete random variables and for all $k=0,1,2,...,N-1$, let $X:=(X(0),X(1)...,X(k))$ and $f := (f(0), f(1),...,f(k))$ with $f(k)$ be the decision function at time $k$, I want to ...
0
votes
0answers
15 views

Optimization of function on integer hypertetrahedron

I have the following optimization problem: Let $k,n \in \mathbb{N}$ with $k < n$. Let $N:=\{1, \dots,n\}$ and $D := \{^{t}(x_1, \dots, x_k) \in N^k \vert \sum_{i=1}^k x_i = N\}$ (hypertetrahedron)...
1
vote
0answers
49 views

How to solve a binary generalized assignment problem

I have the following generalized assignment problem: Z=max $\sum_{i=1}^{N}\sum_{j=1}^{M} x_{ij}R_{ij}$ such that $\quad 1)\quad \sum_{j=1}^{M} x_{ij}=1 \quad \forall i$ $\quad\quad\...
1
vote
0answers
52 views

What are some applications of vertex separators?

What are applications of finding a vertex separator that minimizes a cut in a graph. To clarify the problem I am talking about is is given a graph of n vertices and a partition $m_1,m_2,..,m_k $of ...
1
vote
1answer
131 views

Discrete log for prime powers

I was fiddling around and found that a function of the form $$L_b (x)=\left(\frac{b^{\phi (p^k)}-1}{p^k}\right)^{-1}\left(\frac{x^{\phi (p^k)}-1}{p^k}\right) \mod p^k$$ seems to behave similarly to a ...
4
votes
0answers
67 views

I'm walking towards my car - when should I try the remote, in an optimal sense?

I'm interested to learn about how discrete/'event' based elements are incorporated into optimisation problems. Hopefully this is an interesting problem in its own regard, it's inspired by a daily ...
0
votes
1answer
17 views

discrete convexity arising in a simple discrete optimization problem

Let $S$ be a fixed integer satisfying $S \ge 1$, let $a$ range over the integers between $1$ and $S$ inclusive, and for $i = 1, \dotsc, a$, let each $x_i$ range over the nonnegative integers, such ...
1
vote
0answers
34 views

Optimal choice for the values of money units

I just thought about how to find the optimal values for money units, given that you want your currency to come in $n$ different values (e.g. Euros come in 7 values for bills and 8 values for coins, so ...
1
vote
0answers
15 views

DAG descendant vertices tag sum

Hello I have a DAG with a tag per vertex. I want to write an algorithm to compute a per-vertex sum of the descendant vertices tags counting only once the repeated ones. Tracking visited vertices ...
0
votes
0answers
9 views

Correct definition of the co-occurrence graph of a pseudo-Boolean function

In section 4.6 of Pseudo-Boolean Optimization, Boros and Hammer have defined the co-occurrence graph of a pseudo-Boolean function as follows. If a pseudo-Boolean function $f : \mathbb{B}^n \mapsto ...
0
votes
0answers
11 views

Discrete Approximation to Dynamic Lagrangians

Suppose I have the following dynamic optimization problem, where I want to maximize the function $u(c,h)$ over time that's differentiable in both $c$ and $h$. I'm going to assume that the function $u$ ...
1
vote
1answer
15 views

Tree-width of a quadratic pseudo-Boolean function

A pseudo-Boolean function $f : \mathbb{B}^n \mapsto \mathbb{R}$ is of the following form. $$ f \left(x_1, \ldots, x_n\right) = \sum_{S\subseteq V} c_S \prod_{j \in S} x_j $$ Here $c_S \in \mathbb{R}$,...
2
votes
0answers
87 views

How to maximize this set function!?

Given a set $F$ and a function $p: 2^F \times 2^F \to [-1,0] $ such that $p (A \cup B, C) \leq p (A,C) $ for any sets $ A, B, C \in 2^F $ : Q1: How can we choose a non-empty set $O \in 2^F $ such ...
3
votes
2answers
978 views

Belt Balancer problem (Factorio)

So this question is inspired by the following thread: https://forums.factorio.com/viewtopic.php?f=5&t=25008 In it, the poster is examining an $8$-belt balancer (more on that to come) which he ...
1
vote
2answers
44 views

Minimizing the intersection of three sets

Let the sets $A,B,C$ which are all subsets of a larger set $N$. If $N(A), N(B), N(C), N$ are the populations respectively, then i need to find the minimum value of the population of their intersection ...
0
votes
2answers
45 views

Maximize $\ S=Max{(\sum_{i=1}^{n-1} |f(i+1)-f(i)|)}$

Let $\ f: \{1,2,...n\} → \{1,2,...n\} \quad bijection$ What I want to know is $\ S=Max{(\sum_{i=1}^{n-1} |f(i+1)-f(i)|)}$ Furthermore, Is there a way to know 'when' does S would be maximized? I ...
0
votes
0answers
22 views

Prove that a function is single peaked

Consider the following function: $$F(K)=\sum_{i=K+1}^{M} P(i,M) - \delta K P(K,M),$$ where $K,M\in \mathbb{N}$, $K<M/2$, $0<\delta,p<1$ and $P(i,M) = \binom{M}{i}p^i(1-p)^{M-i}$. I want to ...
0
votes
0answers
27 views

Kinds of logic and constraint programming

I am currently solving combinatorial optimisation problems using integer linear programs (ILP), and I would like to try something different (constraint satisfaction, logic programming, ...). I tried ...
1
vote
1answer
17 views

On the relationship between $\max(p_i)$ and $\omega(b)$, if $\sigma(b^2)/b^2$ is bounded above by a specific number $U$

Let $\omega(x)$ denote the number of distinct prime factors of $x$, and let $\sigma(x)$ be the sum of the divisors of $x$. Denote the abundancy index of $x$ by $I(x) = \sigma(x)/x$. Let the number $...
0
votes
0answers
12 views

Pseudo-Boolean functions restricted to integers

The Pseudo-Boolean functions are of the following form. $$ f : \mathbb{B}^n \to \mathbb{R} $$ I would like to know if there is a special sub-category of $$ f : \mathbb{B}^n \to \mathbb{Z} $$ with ...
0
votes
0answers
24 views

Linear integer programming

I am trying to find the optimal solution for the following linear integer programming: \begin{eqnarray} &&\underset{x_i, \forall i} {\text{maximize}} ~ \sum_{i=1}^N x_i a_i \\ && \...
0
votes
0answers
28 views

What are the steps to optimize simple Sphere function

I am new to optimization. How can one optimize the simple test function, Sphere function available on https://en.wikipedia.org/wiki/Test_functions_for_optimization?
0
votes
0answers
23 views

Quadratization of $5 x_1 x_2 − 7 x_1 x_2 x_3 x_4 + 2 x_1 x_2 x_3 x_5$ using Rosenberg's algorithm

In section 4.4 of Pseudo-Boolean Optimization by Boros et al., the authors have reproduced Rosenberg's quadratization algorithm as follows. Then they have given an example of implementing the ...
0
votes
1answer
26 views

Let $n_1e, n_2e,\ldots,n_ke$ be k numbers, find $e$ if $n_i\in\mathbb{Z}^+$

I have measured a quantized (or discrete) physical quantity. This means that there exists a fundamental quantity $e$ such that the physical quantity is an integer $n$ times the fundamental quantity $e$...
0
votes
0answers
10 views

Convert the Matching Polytope LP to Dual Program

For my course in discrete optimization I am studying about Polytopes and their dual programms. They state that the convex hull of Perfect Matchings in grahph $G=(V,E)$ is given by: $$ x\geq 0\\ x(\...
0
votes
0answers
14 views

Going from discrete solution to continuous solution (Dynamic Programming/Optimal Control)?

Suppose I have a discrete solution for a dynamic programming problem and an optimal control policy. If I can make the control policy continuous, by taking the limit as t-> 0, is that control policy ...
0
votes
2answers
32 views

log modular function whether supermodular or submodular

I have a modular function defined as $$g(X) = \sum_{i \in X} x_i, \quad\text{s.t. } x_i \geq 0$$ Now, I define a function $$f(X) = \exp(-g(X))$$ As I worked out, this function $f$ is submodular, ...
0
votes
0answers
12 views

Which are the alternative approaches to stochastic (online) gradient descend for online optimization?

I'm looking for some alternative approaches to online\stochastic gradient descent for online optimization such that 1) there exists some proof about the convergence of the parameters to some compact ...
0
votes
0answers
18 views

How to solve a multiple knapsack problem?

I have the following binary LP max $\sum_{l=1}^{L}\sum_{f=1}^{F}[S_{f} \sum_{k=1}^{K}a_{kl}b_{kf}]x_{lf}$ s.t $\quad 1)\quad \sum_{f=1}^{F}x_{lf}S_{f}\leq C_{l} \quad \forall l$ $\quad 2)\quad ...