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

Converting a linear-fractional program with an integer constraint to a linear program

Is it possible to convert the following linear-fractional program to a linear program ? $$ \max_x \frac{v\cdot x}{z \cdot x}\\s.t \\x_i \in \{0,1\}\\ \\ \sum_i x_i = k$$ where $v \in R^{d}$, $z \in ...
0
votes
0answers
14 views

The problem of finding a smallest spanning 2-edge-connected subgraph of a graph G is NP-hard

For a given graph G = (V, E) with weights c(e), e ∈ E, the problem of finding a smallest spanning 2-edge-connected subgraph means that one has to find a subset F ⊆ E of smallest weight c(F) ...
0
votes
0answers
6 views

How to use Support Vector Machines with Mixed data?

I have a dataset regarding student records with a mix of continuous, discrete & categorical data - the categorical data takes both nominal and ordinal forms. Ex: Continuous - GPA Ex: Discrete - ...
1
vote
0answers
17 views

What are the different ways of performing Triangular matrix-vector multiplication?

Suppose we have $$\left[\begin{array}{cccc} x_1 & 0 & 0 & 0 \\ x_2 & x_1 & 0 & 0 \\ x_3 & x_2 & x_1 & 0 \\ x_4 & x_3 & x_2 & x_1 \end{array}\right] ...
1
vote
0answers
17 views

Number of global min cuts in undirected graph

I'm looking at a proof of the following theorem "The number of global minimum cut is $\le \binom{n}{2}$". It says $\forall i$ from $1$ to $n-1$ Find min-cut seperating $\{1,2,\cdots,i\}$ from $i+1$. ...
0
votes
0answers
8 views

Submodularity definition

I am currently looking at a paper whose submodularity definition is different from whatever I thought I knew. In this paper, the authors consider a function $\Pi_2(q;a^r)$, where $q$ is composed of ...
3
votes
1answer
89 views

Discrete Linear Programming over Finite Fields?

$A$ is an $l\times m$ matrix with integer entries and each column of which contains at least one negative entry. $y$ is a column matrix with integer entries of length $l$. Define the set of sequence ...
1
vote
0answers
18 views

Minimizing mutual information using Lagrange multipliers

