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

1
vote
0answers
14 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
22 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
15 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
23 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
20 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
14 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
41 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
51 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
0answers
72 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
64 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
16 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
33 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
14 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
8 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
85 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 ...
2
votes
0answers
394 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
40 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
20 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
25 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 ...
0
votes
1answer
15 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
27 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
21 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
25 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
12 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
30 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
17 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 ...
0
votes
1answer
59 views

How to solve a binary LP.

I have the optimization problem given below max $\sum_{i=1}^{N}\sum_{j=1}^{M} x_{ij}R_{ij}$ s.t $\quad 1)\quad \sum_{j=1}^{M} x_{ij}=1 \quad \forall i$ $\quad 2)\quad x_{ij} \in {0,1}$ $\quad ...
1
vote
1answer
59 views

Required conditions for product of two submodular functions to be submodular?

3.32 of Boyd's Convex Optimization book says: Products and ratios of convex functions. In general the product or ratio of two convex functions is not convex. However, there are some results that ...
0
votes
0answers
6 views

Minimizing percentiles of discrete distribution

I have a vector $\vec{v} \in \mathbb{R}^n$ and a matrix $A \in \mathbb{R}^{n \times m}$. For any $\vec{x} \in \mathbb{R}^m$, the vector $\vec{v} + A\vec{x} \in \mathbb{R}^n$ represents a discrete ...
1
vote
1answer
53 views

Ratio of two submodular functions is submodular?

Say we had 3 submodular functions $f(X)$, $g(X)$ and $h(X)$ is $\frac{f(X)}{g(X). h(X)}$ submodular as well? What can be said about the submodularity of $\frac{f(X)}{g(X)}$ and $f(X).g(X)$? I ...
3
votes
1answer
30 views

Nonlinear integer programming problem

I am trying to maximize the following function $$ f(m,n) = \frac{m \log 3 + n \log 2}{\sqrt{m^2+n^2}} $$ where $ n $ and $ m $ are integers, not both $ = 0 $, although one could be $ 0 $. This is ...
2
votes
0answers
37 views

How many combinations of 5 balls from 16 balls can you have in which the numbers on the balls are distinct?

We have $8$ blue balls that are numbered $\{1,2,3,4,5,6,7,8\}$. We have $8$ red balls that are numbered $\{1,2,3,4,5,6,7,8\}$. I think it should be ${8 \choose 5}\cdot 2^5$. There ${8 \choose 5}$ is ...
0
votes
0answers
14 views

Control zone and moat lower bound for the Euclidean traveling salesman problem

By using control zone and moat, we can obtain a lower bound for the TSP, which means that we cannot find such a tour with cost less than the value of control zones and moats. In Euclidean TSP, is ...
0
votes
2answers
49 views

Production optimization - what type of problem?

I want to make an algorithm that distributes orders $O_1,O_2,\dots$ to equipment $E^1,E^2,\dots$ so they can be processed in an optimal way. Different orders require different equipment for the ...
2
votes
0answers
28 views

Discrete Optimization Problem (VRP)

Consider the following setting : We have two pickup nodes (a) and (b)and two delivery nodes (c) and (d). At each pickup node, there are entities to be picked up and delivered by cars (n cars) to ...
2
votes
1answer
44 views

combinatorial optimization - argmax binary vector

I have the following combinatorial optimization problem: $$ \arg\max_{\mathbf{x}} \frac{\alpha + \mathbf{t}\cdot\mathbf{x}}{\beta + \mathbf{f}\cdot\mathbf{x}} $$ where the objective is to find the $n$ ...
1
vote
0answers
31 views

2 dimensional packing Problem with flexible objects

I have a kind of bin packing problem defined as follows: given: m bins $b_1,...,b_m$ of height $h_1,....,h_m$ and width w. The packing objects simply map $1,...,w$ to integers, hence these are ...
1
vote
0answers
15 views

Difference between submodular polyhedron and base polyhedron

Can anyone tell me the difference between base polyhedron and submodular polyhedron of a submodular function $f$ defined over base set $V$ ?. According to the definition, the base polyhedron is same ...
0
votes
0answers
26 views

How can I find a maximum matching?

I have a problem that I was able to conceptualize as following: Suppose that there are n groups of agents A1, A2, …, An. Group Ai contains Ki agents where Ki is an integer between, say, 1 and 10. ...
0
votes
0answers
29 views

Converting a linear-fractional program with an integer constraint to a linear program

Is it possible to convert the following linear-fractional program to a linear program ? $$ \max_x \frac{v\cdot x}{z \cdot x}\\s.t \\x_i \in \{0,1\}\\ \\ \sum_i x_i = k$$ where $v \in R^{d}$, $z \in R^...
0
votes
0answers
17 views

The problem of finding a smallest spanning 2-edge-connected subgraph of a graph G is NP-hard

For a given graph G = (V, E) with weights c(e), e ∈ E, the problem of finding a smallest spanning 2-edge-connected subgraph means that one has to find a subset F ⊆ E of smallest weight c(F) such ...
0
votes
1answer
14 views

How to use Support Vector Machines with Mixed data?

I have a dataset regarding student records with a mix of continuous, discrete & categorical data - the categorical data takes both nominal and ordinal forms. Ex: Continuous - GPA Ex: Discrete - ...