Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [discrete-optimization]

For questions about discrete optimization, which is a branch of optimization with discrete variables, opposed to continuous optimization in applied mathematics and computer science.

0
votes
1answer
28 views

Scheduling Problem

My boss asked me to come up with a presentation that recommends how many hires she would need to support our tests. I have data that shows the number of tests per day. Assuming one worker per test, ...
0
votes
0answers
23 views

How to cut rope effectively using the least number of connector?

So I am given a rope cutting problem. I have 6m rope length for 38 pieces I have 12 m rope length for 17 pieces. The buyer want me to cut the rope for a specific length 6 m rope for 38 pieces And ...
6
votes
2answers
228 views

Find Maximum of any discrete function (not necessarily a PDF)

How can we find the maximum of any discrete function, say $$ f(n)=\frac{(n+1)^2}{2^n},\quad n\in \mathbb{N} $$ that is not the PDF of any distribution? (This query is unrelated to statistics.) By ...
0
votes
0answers
14 views

Choosing an optimal partition

We have a finite list of length $N$ of positive integers, $$B=[b_1,b_2,b_3,...,b_N]$$ We partition this list into three sublists by choosing two points of division: $p,q \in \mathbb{N} $ such that $1&...
1
vote
1answer
31 views

How is this dual function derived?

Say we have primal problem: $$\begin{array}{ll} \text{minimize} & c^T x\\ \text{subject to} & Ax \le b\\ & x_i (1-x_i) = 0, \quad i \in [n]\end{array}$$ where $\le$ means component-wise ...
0
votes
1answer
37 views

Optimization over a binary (or discrete) variable