Im trying to follow a minimization of mutual information using Lagrange multipliers in a highly cited paper called The Information Bottleneck Method (1999), page 4: $$R(D) = \min_{p(\tilde{x}|x): ...
0
votes
0answers
53 views

Formulating shortest path (and tractable graphical model MAP) as submodular minimization

I'm trying to view maximum a posterior inference in discrete graphical model as a submodular minimization. For example, the linear chain model can be solved efficiently by the Baum-Welch algorithm. ...
1
vote
2answers
39 views

Set Covering Problem for Weighted Graph

I am looking for solution of the following problem. Let $G$ be a weighted graph with (positive) weights. The length of a path in a weighted graph is the sum of the weights of the selected edges. The ...
0
votes
0answers
9 views

Searching if a value is returned by a function defined for 2-D lattice points

Two functions $f:(x, y) \rightarrow \Bbb N$ and $g:(x, y) \rightarrow \Bbb N$ are defined where $\Bbb N$ is set of positive integers and $x, y \in \Bbb N$. Properties and relations $g(x, y) \ge ...
0
votes
0answers
19 views

selecting N integers with constraints

I need to write a program which takes 4 inputs as follows N = The number of integers to be generated ($10 <$ N $< 10000$) Start = The minimum value of the integers ($100 <$ Start) End ...
0
votes
1answer
40 views

Network flow as a linear/integer programming problem with special conditional constraints

Consider the classic network flow problem where the constraint is that the inflow to a vertex is equal to the sum of its outflows. Consider having a more specific constraint where the flow cannot be ...
7
votes
1answer
103 views

find the least natural number n such that if the set $\{1,2,…,n\}$ is arbitrarily divided into two nonintersecting subsets

Find the least natural number $n$ such that if the set $\{1,2,\dots,n\}$ is arbitrarily divided into two non intersecting subsets then one of the subsets contains three distinct numbers such that ...
1
vote
1answer
30 views

Subset of Vertices maximizing a function

I have a Digraph $G = (V, E)$ and a function $f: V \to \mathbb{R}$ and want to find $S \subseteq V$ so that $f(S)$ is maximal with the condition that if an edge $(v,w)$ exists in the Graph and $v \in ...
-4
votes
1answer
21 views

Maximize the number of oranges delivered

I have a math problem from my teacher and I can't find the answer, please help me: Tom has to deliver $n$ (Ex: $n=3000$) oranges from A to B with distance $d$ (Ex: $d=1000$) in a vehicle of capacity ...
0
votes
0answers
16 views

Multiple Choice Integer Program Special Ordered Set Naming

I have been given a problem, for which I have a hard time to find literature, since I'm unsure about the right name of the problem. The problem is defined as: We have given $k$ sets and we need to ...
0
votes
0answers
18 views

How many strings can I make with all captials letters of length 4 that have exactly 2 A's and 2 B's?

My attempt on the problem: X X X X = 26^4 number of ways the strings can be made A A X X = 26^2 number of strings with two A's in them B B X X = 26^2 number of strings with two B's in them B B A A ...
2
votes
3answers
59 views

Efficient algorithm for optimization problem.

I had an interesting interview problem today. Let's assume that we have n boxes, containing many numbers. For instance, let's say $n=4$, and four boxes contain the following numbers: ...
0
votes
0answers
13 views

Discretization of Gray Scott Model

Can someone please help me Discretizing the reaction-diffusion equation using forward-time central-space The Gray-Scott partial differential equations are given as: $$\partial u/\partial t = ...
1
vote
1answer
30 views

A variant of subset sum problem with two different sets

The original version of subset sum problem is that, given a set of integers and an integer s, does any non-empty subset sum to s ? I have a variant of this problem but on two different sets. Given ...
1
vote
1answer
26 views

Generalized Farkas Lemma

Farkas lemma can be stated as follow: If for all $\mu$ such that $\mu^T\cdot a_i \geq 0$ implies that $\mu^T\cdot b \geq 0$ then $b=\sum \lambda_i a_i$ with $\lambda_i \geq 0$ I need a generalized ...
0
votes
0answers
15 views

Converting an optimisation problem to an integer linear formulation

Is there a way to convert the following to a linear formulation? In other words, is there a workaround for the absolute value in the objective function? Minimise: ...
0
votes
0answers
12 views

Modellling a newspaper delivery route as an MILP

I am trying to model a smaller version of this problem as an Integer programming problem and I am having some issues while formulating it. Suppose there are 2 vehicles and 6 customers, and a single ...
0
votes
0answers
27 views

combination multiple 2 groups pair wise

I am trying to find the optimal solution or a way to generate an optimal arrangement in the following scenario. 12 people have lunch together twice a month. They split into 2 groups for each lunch. ...
0
votes
0answers
15 views

Does Elzinga & Hearn algorithm depend on initial points

Elzinga & Hearn is an algorithm which find the smallest enclosing circle of $n$ points in plane. I wonder is it a good idea to initialize the algorithm of Elzinga & Hearn with the two ...
0
votes
0answers
11 views

Show that there is a critical transition probability (2 discrete states)

Let $\beta$ be a fixed constant (it isn't specified that $\beta <1$, but assuming it is okay if it is necessary), and $u$ be some function from $W\to \mathbb{R}$. Let there be two discrete states, ...
0
votes
0answers
12 views

Np-hardness of a problem related to the knapsack problem

I am trying to know whether the following problem is NP-hard: Input: A positive number k and N pairs of numbers. Each pair $i$, contains the positive numbers $a_i$ and $b_i$. The problem is to ...
18
votes
2answers
228 views

Largest rectangle not touching any rock in a square field

You want to build a rectangular house with a maximal area. You are offered a square field of area 1, on which you plan to build the house. The problem is, there are $n$ rocks scattered in unknown ...
1
vote
1answer
27 views

How to set up linear programming problem for maximizing score of various combinations?

I have a sample data set that looks like this: x y w 1 1 5 1 2 1 6 2 3 1 7 3 4 2 8 4 5 2 7 5 6 3 5 6 7 4 6 7 8 4 5 8 x and ...
1
vote
0answers
46 views

Find a subset of columns to maximize the number of rows whose sum of entries in selected columns is equal or larger than a given number

Given a real m*n matrix A (m rows, n columns), a real positive number b. Each entry in A can be positive or negative. Find a subset of columns to maximize the number of rows whose sum of entries in ...
0
votes
0answers
26 views

Dual of chromatic number problem

It is well known that every linear minimization problem has a dual maximization problem. For example, the minimum vertex covering problem and the maximum matching problem are primal-dual. I am ...
0
votes
1answer
19 views

The cost function in the Weighted Bipartite Matching Problem (a.k.a the Assignment Problem)

In the definition of this problem, the weight/cost function generally takes value in $\mathbb{Z}$ (or sometimes $\mathbb{Q}$). This is what I observed from some books (e.g. "Combinatorial ...
1
vote
0answers
98 views

maximum matching to solve a path-packing problem

G=(V,E) is a directed graph. . A path packing of G is a collection of paths: $\cal{P}=\{ P_1,\dots P_k\}$ such that $V(P_i)\cap V(P_j)=\emptyset$ $\forall i,j$ s.t. $ 1<i<j<k$ where ...
1
vote
0answers
42 views

Constrained LQR with a fixed terminal state. Can MPC be applied to this problem?

I am interested in solving the constrained LQR problem with discrete finite time when the target $x$ value is given, but the final $u$ could be anything s.t. constraints. $$\text{minimize }J = ...
0
votes
0answers
22 views

Graph Theory: Modification Of Dijkstra's Algorithm

I wanted a modification of Dijkstra's Algorithm, to find the exact shortest path between any 2 vertices of a weighted graph, and not just the shortest distance. I tried the following modification: In ...
2
votes
0answers
35 views

Approximate algorithms for integer linear programming (for optimal subset selection)

I'm trying to select an optimal subset of some items. I've tried 2 optimal approaches (branch-and-bound and integer programming) but both proved impossible for the size of the problem. I'm wondering ...
0
votes
0answers
16 views

Discounted stochastic linear regulator problem with a transversality condition: I think I have a solution, need proof

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) = ...
0
votes
0answers
24 views

Maximize the product of pairwise distances between particles on a lattice

I am trying to solve the following problem : Consider an $N\times N$ square lattice ($N$ even integer, we can assume that N is large) on the complex plane, with lattice sites at position $j+ik$, $j$ ...
1
vote
1answer
96 views

How many telephone numbers that are seven digits in length have exactly five 6's?

How many phone numbers that are seven digits in length, have exactly five 6's? My attempt: {{6,6,6,6,6}{ , }} $(5(top) 5(bottom)) * (18(top) 2(bottom)) = 153$ my reasoning is that the first subset ...
2
votes
0answers
66 views

Why no Forward Dynamic Programming in stochastic case?

Dynamic programming usually works "backward" - start from the end, and arrive at the start. This works both when there is and when there isn't uncertainty in the problem (e.g. some noise in the ...
0
votes
0answers
25 views

how do I select a multiple combination of multi-level variables that meets a set of constraints (totals?)

I have left-censored, tabled survey data, random rounded to base 3, where any count of less than 6 is censored, however true 0s are included as 0. The variables, factors in statistical terms, used ...
0
votes
0answers
24 views

Is it true that there exist exactly ${k\choose n}$ bases that lead to this basic feasible solution?

Let a matrix $A=\left(A_{ij} \right)_{k\times n}$, with $A_{ij}\in\mathscr{R}$, and $$\mathrm{P}=\{ \mathtt{X}\in \mathscr{R}^n \,|\, A\mathtt{X}\ge b\}. $$ Suppose that at a particular basic ...
0
votes
1answer
33 views

Optimization of shopping list by condition

I am a computer science student that is struggling with a problem of mathematical nature. Thus far I have only studied calculus, discrete mathematics and linear algebra, but cannot figure out how to ...
0
votes
1answer
24 views

Optimization of a colour graph

Formulate as a discrete optimization problem: Label each node of the graph with a different non negative integer number, in such a way that the numbers of the nodes of each path composed of the same ...
0
votes
0answers
21 views

Maximize number of bins and minimize cost of elements chosen from a set

I am considering the following problem: there is a set of elements $S$ where each element is assigned to a bin $B$. The bins are disjoint and their union is $S$. There is also a cost function ...
0
votes
0answers
14 views

Convexity of a function with discrete parameters

Let $k\in\mathbb N_{>0}$, $n_1,\dots,n_k\in\mathbb N_{>0}$ and $N=\sum_{i=1}^kn_i$. I would like to know if the following function is convex: $$ r_{\alpha,\theta}(Z) = ...
0
votes
2answers
39 views

Why is an affine set convex?

I wanted to know why do we say that an affine set is convex? From what I understood, if we take two points $x_1$ and $x_2$ $\in \mathbb{R}$, then, the affine set $A$ defined by these two points will ...
0
votes
0answers
30 views

How to obtain the best fit?

I have a complex function say $f(x,a,b,c)$ where $x$ is variable and $a,b,c$ are the parameters. Parameters $a,b$ are linked as $d = (1/a^2) - (i*pi/b)$. The limits of x is very small say -0.02 to ...
0
votes
0answers
11 views

Approximate matrix partition

This problem is similar to the Optimizing sums of log det problem that I had asked earlier, but it is not the same. I have matrix $H$, which has columns $h_1, \ldots, h_n$. I want to partition the ...