The tag has no wiki summary.

learn more… | top users | synonyms

0
votes
1answer
16 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
99 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
44 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
7 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
43 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
42 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
14 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
74 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
27 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
18 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
23 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
32 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
47 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
10 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
45 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 ...
0
votes
0answers
23 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
63 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
110 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
37 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
35 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
49 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
34 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
21 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
12 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
51 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
21 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
57 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
20 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
53 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 ...
0
votes
0answers
18 views

What is an optimal order for integer vectors for minimization of the total distances?

I want to find an optimal order for a number of vectors (or a permutation of vectors) to minimize the sum of distances regarding to the following norm: (this norm is based on the distance on a cycle ...
0
votes
1answer
98 views

Algorithm producing a minimum spanning tree?

I need to prove that the following algorithm produces a minimum spanning tree(MST) upon termination. I think, looking at the lecture notes, that I need to reduce the operations to red and blue rules ...
0
votes
0answers
20 views

How to make likely-to-be-right-guess in “guess and verify method” in dynamic programming

So, in infinite horizon model with autonomous function, guess and verify method is used to solve the dynamic programming problem. But I can't simply rely on that method. At least I need to make ...
1
vote
1answer
33 views

Number of Integer solutions for this optimization problem

What is the number of integer solutions to the problem $$\sum_{i=1}^{i=k}x_i = n$$ subject to $\forall_i\ \ x_i \ge 0 $ note This should hold for both cases $k < n$ and $k \ge n$
0
votes
0answers
24 views

Significance of eigen vectors in Max-Plus algebra

In Max-Plus algebra we have notion of eigen values and eigen vectors. Given a matrix $A \in \mathbb{R}_{max}^{n\times n}$ , $\mu$ is an eigen value of $A$ if it satisfies $A \otimes v = \mu \otimes v$ ...
1
vote
0answers
95 views

Find maximum height of smallest flower

Little beaver planted n flowers in a row on his windowsill and started waiting for them to grow. However, after some time the beaver noticed that the flowers stopped growing.So he decided to come up ...
3
votes
0answers
149 views

Finding optimal velocity profile using Dynamic Programming

This question has been asked on scicomp but I thought maybe it's more a mathematical problem of how Bellman's idea is to be applied here. The main problem for me is: How to introduce the time ...
1
vote
1answer
129 views

Knuth's Sandwich Theorem: requesting proof clarification

The question is about F6 of Section 8 ("Elementary facts about cones") in Donald Knuth's Sandwich Theorem (http://arxiv.org/pdf/math/9312214.pdf). He claims to prove $(A \cap B)^* = A^* + B^*$ when ...
2
votes
0answers
44 views

Given a set of nonnegative numbers, put $\pm$ between them to minimize the magnitude of the result

Let's say I have a finite set of non-negative numbers. I have to put $+$ or $-$ between the numbers, in order to minimize the absolute sum.(i.e the sum has to be closest to 0) For example: the set: ...
0
votes
1answer
43 views

Book recommendations for Binary Integer Linear Programming

I'm looking for a book on BILP, which focuses on algorithms / solutions methods. So far, I only found the following books on ILP "Integer and combinatorial optimization" by Nemhauser, George L. ...
0
votes
0answers
22 views

Must the weight function be nonnegative for the greedy algorithm to be optimal for both a matroid and a greedoid?

Must the weight function be nonnegative for the greedy algorithm to be optimal for both a matroid and a greedoid? For a matroid, the codomain of the weight function is $[0,\infty)$, from Wikipedia ...
0
votes
0answers
25 views

$k$ edge-disjoint $r$-arborescences in an acylic digraph

An $r$-arborescence of a digraph $D$ is a rooted spanning tree with root $r\in V(D)$ in which all the edges of $D$ are directed away from $r$. I would like to prove the following: I have thought ...
1
vote
1answer
58 views

Reduce problem to max flow

I have the following question: Assume each student can borrow at most 10 books from the library, and the library has three copies of each title in its inventory. Each student submits a list of ...
0
votes
0answers
13 views

About the logistic map.

I need guide line about it I also wanted to know how it will appear in graph if we use mathematica or some other software for this.
1
vote
2answers
52 views

About Recurrence Relations.

I need help in order to solve the following question, Here RR is for Recurrence Relations.
1
vote
0answers
59 views

Proof that a Polytope has vertices

As part of my Discrete Optimization course, I have a homework where I have to prove that a Polytope has vertices. I seems to have all tools in hand (definition of a vertex, polytop, convex hull, etc.) ...