Questions tagged [bounds]
For questions about obtaining upper or lower bounds for certain values, usually for an optimization objective.
29
questions
2
votes
0
answers
79
views
Understanding the condition of the bounded variable algorithm in the linear programming
Following is the section 7.3 of Operation Research An Introduction by Hamdy A. Taha,
Define the upper-bounded LP model as, $$\max z=\{CX|(A,I)X=b,0\leq X\leq U\}$$
The bounded algorithm uses only the ...
- 121
2
votes
1
answer
74
views
Find projection onto implicitly defined set
I think this is a problem a lot of people have in minimization but I couldn't find algorithmic approaches to it.
Given a closed domain $D\subset R^n$ over which a function $f$ is supposed to be ...
- 21
1
vote
1
answer
51
views
Get objective upper bound in a callback (cplex)
I wonder if there is a way to retrieve the global objective upper bound in a callback in Cplex (in cpp)? I tried several context/IloCplex/IloModel... methods but nothing worked.
0
votes
1
answer
46
views
Deriving a lower bound for a two-stage stochastic problem
Assume an inventory stochastic optimization problem in the following form:
$$\min\limits_{x\in X} c^\top x + \mathbb{E}_{\mathbb{\xi}}[\mathcal{Q}(x, \xi)]$$
Demand is the uncertain parameter, and is ...
- 2,086
2
votes
3
answers
333
views
Upper bound on length of solution of linear program
Consider the linear program:
$$\text{maximize} ~~ c\cdot x \\ \text{subject to} ~~ A\cdot x\leq b, ~~x\geq 0.$$
Suppose $A$ is an $m\times n$ matrix, $b$ an $m\times 1$ vector and $c$ an $n\times 1$ ...
2
votes
1
answer
145
views
Reduced cost fixing for binary programs
Consider the binary program
$$ \min_{ x \in \{0,1\}^N } \left\{ c^T x \mid Ax \leq b \right\}$$
where $A$ and $b$ are real matrices with appropriate dimensions. I am interested in solving large binary ...
- 66
6
votes
1
answer
258
views
Binary decision variable to indicate whether a continous decision variable is equal to its upper bound
Given a continuous nonnegative decision variable $x\in [0,T]$ bounded by $T$, how can we enforce a relation between $x$ and another binary decision variable $y$ such that when $x$ is equal to its ...
- 147
3
votes
3
answers
239
views
Improving best bound within B&B process
Here is an extract from the BnB solution process of my problem. The solver determines a value of 2627.452494 as being the best bound of the optimal solution. The value for the best bound remains the ...
- 2,180
2
votes
1
answer
188
views
What is the role of computation lower bounds for exact methods, heuristics, and hybrid of exact and heuristics?
I'm struggling with this question for weeks:
What is the main difference between the role of computation lower bounds for exact methods, heuristics, and hybrid of exact and heuristics?
I try to answer ...
- 21
6
votes
1
answer
127
views
Lower bounds for TSP with k missing nodes
I'm struggling with this question for several weeks already and seem to be either stuck, or the bound is not going to be any better. Let's jump right into the problem:
Given a standard TSP on a graph $...
- 121
6
votes
1
answer
466
views
Upper and lower bounds of a variable equal
I'm working on a MILP (Mixed-Integer Linear Programming) problem with the Java API of Cplex.
In order to easily exclude some variables from my problem I thought about setting both their lower and ...
- 307
2
votes
1
answer
269
views
What is an acceptable gap for a lower-bound?
Based on your experience, I want to know what is called an acceptable lower-bound.
I know it can be different based on the problem. For example, is 5% is an acceptable lower-bound gap for VRPTW? By ...
- 683
1
vote
1
answer
336
views
How to convexify log(convex) function?
I have the following optimization problem: \begin{align}\max_x&\quad\log_2(1+|a+bx|^2+cx^2)\\\text{s.t.}&\quad0\le x\le1\\&\quad(1-x^2)\ge\text{constant}\end{align} where $a$ and $b$ are ...
1
vote
1
answer
160
views
Find an upper bound for an objective function
My objective function is $\log_2(1+{x^2y^2})$ and I found two upper bounds for $x^2$ and $y^2$.
For example, assumed that we have the following upper bounds:
$x^2\leq\text{constant}_1^2$ and $y^2\leq\...
4
votes
1
answer
926
views
Which is better to minimize w.r.t a lower bound or an upper bound of an objective function?
Suppose there is a optimization problem that aims at minimizing an objective function $X$ but we can't develop a mathematical model for minimizing $X$. However, there are two objective functions $Y$ ...
- 489
7
votes
3
answers
1k
views
How do Quadratic Programming solvers handle variables without bounds?
Solvers for non-convex QPs generally do the McCormick relaxation of the term $xy=z$ and then do spatial branch and bound.
This requires that $x$ and $y$ have given bounds, how do they handle the case ...
- 3,635
2
votes
0
answers
79
views
Heuristic to compute upper bound for the simple assembly line balancing problem type 2?
I am currently working on SALBP-2 described as:
Given the number m of assembly stations, minimize the cicle time c.
I have done a bit of research and found the following approach to solve it:
The ...
- 121
2
votes
2
answers
757
views
How to use tight upper and lower bounds to get to the optimal value via branch and bound?
I have algorithms that get me a tight upper (UB) and lower (LB) bound to a maximization binary integer program (a routing problem). My formulation is non-compact and requires the addition of sub-tour ...
2
votes
0
answers
193
views
Ways to improve lower bounds while solving MIPs
What are the ways to improve lower bounds while solving a minimization problem (MILP)?
- 21
10
votes
2
answers
241
views
How to exploit known solution in MILP
I have an MILP model to which I get an integer feasible solution as a result of a heuristic search. In this particular example, the initial solution turns out to be the optimal solution, which I prove ...
- 2,180
7
votes
1
answer
82
views
An upper-bound on the value of $S$ in $(s,S)$ policy
I recently have come across a problem which can be categorized as a stochastic optimization. The problem seems simple, but I haven't been able to solve it yet. It has a major impact on algorithm ...
5
votes
1
answer
468
views
Solving a variant of multiple knapsack problem/ generalized assignment problem
Consider $m$ knapsack and $n$ items. With each knapsack $j$ associated a capacity $c(j)$ and with each item $i$ associated a profit $p(i,j)$ (that depends on the knapsack, so it's not exactly the ...
- 943
18
votes
3
answers
1k
views
Variable fixing based on a good feasible solution
Suppose you have a combinatorial optimization problem that is formulated as a mixed integer linear program (minimization). The problem size is denoted $n$ and the expected $n$ is around $100$. The ...
- 2,140
11
votes
4
answers
384
views
Proof of bound on optimal TSP tour length in rectangular region
Lemma 3 in Haimovich and Rinnooy Kan (1985) (Math of OR 10(4):527–542) says:
If $X$ [the set of nodes] is contained in a rectangle with sides $a$ and $b$, then
$$ T^*(X) \le \sqrt{2(n-1)ab} + 2(a+...
- 13.1k
25
votes
6
answers
2k
views
How to compare two different formulations of a problem?
I somewhat know how to compare two MILP formulations of a problem that both use the same set of decision variables (as in the classical MTZ vs DFJ formulations of the TSP). I was wondering how two ...
- 2,140
16
votes
1
answer
1k
views
Prove that these linear programming problems are bounded by $O(k^{1/2})$
Prove that these linear programming problems are bounded by $O(k^{1/2})$
Conjecturally the expanded partial sums of the Möbius transform of the Harmonic numbers have two out of three properties in ...
- 281
21
votes
5
answers
632
views
Tightness of an LP relaxation without using objective function
How can we measure the tightness of a linear programming relaxation for a mixed integer linear program without using the objective value? I would like to get a measure in terms of the feasible set and ...
- 540
15
votes
1
answer
883
views
How to get the best bound of large LP problems in CPLEX?
When using the C callable library to solve a large LP, how can I get the best bound after calling the method CPXXlpopt? Does it depend on the algorithm used to ...
29
votes
3
answers
1k
views
Feeding known lower bounds to solvers
Given an optimization problem that aims at minimizing some objective function, a lower bound that is valid for all feasible solutions, and your solver of choice:
For what theoretical and/or practical ...
- 1,006