I have the equation $y=Kx$ where, for example, $x=\begin{pmatrix} x_1 \\ \vdots \\ x_{50} \end{pmatrix}$, where $x_i=0$ or $1$ $K \in M _{1000,50}(\mathbb R)$ a given constant matrix and $$y=\begin{...
-1
votes
2answers
57 views

How to write the optimization constraint of the following problem

$A$ is an adjacency matrix and $W$ is the weight matrix. So the problem is to find the maximum matching, such that for those nodes are connected, the weight between them is limited by $d$, which $W_{...
0
votes
1answer
40 views

Real division with arbitrary-precision discrete integers, how to?

I need a reliable arbitrary-precision division of discrete real numbers (ℝ), using arbitrary-precision discrete integers (ℤ). It is a classic problem, but it is not easy to verify the good solutions ...
0
votes
1answer
33 views

Coding for data compression with large target's symbol set (where the target symbol set is larger than the source symbol set)

For data compression, every codding that I've seen is binary. It means we convert a language with $N$ symbol size to a language with $M=2$ symbol size. For example, in Huffman coding, the goal is to ...
0
votes
0answers
9 views

The balanced k− partitioning problem : how to design testbeds to compare different metaheuristics methods?

I implemented different search metaheuristics methods (local search, Tabu search, and simulated annealing) on the problem of partitioning a non-oriented weighted graph' vertices into k parts of nearly ...
0
votes
0answers
18 views

Addition chain with two sub-optimal sub-addition chains

An addition chain is a finite sequence of positive integers that starts at $1$, so that any element of the sequence is a sum of two previous elements. That is, it is a sequence $(a_1, \ldots, a_k)$ ...
0
votes
0answers
13 views

Permutative Constraint on Image Approximation

Motivation I am trying to explore the idea of constraining the approximation of an image represented by an $m$-by-$n$ matrix $A$ by the values on a linearly-spaced interval of $mn$ elements $L$ ...
1
vote
1answer
42 views

Correctness of integer reformulation in the FICO MIP quick reference

I have stumbled upon an industry quick reference for MIP formulation by FICO: However, after checking their writing on section 2.3 Maximum value. It seem that there are problems with their ...
1
vote
1answer
43 views

Reformulation of a Mix Integer Programming problem with both if else and min max logical constraints

I am quite new to the field of discrete optimization and currently having problem formulating the system below. This system contain both if-elseif statement and a difficult to linearize min-max ...
4
votes
0answers
53 views

Maximal determinants of zero-one matrices

Is it possible to find the maximal determinant of matrices in $\{0,1\}^{n \times n}$? If so, what do matrices with maximal determinant look like? For example, when $n=3$, it's not hard to see that ...
0
votes
0answers
33 views

What is the difference between Integer Quadratic Programming versus Mixed Integer Quadratic Programming?

I am new to the optimization problem of Quadratic programming. In equation $8$ of this paper, there is an equation: $$\min \operatorname{cost} (x) = x' H x +c' H x \quad \text{subject to,} \tag{8} ...
0
votes
0answers
14 views

Algorithms to define “magnet” values to be used as y-grid ticks in stock market prices

I am writing a program which plots currency and stock market asset rates. For each plot, I will have a minimum and a maximum price for the covered period. Those minimum and maximum prices can be for ...
0
votes
0answers
24 views

How to reformulate (or model differently) the sum of fractions in the objective of integer program?

I have the following (integer) program: $ \max \sum_{i\in I} \frac{a_i}{b_i + \sum_{j\in J} c_{ij} x_{ij}} $ s.t. $ x \in X $ $ x_{ij}\in \{0,1\}, \quad\forall i\in I \wedge j\in J $, where $ a_i ...
2
votes
1answer
41 views

Open Travelling Salesman Problem

I am trying to find a linear program for the open Travelling Salesman Problem, where the salesman does not need to return to the starting point. More precisely, I have to do this with multiple ...
1
vote
0answers
14 views

Inner and outer linearization

Why are Dantzig-Wolfe and Benders decomposition referred to as inner and outer linearization respectively? I am a newbie in Mathematical Programming and optimization and came across these terms while ...
0
votes
0answers
50 views

arrange the functions in increasing order of growth rate

I am supposed to arrange the functions into increasing order of growth rates. $$3^n, 2^n, n2^n, n^{30}, (\log n)^3, \sqrt{n}\log^2 n, n\log n, \sqrt{n!}, n^{29}+n^{27}, n^{2\sqrt{n}}$$ I came up ...
9
votes
4answers
1k views

$100$ birds in $21$ cages each with $≤ 10$, with least cages having $≥ 4$ birds?

A bird cage could only fit a maximum of $10$ birds. If a house has $21$ bird cage and $100$ birds. A bird cage is considered overpopulated if it fits $4$ or more birds inside it. How many cages (...
0
votes
1answer
27 views

What type of optimization problem is this? Ride sharing?

I am given source containers $s_1,s_2, \dots, s_n$, products $p_1, p_2, \dots, p_m$ and an assignment of which container needs to be used to make a certain product, which I represent as follows \...
10
votes
3answers
193 views

We have $n$ charged and $n$ uncharged batteries and a radio which needs two charged batteries to work.

We have $n$ charged and $n$ uncharged batteries and a radio which needs two charged batteries to work. Suppose we don't know which batteries are charged and which ones are uncharged. Find the least ...
1
vote
1answer
71 views

$A_1,A_2,…,A_k\subseteq \{1,2,…,11\}$ are such that for any three of them at least two are not comparable by inclusion. What is a maximum of $k$?

Say $A_1,A_2,...,A_k\subseteq \{1,2,...,11\}$ are such a distinct sets that for any three of them at least two are not comparable by inclusion. What is a maximum of $k$? I'v got idea for this problem ...
1
vote
0answers
32 views

Maximum number of triangles given fixed number of edges

Consider all graphs with E many edges. The question is to find the maximum number of triangles such a graph can have. The answer is $O(E^{1.5})$ and the maximum occurs with it’s a clique. Now my ...
1
vote
1answer
48 views

Selecting elements from overlapping sets in any order without repetition

(there are examples below in this question, which probably explain it all better) Consider a finite set $R = \{1, 2, ..., N\}$ and a tuple of sets $Q = (S_1, S_2, ..., S_M)$, which are possibly non-...
0
votes
1answer
109 views

How to solve the following combinatorial optimization problem?

Is there some efficient method to solve the following optimization problem? If $x_i$ is in a continuous set, is there some efficient method? Thanks. $\min$ $x_1+x_2+\dots+x_n$ subject to: $a_1\log ...
6
votes
1answer
45 views

Minimum number of rectangles to cover diagonal-free grid

I'm trying to figure out the minimum number of rectangles required to cover an $n \times n$ grid, minus the diagonal. What this is means is the following: Suppose we have an $n \times n$ grid, with ...
1
vote
2answers
48 views

Finding Lowest Elevation Path Between Two Points

Let's say I have a matrix of values that represent heights with function $f(x,y)$ and I am trying to find the "lowest value path" beween two points. So this would be the reverse of hill climbing, as ...
0
votes
1answer
26 views

Given $n$ vectors, find partitions with closest centroids

Given vectors $a_1, \dots, a_n\in \mathbb R^d$ where $n$ is even, I want to find partitions $I$ and $J$ of $[n]$ with $|I|=|J|=\frac n2$ to minimize $$\left\| \sum_{i\in I} a_i - \sum_{j\in J} a_j \...
0
votes
1answer
22 views

How to proceed when you have an invalid range in a sum?

this is my very first post here. I think this might be a really stupid question (sorry), but I just need to guarantee it. I have the following equation: $$F_i = \min_{i \ \leq \ j \ \leq \ q} \{\sum_{...
0
votes
0answers
18 views

Expensive combinatorial optimization of choice of subset from a large finite space

I have a fairly general question -- what's a good (gradient-free) approach to optimizing an expensive function whose input is a choice of subset from a large finite population? That is, I have a set ...
0
votes
0answers
24 views

Binary Polymatroid Optimization Problem

Let $\mathcal{N}$ denote the finite set $\{1, 2, \ldots, n\}$, and let $\mathcal{S}_j$ denote the set $\{1, 2, \ldots, j\}$; let $f\colon \mathcal{N} \to \mathbb{N}$ be nondecreasing, submodular and ...
0
votes
0answers
22 views

Infimum of $f(\theta)= -\sum_{i=1}^n (y_i - \alpha p(y_i|x;\theta)) \ln p(y_i|x) $

Suppose $y_1 = 1, y_2 = y_3 = ...=y_n = 0\ (n\geq2)$, and $\sum_{i=1}^np(y_i|x;\theta) = 1$, $0\leq p(y_i|x;\theta)\leq1$. Meanwhile $\alpha > 0$ is a constant. Let's define a function $$f(\theta)...
0
votes
1answer
44 views

Approximate function by stacking building blocks

I need some help with a 'generalised Lego problem': Given a function $f(x)\geq 0$ on an interval $[a,b]$, and a 'building block' function $p(x)\geq 0$ with compact support. The maximum of f shall be ...
1
vote
0answers
27 views

When are quadratic integer programs easy to solve? [duplicate]

Let $N_i=\{0,1,\dots,\bar{n}_i\}$ and define $N=N_1\times \dots \times N_I$. I want to maximize $f$ on $N$. $f$ has the following form $$ f(n) = \sum_i A_i n_i -\sum_i \sum_{j\neq i} B_{ij} (n_i-n_j)^...
0
votes
0answers
12 views

Deconvolution of accumulated values

Introduction I have an unknown function of time $f(t)$ that I would like to learn based on experimental observations. I have an observable $g(t)$, which, to the best of my knowledge, is given by the ...
2
votes
2answers
58 views

Minimum distance between sequence a and all permutations of another sequence b

Let $a$ and $b$ be finite sequences of length $n$, i.e. $a=(a_1,a_2,...,a_n), b=(b_1,b_2,...,b_n)$. I want to calculate the minimum of the distances (in an Lp norm) between $a$ and all permutations of ...
0
votes
0answers
21 views

Maximum weight matching with repeated nodes

We are given two sets of nodes $A$ and $B$ forming a graph where each element $x \in A$ can be connected with an element $y \in B$ with different possible weights. The graph can be explained in two ...
1
vote
0answers
16 views

Finding discrete solutions to inequality involving Exponential Integral

I want to identify the least natural number $n$ (of course, it suffices to solve this problem for the reals, and then take the floor) such that $$-c \text{Ei}\left(-e^{\frac{a-d}{c}} (n+1)\right)+a-...
0
votes
1answer
26 views

Count the number of unique elements in a vector by linear constraints (ILP)

Let $\mathbf{x}\in \{0,1\}^n$, be the objective variables of an ILP. Further, let $\mathbf{a} \in \mathbb{N}_{\geq 0}^n$ be a given random vector and $\mathbf{w} = \mathbf{x} \odot \mathbf{a}$ where ...
0
votes
0answers
19 views

Property of submodular non-decreasing function

Let $f:\mathcal{P}(N) \longrightarrow \mathbb{R}$ be a set function. $f$ is submodular if \begin{align} f(A) + f(B) &\geq f(A \cup B) + f(A \cap B) &\text{for all } A, B \in \mathcal{P}(N), \...
0
votes
0answers
12 views

Bus fleet requirement for transporting passengers/baggage between airport terminals

I am trying to determine the optimum number of buses required for loading and unloading of passengers/baggage. The buses perform following tasks: Transport terminating passengers and their carry on ...
0
votes
1answer
21 views

Ordering tours in a Euclidean TSP according to (strictly) increasing length

Let $H$ be the set of all Hamiltonian cycles on the complete graph $K_n$ associated with a set of $n \geq 4$ points $P$ in the plane where edge weights are defined using the Euclidean distance between ...
1
vote
0answers
43 views

How to find a spanning tree?

The question is: Describe how you can find a spanning tree for which (a) the product of the edge-costs is minimal (b) the maximum of the edge-costs is minimal Somebody has told me to use ...
0
votes
0answers
20 views

Is it possible to turn this into a (standard) integer convex knapsack problem?

I have found a solution algorithm for integer knapsack problems of the following form: $\max\limits_{x_j \in [l_j,u_j]} \sum_{j=1}^n f_j(x_j)$ such that $\sum_{j=1}^n g_j(x_j) \leq b$ ...
1
vote
0answers
30 views

Solving motion equations using linear programming

I'm trying to solve this physics problem using the Simplex method $$\text{Minimize}\qquad \int _0 ^T |f(t)|dt \qquad \text{subject to}\\ j(t) = j(0) + \int_0^t f(t)dt, \forall t \in [0,T] \\ m(t) = m(...
0
votes
1answer
24 views

Searching Solver for a convex seperable Integer programm

I have given a problem of the form $\min \sum_{j=1}^n f_j(x_j)$, s.t. $\sum_{j=1}^n g_j(x_j) \leq b$. Both the $g_j$ and $f_j$ are convex functions and $x_j$ are integer, so its a convex seperable ...
0
votes
0answers
33 views

Production time optimization model

I have a problem where I have 2 different types of raw-material. These materials can be processed in two different production-lines which take different amount of time, depending on raw material. ...