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

Pseudo-Boolean functions restricted to integers

The Pseudo-Boolean functions are of the following form. $$ f : \mathbb{B}^n \to \mathbb{R} $$ I would like to know if there is a special sub-category of $$ f : \mathbb{B}^n \to \mathbb{Z} $$ with ...
0
votes
0answers
18 views

Linear integer programming

I am trying to find the optimal solution for the following linear integer programming: \begin{eqnarray} &&\underset{x_i, \forall i} {\text{maximize}} ~ \sum_{i=1}^N x_i a_i \\ && ...
0
votes
0answers
27 views

What are the steps to optimize simple Sphere function

I am new to optimization. How can one optimize the simple test function, Sphere function available on https://en.wikipedia.org/wiki/Test_functions_for_optimization?
0
votes
0answers
18 views

Quadratization of $5 x_1 x_2 − 7 x_1 x_2 x_3 x_4 + 2 x_1 x_2 x_3 x_5$ using Rosenberg's algorithm

In section 4.4 of Pseudo-Boolean Optimization by Boros et al., the authors have reproduced Rosenberg's quadratization algorithm as follows. Then they have given an example of implementing the ...
0
votes
1answer
23 views

Let $n_1e, n_2e,\ldots,n_ke$ be k numbers, find $e$ if $n_i\in\mathbb{Z}^+$

I have measured a quantized (or discrete) physical quantity. This means that there exists a fundamental quantity $e$ such that the physical quantity is an integer $n$ times the fundamental quantity ...
0
votes
0answers
8 views

Convert the Matching Polytope LP to Dual Program

For my course in discrete optimization I am studying about Polytopes and their dual programms. They state that the convex hull of Perfect Matchings in grahph $G=(V,E)$ is given by: $$ x\geq 0\\ ...
0
votes
0answers
6 views

Going from discrete solution to continuous solution (Dynamic Programming/Optimal Control)?

Suppose I have a discrete solution for a dynamic programming problem and an optimal control policy. If I can make the control policy continuous, by taking the limit as t-> 0, is that control policy ...
0
votes
2answers
29 views

log modular function whether supermodular or submodular

I have a modular function defined as $$g(X) = \sum_{i \in X} x_i, \quad\text{s.t. } x_i \geq 0$$ Now, I define a function $$f(X) = \exp(-g(X))$$ As I worked out, this function $f$ is submodular, ...
0
votes
0answers
12 views

Which are the alternative approaches to stochastic (online) gradient descend for online optimization?

I'm looking for some alternative approaches to online\stochastic gradient descent for online optimization such that 1) there exists some proof about the convergence of the parameters to some compact ...
0
votes
0answers
13 views

How to solve a multiple knapsack problem?

I have the following binary LP max $\sum_{l=1}^{L}\sum_{f=1}^{F}[S_{f} \sum_{k=1}^{K}a_{kl}b_{kf}]x_{lf}$ s.t $\quad 1)\quad \sum_{f=1}^{F}x_{lf}S_{f}\leq C_{l} \quad \forall l$ $\quad 2)\quad ...
0
votes
1answer
45 views

How to solve a binary LP.

I have the optimization problem given below max $\sum_{i=1}^{N}\sum_{j=1}^{M} x_{ij}R_{ij}$ s.t $\quad 1)\quad \sum_{j=1}^{M} x_{ij}=1 \quad \forall i$ $\quad 2)\quad x_{ij} \in {0,1}$ $\quad ...
1
vote
1answer
50 views

Required conditions for product of two submodular functions to be submodular?

3.32 of Boyd's Convex Optimization book says: Products and ratios of convex functions. In general the product or ratio of two convex functions is not convex. However, there are some results that ...
0
votes
0answers
5 views

Minimizing percentiles of discrete distribution

I have a vector $\vec{v} \in \mathbb{R}^n$ and a matrix $A \in \mathbb{R}^{n \times m}$. For any $\vec{x} \in \mathbb{R}^m$, the vector $\vec{v} + A\vec{x} \in \mathbb{R}^n$ represents a discrete ...
1
vote
1answer
48 views

Ratio of two submodular functions is submodular?

Say we had 3 submodular functions $f(X)$, $g(X)$ and $h(X)$ is $\frac{f(X)}{g(X). h(X)}$ submodular as well? What can be said about the submodularity of $\frac{f(X)}{g(X)}$ and $f(X).g(X)$? I ...
3
votes
1answer
27 views

Nonlinear integer programming problem

I am trying to maximize the following function $$ f(m,n) = \frac{m \log 3 + n \log 2}{\sqrt{m^2+n^2}} $$ where $ n $ and $ m $ are integers, not both $ = 0 $, although one could be $ 0 $. This is ...
2
votes
0answers
36 views

How many combinations of 5 balls from 16 balls can you have in which the numbers on the balls are distinct?

We have $8$ blue balls that are numbered $\{1,2,3,4,5,6,7,8\}$. We have $8$ red balls that are numbered $\{1,2,3,4,5,6,7,8\}$. I think it should be ${8 \choose 5}\cdot 2^5$. There ${8 \choose 5}$ is ...
0
votes
0answers
9 views

Control zone and moat lower bound for the Euclidean traveling salesman problem

By using control zone and moat, we can obtain a lower bound for the TSP, which means that we cannot find such a tour with cost less than the value of control zones and moats. In Euclidean TSP, is ...
0
votes
2answers
48 views

Production optimization - what type of problem?

I want to make an algorithm that distributes orders $O_1,O_2,\dots$ to equipment $E^1,E^2,\dots$ so they can be processed in an optimal way. Different orders require different equipment for the ...
2
votes
0answers
26 views

Discrete Optimization Problem (VRP)

Consider the following setting : We have two pickup nodes (a) and (b)and two delivery nodes (c) and (d). At each pickup node, there are entities to be picked up and delivered by cars (n cars) to ...
2
votes
1answer
39 views

combinatorial optimization - argmax binary vector

I have the following combinatorial optimization problem: $$ \arg\max_{\mathbf{x}} \frac{\alpha + \mathbf{t}\cdot\mathbf{x}}{\beta + \mathbf{f}\cdot\mathbf{x}} $$ where the objective is to find the $n$ ...
1
vote
0answers
27 views

2 dimensional packing Problem with flexible objects

I have a kind of bin packing problem defined as follows: given: m bins $b_1,...,b_m$ of height $h_1,....,h_m$ and width w. The packing objects simply map $1,...,w$ to integers, hence these are ...
1
vote
0answers
11 views

Difference between submodular polyhedron and base polyhedron

Can anyone tell me the difference between base polyhedron and submodular polyhedron of a submodular function $f$ defined over base set $V$ ?. According to the definition, the base polyhedron is same ...
0
votes
0answers
24 views

How can I find a maximum matching?

I have a problem that I was able to conceptualize as following: Suppose that there are n groups of agents A1, A2, …, An. Group Ai contains Ki agents where Ki is an integer between, say, 1 and 10. ...
0
votes
0answers
28 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
16 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
1answer
13 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
21 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
20 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$. ...
3
votes
1answer
105 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
22 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
57 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
42 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
10 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
52 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
104 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
31 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
27 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
21 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
65 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: ...
1
vote
1answer
41 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
33 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
16 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
13 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
30 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
18 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
13 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
13 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
250 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 ...