The tag has no wiki summary.

learn more… | top users | synonyms

0
votes
1answer
10 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
12 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
18 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
31 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
11 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
35 views

About Recurrence Relations.

I need help in order to solve the following question, Here RR is for Recurrence Relations.
1
vote
0answers
38 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
16 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
39 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
40 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
27 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
20 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
111 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)$ ...
1
vote
0answers
10 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
32 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
31 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
33 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
20 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
57 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
62 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
81 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$, ...
0
votes
0answers
24 views

About the maximum number of pairwise arc-disjont $s − t$ paths in simple directed graph?

Let $D = (V, A)$ be a simple directed graph and let $s, t \in V$ . Let $a$ be the minimum length of an $s − t$ path. Show that the maximum number of pairwise arc-disjont $s − t$ paths is at most ...
1
vote
1answer
38 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
21 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
33 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
76 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
159 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
269 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
235 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 ...
3
votes
1answer
146 views

Dividing a set of points into two sets of roughly equal diameter

Let $S$ be a finite set whose cardinality is more than 1 and $d: S\times S\rightarrow\mathbb R$ be a positive symmetric function (that is, $d$ is a distance without the axiom of triangle inequality). ...
0
votes
1answer
46 views

Checking whether a solution to MIP is optimal

Consider a binary integer program \begin{align} \min \quad &\sum _{j \in J}f_j x_j +\sum _{i \in I} c_i y_i \notag \\ \mbox{s.t.} \quad &\sum _{j \in N_i} x_j \ge 1-y_i, \quad \forall i\in I ...
4
votes
2answers
54 views

What is an approach for optimizing the values of a matrix?

My apologies if I get some terminology wrong, I don't have a formal math background; half my problem is articulating what I'm trying to do and identifying the domain of math that deals with this kind ...
0
votes
0answers
48 views

Is there an easy solution to this constrained discrete minimisation?

Given $\vec{a}$, $\vec{b}$, and $c$ I want to find a discrete combination $\vec{n}$ (i.e. a vector with non-negative integer elements) to $$\mathrm{minimise}\left(\vec{n}\cdot\vec{a}\right)$$ Under ...
0
votes
1answer
48 views

Optimising profit in responding to offers of customers

I have an linear algebra problem to solve. Currently I have n number of customer lists and m number of offers. I have matrix (P) with dimension m x n. Elements of P indicates probability of ...
0
votes
1answer
105 views

How to solve this minimization (maximization)?

I'm facing this problem: $$ \large \min_{x \in \mathbb{R}_+^3} \max \left\{ { \sum_{i=1}^3 x_i^2-2 x_1 x_3 \over \left(\sum_{i=1}^3 x_i \right)^2} , { \sum_{i=1}^3 x_i^2 + 2 (x_1 x_3 - ...
6
votes
2answers
303 views

How can I, as a future mathematician, contribute most to Smart Grid research?

After I've finished my Master's degree in mathematics, I too want to use my powers for good. One endeavour I consider good is the pursuit of the design and implementation of a Smart Grid which will, ...
2
votes
1answer
172 views

Proof by Contradiction: $100$ Balls & $9$ Boxes

Show, by giving a proof by contradiction, that if $100$ balls are placed in nine boxes, some box contains 12 or more balls. I would like to ask for a hint for this quesiton. Thank you.
1
vote
2answers
63 views

When $\min_{x \in X,y \in Y} f(x,y) = \min_{x \in X} \min_{y \in Y} f(x,y)$?

When $$ \min_{x \in X,y \in Y} f(x,y) = \min_{x \in X} \min_{y \in Y} f(x,y) \qquad? $$ I mean when we are minimizing a function with respect to two variables, under what conditions we are allowed to ...
1
vote
0answers
93 views

Why these two problems lead to same answers?

Suppose these two problems: Problem 1: $$\min_{X,P} \quad\max_{1\leq l\leq L-1} \quad {|\sum_{1\leq i\leq N_p}^{N_p}x_ie^{\frac{2\pi l}{N}p_i}| \over {\sum_{i=1}^{N_p} x_i^2}} \quad \equiv \quad ...
2
votes
0answers
56 views

Quadratic Integer Programming

Would anyone mind helping me solve this problem $$ \min\space f(x) = \frac12 x^\mathrm TQx + bx + c \qquad \text{s.t. } \sum_i x_i=\lambda $$ where $x$ is a vector whose entries are positive ...
2
votes
1answer
250 views

Maximum number of pairwise intersections

Let $[n]=\{1,2,\ldots,n\}$ and let $S$ consist of subsets of $[n]$ of cardinality $2$. I would like to find the maximum number of pairwise intersections that $k$ distinct elements from $S$ can have. ...
2
votes
0answers
70 views

How to define an objective function that conveys the concept of selecting the best elements in a set

Consider a set of tasks $\mathcal{T} = \{t_1, \ldots, t_I\}$. Consider also a set of workers $\mathcal{W} = \{w^1, \ldots, w^J\}$, where each worker $w^j \in \mathcal{W}$ is associated with a value ...
1
vote
1answer
185 views

Solving a constrained Lagrangian dual problem

Consider the following $\max-\min$ integer programming formulation expressed in the binary decision variable $\mathbf{z}$: $$\begin{align*} \max&m \\ s.t.&\\ m \leq& s_i + \sum_j^J ...
2
votes
1answer
155 views

minimum lines, maximum points

There are $P$ points in the 2-dimensional plane. Through each point, we draw two orthogonal lines: one horizontal (parallel to x axis), one vertical (parallel to y axis). Obviously, some of these ...
2
votes
1answer
46 views

Repeatedly assigning people to subgroups so everyone knows each other

Say a teach divides his students into subgroups once every class. The profile of subgroup sizes is the same everyday (e.g. with 28 students it might be always 8 groups of 3 and 1 group of 4). How can ...
23
votes
4answers
489 views

square cake with raisins

Alice bakes a square cake, with $n$ raisins (= points). Bob cuts $p$ square pieces. They are axis-aligned, interior-disjoint, and each piece must contain at least $2$ raisins. Note that a single ...
1
vote
1answer
59 views

Is there an explicit solution to: $\arg \min mn : mn \geq k, l_0 \leq n \leq l_1$?

Is there an explicit solution or a fast algorithm to compute: $$\underset{(m, \ n) \in \mathbb{N}_{+}^2}{\arg \min} \ mn \ : \ mn \geq k,\ l_0 \leq n \leq l_1$$ for given constants $k, l_0, l_1 \in ...
1
vote
0answers
84 views

Which cut does the “minimum cut” refer to?

My course notes give the following definitions; could someone please verify that the last definition is non-standard? (I've spent all evening googling, and isn't "minimum cut" a concept related to cut ...
2
votes
0answers
132 views

Are edge cuts, vertex cuts, and cut sets all variously called “cuts”?

I've seen "cut" being used to refer to all three, in different places, and sometimes in the same book. Which does "cut" most commonly refer to? p.s. I am aware that "cut" itself can be defined to ...