6
$\begingroup$

I have a "mathematical programming" (MP) problem that does not have an objective function. Namely, I want to find a vector that satisfies all constraints (no optimization involved, right?). Now, a couple of (maybe) silly questions come to my head:

  1. A "mathematical programming" problem with no objective function is a valid mathematical programming problem?

  2. Whatever the nature of this problem, it can be implemented in optimization software by adding a dummy objective function that is just ignored. So, is this an optimization problem or not? Is it an existence problem that may be solved by construction (finding the solution if it exists)?

  3. Does this kind of problem have a particular name?

Improve this question
$\endgroup$
1
  • $\begingroup$ In addition to the other answers I would like to note that any instance of a mathematical program that minimizes $v(\mathbf{x})$ with some set of constraints $f(\mathbf{x}) \leq \mathbf{c}$ can be transformed into an always satisfiable optimization problem by minimizing $v(\mathbf x) + \max \{0, s_1, s_2, \dots \}$ subject to $f(\mathbf{x}) + \mathbf{s} = \mathbf{c}$. In your case let $v(\mathbf x) = 0$. $\endgroup$
    – orlp
    Mar 3, 2021 at 14:08

3 Answers 3

Reset to default
11
$\begingroup$
  1. Yes. But some software may require explicit specification of an objective, which can be a constant.
  2. Yes. An optimization solver will attempt to find a feasible solution. Any feasible solution is optimal.
  3. Feasibility problem.

Some optimization modeling systems or optimization software require an objective to be provided. In such case, you can specify the objective as a constant of your choice; zero is a popular choice.

If there are no inequalities, a feasibility problem is often called "root finding", or "solving a system of equations".

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ I agree on points 1 and 3. With point 2, I suspect it depends on who is asking, a mathematician, an engineer or a lawyer. $\endgroup$
    – prubin ♦
    Mar 2, 2021 at 20:43
  • 1
    $\begingroup$ @prubin As an O.R. person, If i can solve a problem using an optimization solver, I'll consider it an optimization problem, even though it might also have an akternate characterization. $\endgroup$
    – Mark L. Stone
    Mar 3, 2021 at 2:24
  • $\begingroup$ @MarkL.Stone For 2. if it's MINLP a feasible point won't necessarily satisfy KKT so it depends on your definition of "optimal". Many optimisation solvers also don't necessarily solve for KKT points (e.g. derivative-free solvers). $\endgroup$
    – Nikos Kazazakis
    Mar 3, 2021 at 16:38
  • $\begingroup$ My answer does not say anything about KKT one way or another. Any feasible solution to an optimization problem having a constant objective, is optimal. Whether the solver reoogizes it as such, is another matter. Some sokvers have rather non-robust termination criteria. And frankly some solvers "blow". $\endgroup$
    – Mark L. Stone
    Mar 3, 2021 at 18:24
9
$\begingroup$

These problems are known as Constraint Satisfaction Problems. In contrast, problems with an objective function are known as Constraint Optimization Problems. Many examples exist. E.g. given some graph with an incomplete edge set, does there exist a closed tour in the graph such that every city is visited exactly once? Or find a schedule that satisfies all scheduling constraints, e.g. every shift needs to be assigned to someone, there must be 1 day off between two different shifts assigned to the same person, no-one can work more than 5 consecutive days.

Not all optimization solvers require you to specify an objective function. Even if they do, if the objective is irrelevant you can always specify some dummy objective. In some cases, if you are simply interested in finding any feasible solution, you can actually specify a suitable objective function, and terminate the search when the first feasible solution is found.

Improve this answer
$\endgroup$
2
  • $\begingroup$ So, if the problem is a constraint programming problem with quadratic constraints and integer decision variables, would it be confusing to refer to this problem by such name? Would it be less confusing if I state that this problem is a QCIP (quadratically constrained integer programming problem) with no objective function? $\endgroup$
    – jesús garcía
    Mar 2, 2021 at 18:56
  • 1
    $\begingroup$ @jesúsgarcía Personally I would not use QCIP since this is not commonly used in papers (I did not find this abbrev. anywhere). You could always introduce this acronym in your text, but I would prefer to stick to commonly used acronyms. Your problem is a Nonlinear Programming Problem (NLP), or even a Mixed-Integer Nonlinear Programming (MINLP). Moreover, in the absence of an objective function, it is also a Constraint Satisfaction Problem (CSP). In the world of Constraint Programming (CP), problems with or without objective are common, and all of them are referred to as CP problems. $\endgroup$
    – Joris Kinable
    Mar 2, 2021 at 19:13
3
$\begingroup$

Others have answered most of your questions so I'll just add a bit of info on 2.

Any optimisation solver would support this formulation unless it's a very crappy one. Our solver even has a special exit flag for this, Found_Solution_For_CS_Problem. What might not support the notation explicitly is the modelling environment.

For instance, AFAIK GAMS requires users to specify an objective no matter what. The most common way to do this is to simply minimize 0.

AMPL on the other hand doesn't need an objective defined, and under the hood it passes $obj=0$ to the solver.

When we receive such a problem in our solver we simply solve $\min_{x\in X} 0$, s.t. the constraints.

It's important to note that it's bad practice to introduce a dummy variable, because unless you remember to fix its bounds the problem will be unbounded, e.g. $\min x, x\in[-\infty,\infty]$ is an unbounded problem if $x$ doesn't appear in your constraints, regardless of your other constraints. Most solvers reeeeeally don't like unbounded problems.

The algorithms used to solve constraint satisfaction problems reuse all the basic building blocks but are slightly different because we don't have an objective value to guide us.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.