Questions tagged [bounds]
For questions about obtaining upper or lower bounds for certain values, usually for an optimization objective.
31
questions
0
votes
1
answer
33
views
Pulp Optimization with Decision Variable as Boundary
I am currently working on a linear programming problem using the Pulp library in Python. The problem involves optimizing the capacity of a battery, which is represented as a decision variable in my ...
- 191
1
vote
1
answer
168
views
Lagrangian Relaxation Lower Bound exceeds the Upper bound and the Optimal solution
I'm trying to minimize an MIP model employing a Lagrangian relaxation approach. However, I've encountered an issue where, in certain instances, the lower bound (resulting from the Lagrangian sub-...
- 19
2
votes
0
answers
94
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
83
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
79
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
2
answers
73
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,104
3
votes
3
answers
420
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$ ...
- 1,019
2
votes
1
answer
164
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
264
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
262
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,252
2
votes
1
answer
202
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
134
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
519
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
299
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
369
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
166
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
1k
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$ ...
- 521
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,655
2
votes
0
answers
90
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
887
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
1
answer
274
views
Ways to improve lower bounds while solving MIPs
What are the ways to improve lower bounds while solving a minimization problem (MILP)?
- 29
10
votes
2
answers
263
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,252
7
votes
1
answer
87
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
480
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 ...
- 963
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
386
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
672
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
936
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 ...
31
votes
3
answers
2k
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,026