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
25 views

Will the result of this maximization problem be the same for the two considered cases?

Suppose I have $2$ options: option1 and option2. For each option we associate a quantity $q$ that changes each time $t$, namely $q_1(t)$ and $q_2(t)$. Let $\mathbf{q}=(q_1(t),q_2(t))$. The different ...
0
votes
0answers
3 views

What are the special properties of the base polyhdron induced by a submodular function?

What are the special properties of the base-polyhdron induced by a submodular function ? Detailed definitions are given here at Sec 3. To ask more precisely I'm curious about given a polyhedron how ...
-4
votes
0answers
15 views

Inventory Distribution [closed]

I have inventory for goods that needed to be distributed to each branch as depicted in this picture and how much each branch will get goods depends on past sales record condition : goods unit ...
0
votes
0answers
48 views

Optimization over a discrete set

For any given real numbers such that $\lambda_1\geq\lambda_2\geq\lambda_3\geq\lambda_4\geq\lambda_5\geq\lambda_6$, show that the optimal solution of the problem \begin{align} \mbox{maximize}& ...
1
vote
1answer
53 views

Kill the creeps with minimum cost

Oz plays popular ARTS Dota 2. Invoker is one of the favourite Oz's heroes. Oz's skills are not perfect yet, so he uses only two spells - SunStrike and Tornado. Each of these spells takes some mana ...
0
votes
1answer
25 views

Differentiating social surplus function

