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.

Filter by
Sorted by
Tagged with
0
votes
0answers
19 views

Min cost max flow optimization problem

Let $I$ be the set of customers and let $J_i \subseteq J$ be the set of items from which customer $i \in I$ wants to buy only one, where $J$ are the items. Denote $w(i,j) \geq 0$ as the price customer ...
0
votes
0answers
9 views

Create MST by removing maximum weight edges in all cycles?

Let G be an undirected graph with distinct positive weights. Is it possible to create a minimum spanning tree by just finding all the cycles in G and removing the edges with the maximum weights in ...
2
votes
1answer
11 views

Maximize number of edges in a directed graph with vertex degrees bounded by one

Given a finite simple directed graph $G = (V, A)$, I am looking for a subgraph $G' = (V', A')$ of $G$ such that, for each vertex $v'$ of $V'$, the in-degree and the out-degree of $v'$ are at most one, ...
0
votes
1answer
27 views

split a number sequence into balanced groups [closed]

Given a sequence of real numbers, ${a_1,a_2,...,a_n}$, I want to split them into $\textbf{m}$ groups ($\textbf{m}$ is fixed and $m<n$). If the sum of each group is termed as $s_j$, how to setup the ...
0
votes
1answer
44 views

Knapsack, but divided by summation

For a given set $S = \{1, 2, ... , N \}$, each component $i\in S$ can be represented by $(a_i, b_i, c_i, w_i)$. Is there any technique for solving the following problem? $$\max_{S' \subseteq S} \frac{ ...
0
votes
0answers
19 views

Graph Theory: An inequality revolving about arborescences

I am stuck at the following exercise: Let $G = (V,E)$ be a directed graph with weight function $c$ sucht that every node is reachable from vertex $s \in V$. Let further be $A_S$ be the $G$-spanning ...
0
votes
2answers
26 views

Algorithm to find number of babysitters in $O(n)$ time

I want to hire a babysitter to watch over my baby 24 hours a day. I've gotten $n$ responses. Assume that all 24 hours can be covered. A babysitter is willing to work any part or parts of their ...
0
votes
1answer
23 views

NP hard (like KNAPSACK)- any approximation scheme?

For a given set $S = \{1, 2, ... , N \}$, each component $i\in S$ can be represented by a triple $(a_i, b_i, c_i)$. How can the following be solved? Any polynomial time algorithm exists? $$\max_{S' \...
0
votes
1answer
22 views

Solving linear programming problems with consecutive 1s in restriction matrix.

Let $A \in \{0, 1\}^{m \times n}$ be a matrix with consecutive ones in either the rows or columns. Then apparently solving an linear programming problem of the form ...
0
votes
0answers
24 views

Maximisation subject to an integer constraint

I am trying to solve an unconstrained maximisation problem. The objective function is quadratic in the (single) choice variable. Annoyingly, the choice variable must be an integer. Is there some ...
2
votes
1answer
24 views

strategy to find all spanning trees of a given weight

Given a graph and its weight function, is there a general strategy to compute all of its spanning trees of a given weight? Maybe we can write a program to sort out all the combinations of edges which ...
0
votes
2answers
66 views

Find minimum $n$ that satisfies $\frac{1}{a_1}+\frac{1}{a_2}+\cdots+\frac{1}{a_n}=\frac{12}{13}$

From the test: We have the following equation: \begin{equation} \frac{1}{a_1}+\frac{1}{a_2}+\cdots+\frac{1}{a_n}=\frac{12}{13} \end{equation} where $a_i$ are distinct natural numbers not equal to $13$....
4
votes
2answers
60 views

Find minimum number of figures needed , so that no additional figure can be added?

I have a $6\times 12 $ rectangle, which I need to fill by the following figure: What is the minimum number of figures I need to use, so that no additional figure can be added? The figure can be ...
0
votes
0answers
28 views

How to solve $\mathop{max}_\limits{F} \ Tr(F^TAF)$, where $A=A^T$, $F \in \Bbb \{1, 0\}^{n \times c}$ is an indicator matrix?

For indicator matrix $F$, each row of $F$ has only one 1 and each column of $F$ has at least one 1. An example in python is as follow ...
0
votes
1answer
20 views

What is the definition of “augmenting path capacity”?

I am reading the text "Combinatorial Optimization: Networks and Matroids" by Eugene Lawler. Notation/Definitions: \begin{align} s, \quad &\text{source vertex} \\ t, \quad &\text{sink ...
1
vote
0answers
16 views

VRP with multiple locations for the same customer?

I am looking into the vehicle routing problem, and am looking for a specific case where a vehicle can visit a costumer at multiple locations, the vehicle only have to visit one of the locations. Does ...
1
vote
0answers
27 views

Minimize function over discrete set

I want to solve the following optimization problem where $1 \leq p \leq n, p \in \mathbb{N}$ and $c_i \in \mathbb{R}$. How can I derive a closed form solution? My approach is to relax the set $\{-1,0,...
0
votes
0answers
41 views

Optimal Set Partitioning

Consider a set of integers $1$ to $n$, $$ \mathcal{S} = \{1,2,3,\ldots,n\} $$ initialised with no-partitions. Now let $L[f(\mathcal{S})]$ be a cost function we wish to minimise that depends on some ...
0
votes
0answers
29 views

Why For any integer point in the feasible region the right side of this equation is less than 1 and the left side is an integer?

I wanted to find Why Gomory's cut works. wikipedia Gomory's cut explains: An integer programming problem be formulated (in Standard Form) as: \begin{aligned}{\text{Maximize }}&c^{T}x\\{\text{...
0
votes
0answers
60 views

Graph Theory: Minimum Cost Spanning Tree with Kruskal's Algorithm

This is a problem for a community college course. The goal is to find the minimal cost (number) of the tree. I've tried to make a tree of my own and connect the edges, but I keep getting a number that ...
0
votes
0answers
38 views

Maximum flow problem: one arc always has full capacity in the maximum flow does this imply there is a minimal cut through this arc?

I have a maximum flow problem with directed graph G = (V, E) and edge capacities c : E → R≥0 and s, t ∈ V . Of course, there may be more than one flow f that gives the maximum flow value. But now I ...
0
votes
0answers
39 views

Can minimal addition chains always be built from smaller minimal ones?

Is there always a minimal addition chain for n that is the union of two minimal addition chains for some i, j, s.t. i+j=n, together with n itself? If so, can you provide a proof? And if not, what's ...
0
votes
0answers
26 views

Maximising a discrete valued probability function

The problem I am attempting to solve is the maximising bit. The solution talks about how we should look at adjacent terms for when $p_N≈ p_{N-1} $. However, how do I know that I am not finding a ...
0
votes
0answers
61 views

Prove the following statement about Kruskal Algorithm

Let $G$ be undirected graph, $G=(V,E)$. Consider an edge $e = (u,v) \in E$ that wasn't included in the solution obtained from applying Kruskal Algorithm to $G$. Prove that this edge isn't in any ...
0
votes
0answers
12 views

Bounds on rate $r$ for finishing $n$ jobs: $[w_1,w_2,\cdots, w_n]$ to be completed by time $H$

Given $n$ jobs $[w_1, w_2, \cdots, w_n]$ where $w_i$ represents some integer unit of work to be done, and a time $H$ (hours, integer) required to finish all the jobs, note that each job must take ...
0
votes
0answers
20 views

How this author calculates this discrete gradient?

In this paper on page 3 http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.900.2273&rep=rep1&type=pdf author gives formula for finite difference of first order The discrete gradient ...
3
votes
1answer
68 views

Best subset with exactly one success [closed]

This is an interview question that I was asked, but I totally couldn't figure it out: Given N items = {a,b,c,d,e...}, each with a probability {$P_a$,$P_b$,$P_c$,$P_d$,$P_e$...} of succeeding. Given ...
3
votes
2answers
104 views

What is $\underset{\pi \in S_n}{\max}\underset{1\leq i\leq n}{\sum}|i-\pi(i)|$, where $S_n$ is the set of permutations of $(1,2,\ldots,n)$?

What is the value of $$\underset{\pi \in S_n}{\max} \biggl( \underset{1\leq i\leq n}{\sum} \big|i-\pi(i)\big|\biggr)\,,$$ where $S_n$ is the set of permutations of $(1,2,\ldots,n)$? I can see that if ...
3
votes
1answer
47 views

Finding a subset of fixed size of a graphs vertex set that minimizes 'surface area'. AKA finding min cut for fixed partition size.

Let $G$ be a graph with vertex set $V$ and $n$ a fixed integer. I want to find a set $S\subseteq V$ with $|S|=n$ that minimizes the 'surface area' of $S$, surface area being the number of edges ...
1
vote
0answers
31 views

Estimation of the standard deviation of a zero mean distribution with partial information about it

I'm trying to estimate the standard deviation of a zero-mean distribution of values. Let me start with this brief introduction to the problem: Let $\{\Omega_{ij}^{\mu \nu}, C_{ij} \in \mathcal{Z}\}$ ...
0
votes
0answers
64 views

Solving a coupled system of linear ODEs one second order, the other first order

i want to find Aerodynamic center (y,z) and its moment(M ac) for vehicle , so i searched a lot , and i found these information . Aerodynamic center position doesn't change wrt angle , drag ,lift ...
0
votes
0answers
20 views

Kernel of Hermite Normal Form

In the following theorem, related to integer solutions of a homogenous system, I am having trouble understanding the last two sentences of the proof. I understand that an invertible matrix times a ...
0
votes
0answers
12 views

Upper bound on the TSP costs of the subsets of cities in original TSP

I have an asymmetric non-euclidean Traveling salesman problem $ p $ with an even number of cities and known cost $ c(p) $. Now I randomly split the set of cities into two equal subsets, creating new ...
1
vote
2answers
51 views

0/1 - Knapsack and similar problem on 2D Matrix [closed]

Problem: Given a 2d matrix of item weights, their respective costs in another 2d matrix, and max capacity W. Find the optimal selection such that profit is maximum(i.e sum of costs is maximum) and ...
0
votes
1answer
37 views

How to select the columns of a binary feature matrix to obtain minimal overlap

Suppose you have a (rather sparse) binary matrix with $M$ rows and $N$ columns. The columns represent objects, the rows represent features of the objects. A $1$ in the matrix indicates that the ...
1
vote
2answers
55 views

Find the largest possible number n of three-digit numbers, following a set of properties

I just recently solved the following problem Let n three-digit numbers satisfy the following properties: (1) No number contains the digit 0. (2) The sum of the digits of each number is 9 (3) The units ...
1
vote
1answer
32 views

Global minimum for $\frac{2(q - 1)(q^k + 1)}{q^{k+1} + q - 1}$, if $q \geq 5$ and $k \geq 1$

Let $q$ be a prime number, and let $k$ be an integer. THE PROBLEM Does the function $$f(q,k) = \frac{2(q - 1)(q^k + 1)}{q^{k+1} + q - 1}$$ have a global minimum, if $q \geq 5$ and $k \geq 1$? MY ...
0
votes
1answer
57 views

How to find minimum number of switches to sort a given permutation(let's say 1-10) in ascending order

King Arthur has a shelf with $10$ books, numbered $1,2,3,\dots,10$. Over the years, the volumes got disordered. Arthur tries to order the books in the increasing order by exchanging positions of two ...
1
vote
1answer
20 views

Searching for the right partitions

I have a set of integers $U$ with cardinality $311$ and whose sum is 500 dollars. I want to group all the elements of this set into three different subsets: The sum of the elements of subset $A$ is $...
0
votes
0answers
9 views

Maximizing a function whose logarithm is submodular set function

I am trying to maximize a function which itself is not submodular, but its logarithm is submodular. Does that give me any approximation result with the actual function itself? Formally, I have: $$ \...
1
vote
0answers
35 views

Maximize area spanned by convex hull of a permutation

Given an ordered set $X = (x_1, x_2, \dots, x_n), x_i \in \Bbb R^2$ and a permutation $P$ defined on $X$ and that shuffles the order of the elements in $X$, $$P(X) := (p_1, p_2, \dots, p_n)$$ and we ...
1
vote
1answer
71 views

What is the maximum value of the $4 \times 4$ determinant composed of 1-16?

If 1-9 is filled in the $3 \times 3$ determinant, and each number appears once,then the maximum value of the determinant is $412$. For example, the following determinant can take the maximum value of ...
0
votes
0answers
44 views

How to optimize a high-order objective function?

I have an objective function which I want to maximize. Ordinarily, one would perform some sort of optimization process on the parameters of this objective function in order to find parameter ...
1
vote
1answer
41 views

Half-SAT/ Half-Satisfiability

Is the following satisfiability problem hard? Given a set of clauses over boolean variables in conjunctive normal form, decide whether there is an assignment of truth values to the variables that ...
0
votes
0answers
7 views

Proof of a tight bound for binary space linear plane partitioning

I study the binary optimization problem. Constraints are formulated as $s1(x_1, x_2, ... , x_n)=a_1 x_1 + a_2 x_2 + ... +a_n x_n >= b$ where $x_i = 0 or 1$ only Assume that somehow we obtained n ...
6
votes
2answers
221 views

Best approximation of sum of unit vectors by a smaller subset

Let $v_1,\ldots,v_N$ be linear independent unit vectors in $\mathbb{R}^N$ and denote their scaled sum by $s_N = \frac{1}{N}\sum_{k=1}^N v_k.$ I would like to find a small subset of size $n$ among ...
1
vote
2answers
74 views

Let $P$ be a $3\times 3$ matrix such that all the entries are from $\{–1, 0, 1\}$. What is the maximum possible value of the determinant of $P$?

Let $P$ be a matrix of order $ 3 \times 3$ such that all the entries in $P$ are from the set $\{–1, 0, 1\}$. What is the maximum possible value of the determinant of $P$? The original question This ...
1
vote
1answer
36 views

Transforming constraints into linear inequality

I want to model the following two constraints in terms of LP, but after trying various ways without success, I wonder if it is possible at all? Given $x$ and $y_{ij}$ are binary variables. We need the ...
0
votes
0answers
22 views

Optimality condition for convex problem

Let $P_X$ denote a distribution from $\mathcal{P}(\mathcal{X})$. For each $x \in \mathcal{X}$ let $$f_x:[0,1] \rightarrow \mathbb{R}$$ denote a given decreasing convex function. The goal is to compute:...
0
votes
1answer
26 views

Convexity and NP-hardness

Suppose that we have the following optimization problem: $$Maximize_{x_{j,i}} ~ {{\sum_t \sum_i \sum_j (a_{0,i;t}+\sum_i \sum_j a_{j,i;t} x_{j,i;t})}\over{\sum_t\sum_i\sum_j x_{j,j;t} b_{j,i;t}}}$$ $$...

1
2 3 4 5
14