The tag has no wiki summary.

learn more… | top users | synonyms

0
votes
0answers
33 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
33 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
12 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
17 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
9 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
15 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
18 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
7 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
19 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
47 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
9 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
42 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
14 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
90 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
17 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
29 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
17 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
94 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
135 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
114 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
39 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
30 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
16 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
20 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
39 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
12 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
43 views

About Recurrence Relations.

I need help in order to solve the following question, Here RR is for Recurrence Relations.
1
vote
0answers
43 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.) ...
1
vote
0answers
18 views

Comparing the hardness of optimizing two similar, but different expressions

Suppose we have binary variables $y_1, ..., y_n$. To make the representation simple, we show the concatenated vector as $\mathbf{y} = (y_1, ..., y_n)$. Consider the two following functions: $$ ...
0
votes
0answers
43 views

Removing backups in an exponential fashion

Background: I want to create a backup system that utilizes the full space of a hard-disk. Given that all backups are approximately equal in size this means that I can save a fixed amount of backups. ...
3
votes
0answers
79 views

How to find the minimal path between points in a planar set with holes in it?

When I was a commuter student, I would park in a very large parking that that had a set of stairs in a corner that I had to climb. In general, I had to park far away from this corner in an almost full ...
2
votes
1answer
29 views

How is the upper bound of a minimisation IP determined during branch-and-bound?

When using the branch-and-bound algorithm to solve an Integer Programming (IP) problem, the entire enumeration tree doesn't need to be evaluated and that's where the speed-up is achieved. Suppose the ...
1
vote
0answers
29 views

Finding 'closest' function subject to constraints on derivatives

Suppose I have a real-valued function $f(t)$ for $t\in[0,T]$ s.t. $f'''(t)$ is defined as piecewise constant values: $$ f'''(t) = \begin{cases} k_0, & 0 < t \le t_0 \\ k_1, & t_0 < t ...
3
votes
1answer
112 views

Minimizing Height of a Table

This optimization question popped into my mind while working with latex tables: Suppose we have a table with $m$ rows and $n$ columns, and for each $1\le i\le m,1\le j\le n$ we are given $T(i,j)$ ...
2
votes
0answers
16 views

is it a discrete optimization problem?

I have a function 'F' which has five input variables p1,p2,p3,p4,p5. Each one of the variable from p1 to p5 can have values from the sets S1,S2,S3,S4 and S5 respectively. S1,S2,S3,S4 and S5 are ...
1
vote
2answers
40 views

Knapsack variation NP-complete

I have C processors and $C$ items that have to be run on it. I can either run each item on a seperate processor and have a running time of $\sum_{i=1}^{c} c_i$, or divide the $C$ items into $k$ ...
0
votes
1answer
40 views

Can the search space of a solvable linear optimization problem be discontinuous?

Background Say you have a traditional linear-optimization problem, there is a linear cost function, $\vec{c}\cdot\vec{x}$ and a set of linear constraints, $A_1\vec{x} \geq b_1 $ $A_2\vec{x} \leq ...
0
votes
1answer
64 views

Polyhedron's Representations and spanning the Euclidian space

Let's say you have to different representations of the same polyhedron $P\neq \emptyset$: $$P=\{x\in \mathbb{R}^n\;|\;h_i^Tx\leq c_i, i=1,...,k \} =\{x\in \mathbb{R}^n\;|\;g_j^Tx\leq d_i, j=1,...,l ...
0
votes
0answers
32 views

Finding equivalent minimization problem

I am having some trouble while implementing the minimization problem of a paper. My goal is to minimize the following: $\epsilon_L = \epsilon_1 + \lambda \epsilon_2$ where: $\epsilon_1 = \sum_i ...
2
votes
1answer
66 views

Combination Problem with mulitiple variables

I am new to this, but getting into math more and have a question regarding combinations and permutations with several variables involved. I work for a sales company and this question is based on ...
0
votes
1answer
109 views

Mathematical Induction for greedy algorithm problem?

Suppose you want to place towers along a straight road, so that every building on the road receives cellular service. Assume that a building receives cellular service if it is within one mile of a ...
0
votes
1answer
88 views

How do I optimize a function subject to a two-part constraint?

I would like to maximize the following function $$\max\; U= log(xT_o + (1-x)T_s) + log(Y)$$ by choosing levels of $T_o$, $T_s$, and $Y$, and where $x\in[0:1]$ subject to $$N = \binom{P_sT_s+Y ...
2
votes
1answer
68 views

How to maximize $\left({a+b \choose a} 2^{-a-b}\right)$?

How can you maximize $\left({a+b \choose a} 2^{-a-b}\right)$ assuming, $a,b \geq 0$ and $0< (a+b) \leq n$, where all the variables are non-negative integers? Is the maximum when $a=b=n/2$, ...
1
vote
1answer
44 views

Minimise Total $x$, Maximum $x$ or $|x|$ in integer/linear programming

Suppose we have a linear program (it may be integer, it probably doesn't matter). Suppose the variables $t_j$ give the tardiness for job $j$, and we want to minimise something to do with this ...
0
votes
0answers
23 views

Weighted partial MaxSAT (and MinSAT) with real-valued weights?

Consider the following optimization problem ($\min$-version also of interest): $$ \max_{β\in\{0,1\}^m}\{c'φ(β): ψ(β)=1\} = \max_{\phi\in\{0,1\}^n}\{c'\phi: β\in\{0,1\}^m, \phi=φ(β), ψ(β)=1\},$$ ...
1
vote
1answer
41 views

A non-linear optimization problem

I have the following optimization problem on the variables $a_1, ..., a_n$: $$ minimize \frac{\sum_{k=1}^{n}\max(k\cdot a_{k},1)}{\sum_{k=1}^{n}a_{k}} $$ $$ such\ that\ \ 0\leq a_k\leq 1\ \ \ (k=1, ...
0
votes
1answer
82 views

Simplex Algorithm

I'm currently trying to implement the (revised) Simplex Algorithm, but according to my notes the LP in standard form $\left( Ax = b, x \geq 0 \right)$ with $A \in \mathbb R^{m \times n}$ has to have ...
1
vote
0answers
234 views

Constraints of a linear programming problem

QUESTION Sandy Arledge is the program scheduling manager for WCBN‐TV. Sandy would like to plan the schedule of television shows for next Wednesday evening. Of the nine possible one‐half hour ...
6
votes
1answer
395 views

Minimum number of lines covering n points

Let there be n points in the plane. I want to know the minimum number of horizontal and vertical lines covering all the points in the plane. My initial approach started like this, 1) for each point I ...
0
votes
1answer
269 views

Variations of the transportation problem in linear programming

The transportation problem is a famous problem in linear programming. For instance, http://www.utdallas.edu/~scniu/OPRE-6201/documents/TP1-Formulation.pdf or http://www.math.ucla.edu/~tom/LP.pdf ...