Stack Exchange Network

Stack Exchange network consists of 174 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]

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 ...

0
votes
0answers
13 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
10 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
17 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
30 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 Jarnik-Prim ...
0
votes
0answers
16 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
22 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
20 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
30 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. ...
2
votes
0answers
85 views

What is the maximum value of $x^TAx$ subject to $x\in\{\pm1\}^n$?

Let $A \in \mathbb{R}^{n\times n}$ be symmetric and positive definite. What is the following maximum? $$\max_{x\in\{\pm1\}^n}x^T A x$$ My attempt: if all $a_{ij}\geq 0$, then \begin{equation} \...
0
votes
0answers
19 views

What are the directions of research in Numerical Optimization?

I have just begun reading in the field of Numerical Optimization. Are people trying to invent new Algorithms? or proving the convergence of Heuristic Algorithms? and what else? What are the tools a ...
0
votes
1answer
36 views

Maximise $z = \frac{y}{2x+2y}+\frac{50-y}{200-2x-2y}$ given that $x+y$ is non zero and $x+y<100$. Also, $x\leq50$ and $y\leq50$ and non-negative.

Z is actually a probability function. I am finding where the probability is maximized. But I could find no way how to maximize this function. Original question is as follows: Mr A wants to join a ...
4
votes
2answers
102 views

What is the biggest possible sum $|X_1-X_2|+|X_2-X_3|+\cdots+|X_{n-1}-X_n|$ where $X_1,X_2,\cdots,X_n$ are first $n$ positive integers?

What is the biggest possible sum $|X_{1}-X_{2}|+|X_{2}-X_{3}|+\cdots+|X_{n-1}-X_{n}|$ where $X_{1},X_{2},\cdots,X_{n}$ are first $n$ positive integers?
3
votes
1answer
31 views

Limitations of SDP