Can someone possibly explain how to >>make sense<< of the following identity: $\int \frac{\partial \ max_d \{ u(x,d) + \epsilon(d) \} }{\partial u(x,d)} q(d\epsilon \lvert x) = \int I\{d = ...
6
votes
2answers
110 views

Finding minimum from matrix

Consider following $3\times 3$ matrix. $\begin{pmatrix}3&6&9\\ 2& 4 &8\\ 1 &5& 7 \end{pmatrix}$ I need to find combination of three numbers where each number ...
0
votes
0answers
19 views

Find the signs of elements in a list such that their sum is equal to zero

I have a set $X = \{x_1, x_2, \dots x_N\} \in [0;1]^N$ containing $N$ elements, initially all positive. My goal is to find a vector of signs $S = \{s_1, s_2, \dots s_N\} \in \{-1; 1\}^N$ such that: ...
0
votes
0answers
14 views

Mixed Integer Linear Program (MILP) question

I am trying to solve an MILP problem. I was wondering if Branch and Cut/Branch and Bound methods find optimal solution or not? Isn't the complexity exponential? Are there heuristic solvers available? ...
0
votes
0answers
8 views

Approximating a grid-valued signed distance function with a continuous function

I want to solve a continous optimization problem using IPOPT. My optimization involves a signed distance function whose values are defined on a 2D grid. Since IPOPT can't handle piecewise functions, I ...
0
votes
1answer
23 views

Is this reducible to a standard optimization problem?

There are $N$ agents who needs to be allocated $K$ discrete resources. There is a bottleneck threshold utility $R$ per agent. The $i$th agent has utility $r_{ij}$ if he is allocated $j$th resource. ...
3
votes
1answer
14 views

Discrete-time derivative of the sign function

How does one calculate the time derivative of $$ x_{k+1} = C_1\, \text{sign}(x_k-y_k)\sqrt{2\vert x_k-y_k\vert}, $$ with respect to $x_k$ ? I know that the right part of the equation should yield ...
2
votes
1answer
23 views

Perfect matching problem

We have a random graph G = (V,E). Two players are playing a game in which they are alternately selecting edges of graph so that in every moment all the selected edges are forming a simple path (path ...
1
vote
1answer
27 views

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 ...
1
vote
0answers
17 views

Book recommendation on integer programming ? (in order to solve a set cover problem)

I'm trying to solve a set cover problem. To put it shortly, my problem is about covering a $N \times M$ grid, by using various rectangles which have associated cost depending on their shape and ...
1
vote
1answer
31 views

0/1 knapsack upper bound

I'm new to the 0/1 knapsack problem and I've ordered my nodes into profit/weight as: Knapsack max weight: 12 ...
0
votes
1answer
19 views

Discrete optimization of weighted sum under constraint

Let $\lambda_1, \dots, \lambda_n \geq 0$, $\;\;c_1, \dots, c_n \in \mathbb{R}$ and $\;\;\gamma >0 $. We are looking for the maximum of function $f$ with $$ f(x) = x_1\lambda_1 + \dots + ...
4
votes
2answers
149 views

Optimization of parameter for recursive Cauchy sequence

I have the following recursive sequence I'm analyzing: $$V_0 = 50, V_1 = (1-10k)V_0,$$ $$V_{n+1} = (1-10k)V_n - 5kV_{n-1}$$ where $k > 0$ is a parameter that I'm investigating by running ...
4
votes
1answer
47 views

Is the optimal solution of a strictly convex function over $\mathbb{Z}^d$ a rounded version of its optimal solution over $\mathbb{R}^d$

Consider a strictly convex function $f: \mathbb{R}^d \rightarrow \mathbb{R}$. Let $x^* = \min_{\mathbb{R}^d} f(x)$ denote the (unique) minimum of this function over $\mathbb{R}^d$. Similarly, let ...
1
vote
0answers
8 views

Approximation for the minimal test cover / minimal group test problem

There are multiple approximation methods I find for the minimal test cover, where approximation is with respect to the size of the test set. However I am looking for approximation which starts with a ...
0
votes
1answer
60 views

Proof that minimum of sum of absolute differences is greater or equal of max value minus min value

Let's have an vector of natural numbers $[v_1, ..., v_N]$ my goal is to show that $$\sum_{i=1}^{N-1}|v_i - v_{i+1}| \ge v_{max} - v_{min}$$ where $v_{max} = \max_{i\in1...N}(v_i)$ and $v_{min} = ...
1
vote
1answer
47 views

Combining kindergardeners in 'fair' cookie-baking groups. Kirkman's schoolgirl problem extended version

I am coordinating cookie-baking events with kindergarten kids. This turns out to be a challenging problem, and I could use a little help: We would like a general way of creating 'fair' cookie-baking ...
1
vote
0answers
22 views

Multi-Objective Approximation Algorithms

Can algorithm approximations be combined in some form for purposes of multi-objective optimization? The study of approximation algorithms is very new to me, but I have been having a lot of difficulty ...
2
votes
1answer
80 views

What kind of algorithm might solve this type of optimization problem?

I am trading futures contracts in baskets at ratios that I compute by some method. Suppose there are $n$ contracts in a basket, and the ratio is given by $\mathbf{r}\in \mathbb{Z}^n$, so that the ...
0
votes
1answer
43 views

Wrong ILP solution with LPSolve (simple example)

I added the following example into LPSolve and found a strange issue. I don't want S1 and S2 to overlap within certain margins. ...
2
votes
1answer
19 views

Random allocation of groups of objects to agents

I have a poorly specified random allocation problem, which I need help in trying to tighten the definition and consider an effective algorithm. I have groups of objects, each group containing at ...
2
votes
0answers
24 views

What decides the structure of the dual variables taken in designing min-max type combinatorial optimization algorithms?

There are a bunch of combinatorial optimization problems like min cost flows and min weight perfect matchings that invoke duality and complimentary slackness to improve the primal feasible solution. ...
0
votes
1answer
33 views

Labeling constraints in a MILP

A manufacturing company consisting of two plants intends to introduce up to three new products. The production quantity of each product can be any number, integer or non-integer, but there is an upper ...
0
votes
1answer
59 views

Puzzle Involving Infinite Grid

This is a riddle that a coworker of mine posed to me, I have a solution but I'm curious to see what you all arrive at (I'm more interested in the approach than the answer). The question (potentially ...
0
votes
0answers
13 views

Properties of row-wise maximum on matrices.

All matrices are real. The operator $\max$ on matrices returns the largest value in each row. Consider a given matrix $D \in \mathbb{R}^{n,m}$ with $n > m$, independent columns and non-negative ...
1
vote
2answers
54 views

How to iterate through all the possibilities in with this quantifier?

This is a problem from Discrete Mathematics and its Applications My question is on 9g. Here is my work so far I am struggling with the exactly one person part. The one person whom everybody loves ...
1
vote
0answers
37 views

Combinatorial Optimization and Relaxation

There are a number of NP-hard optimization problems that may be formulated as either binary linear or quadratic programs, i.e. $\min_x c^tx $ s.t. $x \in K, x_i \in \{0,1\}$ or $\min_x x^t Q x $ s.t. ...
0
votes
0answers
11 views

Bicritiera combinatorial/linear optimization problem with an exponential number of non-dominated extreme point

In [Ruhe 1988] an instance of a bicriterial combinatorial optimization problem is constructed such that the number of non-dominated extreme points is exponential in the input size. Are there any ...
1
vote
0answers
65 views

When is $D \max G = \max D G$?

All matrices are real. The operator $\max$ on matrices returns the largest value in each row. We are interested in characterizing the set of matrices $D$ of size $n \times m$, $m < n$ such that we ...
2
votes
1answer
113 views

Given 500 parts and a list of orders, pick 50 parts to maximize the number of fulfillable orders

I'm going to start with a proclamation that this kind of optimization is new to me, so don't fault me for setting up the problem in a weird way. Please let me know if this is unclear. In a ...
2
votes
0answers
39 views

Structural / design / meta optimization - is there mathematical theory. Optimization over categories?

There is huge branch of mathematical optimization theory, but it mostly considers the finding optimal parameter values for the predefined structures. There are variational calculus and optimal control ...
0
votes
1answer
34 views

Discrete Math number of multiplications it takes to calculate $x^{15}$

This is in the topic of time complexity and algorithms in my list of problems and I really wanted to figure it out how to take a grip. Here's the problem: Find the number of multiplications needed ...
2
votes
3answers
47 views

Finding a ratio from a set of discrete values

For x = p/q, where x is a known value between 0.000 and 1.000 rounded to the thousandths place, p is an integer value between 0 and 127, and q is an integer value between 0 and 255: what is p and q? ...
0
votes
0answers
60 views

Find the finite sequence that minimizes the value of $T_5(P)$

Given a finite sequence $P(a_1,b_1),(a_2,b_2),...,(a_n,b_n)$, define $T_1(P):=a_1+b_1$, $\forall 2\leq k\leq n$, $T_k(P)=b_k+\max\{T_{k-1}(P),a_1+a_2+...+a_k\}$. Let $m=\min\{a,b,c,d\}$. ...
2
votes
1answer
56 views

Derivatives defined on a discrete state space

Ive been looking at certain economic papers, and optimal control papers. They define a state variable, $\omega$, which follows a discrete time Markov Chain. Then they define a utility function ...
0
votes
1answer
50 views

MINLP optimization with matlab reaching different solutions every run

I have written a program for optimizing a set of generators. I have hourly price and cost data and need to figure out when a generator should run or just stay off. I describe the problem in more ...
2
votes
0answers
23 views

discrete nonlinear convex optimization relaxation over a dense set

Be a discrete nonlinear convex optimization problem $P$ \begin{align} \underset{x\in \mathrm{C}^n}{\mathrm{min}} \ \ \ f(x) \\ Ax=b \\ c \leq x \leq d \end{align} $C$ is a dense in $F$. Is solving ...
0
votes
0answers
15 views

Binary Linear Programm: Check for feasability and multiple solutions

Assuming, I have binary integer program, e.g. given by: $ \arg\min_x \quad 0\\ \text{such that}\quad A_\text{eq} x = b_\text{eq}, x_i \in \{0,1\} $ Where also $[A_\text{eq}]_{ij} \in \{0,1\} $ and ...
0
votes
0answers
17 views

Discrete time adaption rule

Is it possible to find an update rule for $d(k)$ that satisfy following equation $$\log\frac{d^2(k+1)+1}{d^2(k)+1}=-c\log\left(|f(d(k))|+10\right)$$ where $c>1$ . I appreciate the time you'll take ...
0
votes
0answers
23 views

Nonlinear discrete time systems

Is it possible for discrete-time parameter $a(k)$ with an update rule like $a(k+1)=f(a(k))$ & always $|f(a(k))|<= c|a(k)|$ where $0<c<0.5$ to converge from the initial value $c_1$ ...
0
votes
0answers
78 views

Converting a boolean expression into CNF and DNF

Is there any systematic way to convert the following boolean expression (QUBO) into CNF or DNF? Here, $x_1, \ldots, x_n \in \{0, 1\}$, $a_1, \ldots, a_n \in \mathbb{Z}$ and $b_{1,1}, \ldots, b_{n,n} ...
0
votes
0answers
23 views

A variant of submodularity?

See the definition of submodulation functions: $$ f(A) + f(B) \geq f(A \cup B) + f(A \cap B) $$ Suppose I make this definition a little stronger: $$ f(A) + f(B) \geq f(A \cup B) + f(A \cap B) + A ...
1
vote
1answer
59 views

Minimizing image compression error (DCT)

I'm doing an assignement on image compression. I have to quantify the error given as $||A-\hat{A}||^2/||A||^2$, where $|\cdot|$ is the Eucledian norm. I really need help, so please just give some ...
0
votes
0answers
23 views

Algorithm to compare set of objects given a metric

Assume I have Objects $x\in X$ with an associated metric $d:X\times X\to\mathbb N_0$. I want to find a metric $d^*: \mathcal P(X) \times \mathcal P(X) \to\mathbb N_0$ wich compares sets of these ...
0
votes
1answer
56 views

Example Intersection Matroid is not a matroid.

Consider any two matroids $M_1=(E,\mathcal{I})$ and $M_2=(E,\mathcal{K})$ and let $\mathcal{Z}=\mathcal{I}\cap\mathcal{K}$. Can someone give an example where $(E,\mathcal{Z})=M_1 \cap M_2$ is not a ...