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

6
votes
1answer
44 views

Is this set of random variables a Hilbert space?

Consider a sequence of i.i.d. random variables $\left\{ {{\varepsilon _t}} \right\}_{t = 1}^\infty $ with $E\left( {{\varepsilon _t}} \right) = 0$ and $E\left( {\varepsilon _t^2} \right) = {\sigma ...
2
votes
0answers
45 views

Is this (funny) combinatorial optimization problem NP-hard ? (cutting numbers and placing them in urns)

The parameters of the problem are $m$ numbers which are integers (these numbers are denoted $b_i$), $n$ urns and in each urn, we can place $C$ numbers. We assume $nC \geq m$ so that the problem is ...
1
vote
1answer
18 views

How to derive formula for marginal probability of choosing nest in nested logit model?

I am trying to understand all the details of the nested logit and what confuses me is the formula for marginal probability of choosing the nest. In more details: the joint probability of individual n ...
1
vote
1answer
29 views

Probabilistic dynamic programming question

A gambler has 2 dollars. He is allowed to play a game four times and his goal is to maximize his probability of ending with at least 6 dollars . If the gambler bets $b$ dollars then with ...
3
votes
1answer
35 views

Dynamic programming recursion

In a book by Wayne Winston for operations research I found this question. Here's how I did it: Let $t$ be the no.of subjects to pass and let h be the no.of hours she has in hand for studying. ...
1
vote
1answer
198 views

What kind of a problem is this?

The problem can be stated as: I have $m$ liquids ($A_i$ is the amount of the $i$-th liquid) and $n$ tanks ($x_j$ is the volume of the $j$-th tank), and the task is to find the best way to ...
0
votes
1answer
16 views

Frobenius norm optimization

I need to minimize the Frobenius norm of (A-k*B) by finding appropriate value for k. min (norm(A-k*B),'fro') In this question A and B are m*n known matrices. We know that ...
1
vote
2answers
16 views

Elements that always stay together in multiple sets

I have a problem that I have encountered a number of times in practice, and I'm curious if there is a formal name for it so I can look for other people's solutions (I wrote an algorithm to solve it, ...
4
votes
1answer
82 views

Algorithm to find shortest path to net values across nodes

I have an undirected graph $G = (V, E)$ with nodes $V$ and edges $E$. Each node $v$ has an associated number $n_v \in \mathbf{Z}$ Let us define for any two nodes $v, w \in V$ connected by an edge $e ...
1
vote
1answer
20 views

Numbers written into a square grid

I was working on a problem from The Art and Craft of Problem Solving by Zietz, in the chapter called 'The extreme principle.' Here is the problem: "The integers from 1 to $n^2$ are written into a ...
0
votes
0answers
26 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 ...
0
votes
0answers
49 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
55 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
27 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
116 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
20 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
19 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
12 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
24 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
19 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
27 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
31 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
19 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
38 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
20 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
48 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
9 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
67 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
53 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
23 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
51 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
21 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
61 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
55 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
40 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
12 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 ...
3
votes
0answers
42 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
49 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
61 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
58 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
51 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 ...