Semidefinite programming seems to be a very powerful tool to approach NP-hard optimisation problems, for example in discrete optimisation and there are some very interesting results (like the max cut ...
0
votes
0answers
6 views

Applications of high mean escape time subgraphs

I am learning about algorithms for finding subgraphs with high mean escape time, and I am wondering if someone could enlighten me on what applications there are for such a task. Applications to either ...
0
votes
0answers
21 views

Discretization of PDE

Set $\Omega = (0,1)$. (*) I have given $\int_{\Omega} e^x u' v' = \int_{\Omega} fv $ for all $v \in H_0^1(\Omega)$. I found the solution $u \in H_0^1(\Omega)$: $u = -c_1 e^{-x} + c_2 - e^{-x} $ for ...
0
votes
0answers
15 views

need help (or literature) with an optimization problem

Hello, during my master thesis i came across an optimization problem which essentially has the form: $\min_{(n,L) \in \mathbb{N}^2} n C_1 h^{-rL}$ such that $C_2h^{q_1 L}+\frac{C_3}{n^{1-\frac{1}...
0
votes
0answers
31 views

Trying to formulate optimization problems as a linear program (LP) or a quadratic program (QP)

I'm trying to formulate and determine the variables, objective, and constraints for the minimization problem $\min_\vec{x}f(\vec{x})$ for the following functions $f \in$ ($q,r,s,t$) as linear program (...
0
votes
0answers
23 views

Show that the set of nonpositive rational numbers is countable [duplicate]

Can someone show that the set of nonpositive rational numbers is countable ?
0
votes
2answers
38 views

How to find the modules of a big number with a big powe ?? [closed]

How to find the modulus of a big number with a big power? Such as $2222^{5555}$ or $5555^{2222}$ (mod 7)?
1
vote
0answers
58 views

Fock-space-related combinatorial problem

I don't really know how to approach a combinatorial problem arising from the physics context. Here's the setting. The state of a bosonic system in ${(1+1)}$ dimensions is described by a vector of the ...
0
votes
0answers
15 views

Symmetry breaking in VRP families problem

Hollo everybody I have a question about symmetry in VRP problem. What is the meaning of symmetry and asymmetry condition in the optimization problem and could you pls tell me, how can we break it from ...
0
votes
1answer
24 views

- Optimization - Standard Grid Search

I'm struck into an portfolio opt. problem and the paper I'm replicating (or, better, trying to) is using a "Standard Grid Search". Since I never encountered it before, I would like to ask you about: ...
0
votes
0answers
36 views

Combination of unique subsets - Combo menu problem

I have a food menu with multiple categories and several options in each one. The combo meal selects one from each category. I want to find how many combinations I can make from this menu, but with the ...
1
vote
1answer
29 views

Converting a supermodular optimization problem to submodular optimization

A constrained concave maximization problem can be converted to a constrained convex minimization problem by negating the objective function and keeping the constraints intact. But in case of ...
0
votes
0answers
29 views

Integer Optimization with a specific form ($\sum f_{ij} (x_i,x_j)$)

I encountered a series of integer optimization problems that share a similar structure. The integer variables are $(x_1,x_2,\cdots,x_n)$, where each $x_i$ is non-negative. The objective function $f$ ...
0
votes
1answer
21 views

Optimizing in role-playing games [closed]

I know the answer to this must be out there somewhere, because people play a lot of games (online or otherwise) that do this sort of thing, but I don't know what words to search for. (The existence of ...
1
vote
0answers
29 views

Under what condition, the optimal solution of assignment problem is unique?

Is there any conditions that can make the optimal solution of a assignment problem unique? I know if there is no conditions on the cost matrix, it is not guaranteed to have a unique solution. (e.g. ...
-1
votes
1answer
39 views

definition of a set function?

Assuming $A$ is a set, then $F: A\rightarrow \mathbb{R}$. We can define $F(\varnothing) = 0$. But what is $F(x)$ for $x\notin A$? Is it 0?
0
votes
0answers
12 views

Submodular functions and roof duality

Is there a good online source to understand roof duality derivation and possibly a toy example coded in python? Not sure if the question is valid for this forum. I have searched a lot to find some ...
1
vote
2answers
88 views

Calculate the constant acceleration needed for the discrete time trajectory to intersect a given target point

I have an object with an initial velocity in 2D space represented by a vector. I want to calculate a constant acceleration with a given magnitude required for the object to (potentially) change ...
8
votes
1answer
143 views

Maximize the trace of a matrix by permuting its rows

I have been struggling with a combinatorial problem that eventually translates to the following: Given an $n \times n$ nonnegative matrix, find a permutation of the rows that maximizes the trace. ...
0
votes
1answer
85 views

How to solve binary nonlinear programming problems?

I have written binary nonlinear programming problem: Now I want to solve this problem. My decision variables are $x_{i,j}, y_{i,j}$ and $z_{i,j}$. The other terms are constants. N=30 and K=4. I ...
1
vote
1answer
30 views

Solving a many-to-one assignment problem with additional constraints

Assume there are $M$ items and $N$ people with $M \ge N$. A single item can be assigned to more than one person; however, item $i$ cannot be assigned more than $d_i$ times in total. Furthermore, ...
1
vote
0answers
33 views

Assignment problem with multiple total sum constraints for various parametres

I have an assignment problem. There are $N$ tasks and $M$ people. Assigning job $i$ to person $j$ will result in a profit of $p_{ij}$ and also comes with various other parameters, say, stress of $s_{...
0
votes
1answer
35 views

What is the term used to describe a discrete function which is non-zero at only 1 point, and zero everywhere else? Intended for a spatial domain.

Please see the image below. What is the formal term for the type of function shown below. One could describe it as a uniform distribution and the domain being x=5. But this is not elegant One could ...
0
votes
0answers
35 views

Graph Clustering - Capacitated VRP on a MultiDiGraph

I'm working on the problem of the CVRP on a Multi Directed non-complete graph that has been extracted from OpenStreetMaps using OSMnx. In the extracted graph I have also 'flagged' several delivery ...
2
votes
1answer
62 views

How to formulate this optimization problem mathematically?

Suppose we have a discrete function $f(x,y,z),g_1(x,y),g_2(y,z)$ in which $x,y,z\in \{1,...N\}$. I want to find several $\{(x_1,y_1,z_1),...,(x_K,y_K,z_K)\}$ triples such that $g_1(x_i,y_i)$ ranks in ...
1
vote
1answer
43 views

How to rewrite this optimization problem in standard form? [duplicate]

Consider the following problem \begin{eqnarray*} \underset{y}{\max} & f(y)\\ s.t. & y_{1}A_{1}+y_{2}A_{2}+y_{3}A_{3}+S_{1}=C_{1},\\ & y_{4}A_{4}+y_{5}A_{5}+y_{6}A_{6}+y_{7}A_{7}+S_{2}=C_{...
0
votes
1answer
33 views

How can we rewrite this optimization problem in standard form?

Consider the following problem $$ \begin{array}{crl} &\underset{y}{\max} & f(y)\\ s.t. & y_{1}A_{1}+y_{2}A_{2}+S_{1}&=C_{1},\\ & y_{3}A_{3}+y_{2}A_{4}+y_{5}A_{5}+S_{2}&=C_{2},\...
4
votes
1answer
65 views

Maximal diagonalization of a matrix by permutation matrices

I found an interesting problem based on a project I'm working on at my job. I'd like to share and see if anyone either knows if it is well-known or if anyone has any algorithms or techniques for ...
0
votes
0answers
43 views

Adding to the objective the absolute differences of numbers that are multiples of decision variables in mixed integer programming

I am trying for formulate a mixed integer program that optimizes the cost of transferring water through three piping systems. I have three tanks $S_i$, $i= 1,2,3$. Each tank $S_i$ has $5$ pipes ($j=...
0
votes
0answers
25 views

A ring to place numbers in, how to select numbers uniquely to minimize running variation?

Say I have the numbers in some list $\{1,2,2,3,4,3\}$ and I want to select them uniquely and place so that the average variation (for example running absolute difference, or running square difference) ...
1
vote
0answers
46 views

Integer equivalent of If-conditions

I had found the following statements to find integer equivalent of the if statement which I have lost. However, I have tried to recall those statements and tried to prove them all. Can the community ...
2
votes
1answer
51 views

Maximizing Euclidean length of $\pm 1$-combination of given vectors

Suppose we have 3d vectors $v_1, v_2, \dots, v_n$ where typically $n$ is large (100 or so). Then we want to find a sequence of $\pm$ such that $|\pm v_1 \pm v_2 \pm \dots \pm v_n|$ is maximal. Note ...
1
vote
1answer
41 views

Is the LP-relaxation value on a subset of variables a bound for that subsets value in the MIP solution?

Say we're given the following integer problem: $\min c^Tx$ s.t $Ax \leq b$ $x \in \{0,1\}^n$ and its corresponding LP-relaxation: $\min c^Tx$ s.t $Ax \leq b$ $x \in [0,1]^n$ Then we can ...
9
votes
3answers
137 views

Find smallest set of natural numbers whose pairwise sums include 0..n

Given a positive integer $n$, how do you find the smallest set of nonnegative integers $S$ such that for each integer $m$, where $0\leq m<n$, there exist two (not necessarily distinct) members of ...
1
vote
0answers
66 views

Life cycle model in Matlab

I am currently working on a life cycle model about saving and investing for pension funds. However, I have some problems solving the model. The model runs for $T$ years over the life cycle. At every ...
1
vote
0answers
60 views

Splitting a graph into disjoint blocks

Suppose we are given a weighted graph $G=(N,E)$ ($W(e)$ is the weight corresponding to $e\in E$). Let $d(i,j)$ denote the minimum weighted distance between nodes $i$ and $j$. My goal is to split the ...
0
votes
0answers
28 views

Maximize HCF of a set of integer variables given their range

$$ \max \operatorname{HCF}(x_1, x_2 \dots x_n) $$ subject to $$\qquad \qquad \quad l_i \le x_i \le u_i \qquad \forall i=1 \dots n$$ $$ x_i, u_i, l_i \in \mathbb{Z}^+ $$ where HCF is the Highest ...
1
vote
1answer
30 views

Genus - Roads Crossings.

There are ten roads linking all possible pairs of five cities. It is known that there is at least one crossing of two roads, as illustrated in the diagram below on the left. There are nine roads ...